March 16, 2019 2019 Humblefool Cup Editorials

2019 Humblefool Cup Prelims were held on March 15, 2019. Click here to see the detailed match results.

SwappingNodes – (Easy)

This is a simple ad-hoc problem.
When leaves are [5,3,2,1] and we perform swapping on ROOT of the tree the new permutation on the leaves will be [2,1,5,3]

Idea:
We start from lowest level above the leaves and proceed to highest level (root):
     For each node in that level:
         If left most leaf in its left subtree is greater than left most leaf in its right subtree:
              We perform swapping (Equivalent to swapping 2i leaves of left and right subtree)
 
This is equivalent to following process in terms of array
 For 2 elements at a time
     Take first two elements
         If 0th is greater than 1st, swap
     Take next two elements
         If 0th is greater than 1st, swap
     And so on.
 For 4 elements at a time
     Take first four elements
         If 0th is greater than 2nd, swap
     Take next four elements
         If 0th is greater 2nd swap
     And so on.
 For 8 elements at a time
     Take first 8 elements
         If 0th is greater than 4th, swap
     Take next 8 elements
         If 0th is greater than 4th, swap
     And so on.
  And so on.
Complexity: At each level we iterate entire array of leaves once.
Thus complexity is O(NlogN) where N is number of leaves.

 

Code in JAVA :
public int[] swapNodes(int[] leaves,int numberOfLeaves) {
        int i,j,k,l,temp;
        for(i=1; i<numberOfLeaves; i = i*2) {
            for(j=0,k=i; j<numberOfLeaves && k<numberOfLeaves; j += (2*i) , k += (2*i))
            {
                if(leaves[j] > leaves[k])
                    for(l=0; l<i; l++) {
                        temp = leaves[j+l];
                        leaves[j+l] = leaves[k+l];
                        leaves[k+l] = temp;
                    }
            }
        }
        return leaves;
    }

DismantleTheTree ñ (Medium)

This is a problem based on dfs.

Idea:
If a node has K edges with weight W (apart from the one connecting the current node to it's parent)
The edges will be removed in pairs of two and paying cost W for each pair.
If K is even , all the edges vanish in these pairs and cost becomes W(K/2) When K is odd , all edges except one edge will vanish in these pairs adding cost with W*floor(K/2)
     For this remaining edge, if it has same weight as the one connecting current node with it's parent, we leave it (as it's cost will be considered in some ancestor node of the path) otherwise add another W to our cost.

Algorithm: 
Let's consider the tree to be rooted at 1.
At every node create an array freq[] such that freq[i] is count of edges with weight equal to i incident on that node, where i varies from 1 to 100, inclusive.
 call dfs from 1 with its parent as -1.
 Inside dfs with a node 'u' and parent 'p'
     for each of its child call the dfs and sum up the result of every call.
     first decrement freq[w] where w is the weight of edge connecting the current node 'u' with its parent 'p'
     for each i from 1 to 100
         first increment the ans by i*freq[i]/2;
         if freq[i] is odd and i !=w(where w is the weight of edge connecting the current node 'u' with its parent 'p' ) then increment ans by another i.

Complexity: At each dfs call we iterate from 1 to 100 to check for each edge weight. Thus complexity is O(N*(N+100)) where N is number of nodes.

Code in JAVA :
// dfs function in java (Using adjacency matrix)
// tree is the adjacency matrix and freqs[i][j] is count of edges with weight j incident on node i
public int dfs(int node,int par) {
int parEdge = -1;
    if(par != -1)
        parEdge = tree[node][par];
    int ans = 0;
    int i;
    for(i=1;i<=N;i++)
        if(i != par && tree[node][i] > 0)
            ans += dfs(i,node);
    if(parEdge != -1)
        freqs[node][parEdge]--;
    for(i=1;i<=100i++)
    {
        ans += (i*(freqs[node][i]/2));
        if(freqs[node][i]%2 == 1)
        {
            if(i != parEdge)
                ans += i;
        }
    }
    return ans;
}

Alternate approaches :-
1) Above code can be solved with using adjacency list in O(N100). 2) ( Provided by misof ) Consider only the edges with some specific weight c. If you have exactly 2k nodes with an odd degree, you need at least k paths (i), and it can always be done using k paths (ii), so the contribution to the solution is kc.
i) Each path will change the parity of only two nodes: the one where it starts and the one where it ends.
ii) If you connect some k-1 pairs of odd vertices by new edges in a way that makes the graph connected, it will have an Euler tour. Remove those edges again to split the tour into k paths.

Code in python ( by misof):-
class DismantleTheTree:
     def dismantle(self, N, X, Y, W):
         degrees = { (x,w) : 0 for x,w in zip(X+Y,W+W) }
         for x,w in zip(X+Y,W+W): degrees[x,w] += 1
         return sum( (d%2) * w for (x,w),d in degrees.items() ) 

PrimeAlters – (Hard)

The problem required you to perform few calculations on your local machine, collect artifacts and code them.
Idea : (By misof)
The answer is almost always "yes".

On your machine, use the Sieve of Erathostenes to generate all primes up to 10^8 and run BFS to find the connected components of the graph. For small numbers of digits you'll find that the entire graph is connected, for larger numbers of digits there will be a few isolated vertices, a single component of size 2, and the entire rest of the graph is connected. Once you know this, the easiest way to get accepted is to hardwire the few exceptions into your solution. The entire solution you submit will then just check for the exceptions and answer "yes" otherwise.

The really top contestants should see that this approach will work before implementing anything. Here's how: Primes are not random, but in most aspects they behave as if they were. Thus, what we have here is essentially a large random graph with rather large vertex degrees (see below), and it is known that dense random graphs behave this way.
 
There are roughly n/ln(n) primes up to n. Among the 45,000,000 odd numbers with 8 digits, around 5,000,000 are prime. If you pick a prime number, there are 66 other odd numbers that differ from it in a single digit. 
On average, about seven or eight of those should be prime. (This is indeed true. For 8 digits the graph has over 20,000,000 edges, putting the average degree a little over 8.) If this was a truly random graph, the edge probability would put us significantly beyond the threshold probability from which essentially all graphs are connected. As it's not a truly random graph, we may expect some artifacts, but as it turns out, not too many.
Code for local machine to find out the artifacts

(406 isolated nodes , 1 component of size 2 : 89391959 and 89591959 ,Apart from these any prime number is reachable by any other prime number given they are of same length)

#include<bits/stdc++.h>
using namespace std;
#define nm 100000000
bool sieve[nm];
int parent[nm];
int size[nm];
char arr[15];
int par(int x)
{
    if(x == parent[x])
        return x;
    return (parent[x] = par(parent[x]));
}
void unio(int u,int v)
{
    u = par(u);
    v = par(v);
    if(u != v)
        parent[u] = v , size[v] += size[u];
}
void func(int u)
{
    sprintf(arr,"%d",u);
    int d,i;
    int len = strlen(arr);
    int v,temp;
    for(i=0;i<len;i++)
    {
        if(i == 0)
            d = 1;
        else
            d = 0;
        for(;d<9;d++)
        {
            if(d != arr[i]-'0')
            {
                temp = arr[i];
                arr[i] = '0'+d;
                v = atoi(arr);
                if(sieve[v] == 0)
                    unio(u,v);
                arr[i] = temp;
            }
        }
    }
}
int main()
{
    int i,j;
    for(i=2;i*i<nm;i++)
        if(sieve[i] == 0)
            for(j=i*i;j<nm;j+=i)
                sieve[j] = 1;
    for(i=1;i<nm;i++)
        parent[i] = i , size[i] = 1;
    for(i=2;i<nm;i++)
        if(sieve[i] == 0)
            func(i);
    set <int> s;
    set <int> :: iterator it;
    for(i=2;i<nm;i++)
        if(sieve[i] == 0)
            if(size[par(i)] == 1)
                cout << i << endl;
            else if(size[par(i)] == 2 && i != par(i))
                cout << i << " " << par(i) << endl;
    return 0;
}

//By misof
import java.util.*;
import java.math.*;
public class PrimeAlters {
    int[] isolated = { 294001, 505447, 584141, 604171, 929573, 971767, 1062599, 1282529, 1524181, 2017963, 2474431, 2690201, 3070663, 3085553, 3326489, 4393139, 5152507, 5285767, 5564453, 5575259, 5974249, 6173731, 6191371, 6236179, 6463267, 6712591, 7204777, 7469789, 7469797, 7810223, 7858771, 7982543, 8090057, 8353427, 8532761, 8639089, 9016079, 9262697, 9537371, 9608189, 9663683, 9700429, 9931447, 10506191, 10532453, 10564877, 11124403, 11593019, 12325739, 12968519, 14075273, 14090887, 14151757, 15973733, 16497121, 17412427, 17412599, 17424721, 18561293, 18953677, 19106729, 19158221, 19579907, 19851991, 20212327, 20414561, 21044557, 21089489, 21281479, 21496661, 21668839, 21717601, 21825337, 22138349, 22431391, 22480351, 23196157, 23228479, 23274191, 23462969, 24328567, 25081361, 25151927, 25475617, 25556941, 25768091, 25872199, 25948847, 26024267, 26521721, 27242179, 27245539, 27425521, 27465103, 27469241, 28046353, 28070047, 28978889, 29136091, 29348797, 29617897, 29638519, 30791767, 30915637, 30964013, 31181461, 31240481, 31746383, 31839427, 32524313, 33051769, 34302127, 34349969, 34586371, 35009671, 35319367, 35355923, 35673679, 35954509, 36221597, 36438379, 36745811, 37074487, 37095427, 37448137, 37763641, 38178211, 38530123, 38585039, 38774851, 38888137, 39397009, 39600559, 39689597, 39724417, 40085977, 40432489, 40638727, 40812781, 41745331, 41980441, 42120581, 42145837, 42758917, 43414669, 43432409, 43924399, 43988459, 44617561, 44750351, 45412331, 45420457, 45743483, 46031123, 46301219, 46448719, 46591507, 47263001, 47457367, 47500217, 47632271, 47744239, 48024359, 48143047, 48341959, 48384977, 48441331, 49259803, 49353841, 49453847, 50030077, 50170513, 50413439, 50456519, 50471857, 50592911, 50729603, 51340909, 52127189, 53355689, 53420963, 53454589, 53751119, 53753587, 53977403, 54048263, 54127231, 54292081, 54559123, 54868459, 55204889, 55959643, 56242891, 56485057, 56660599, 56690071, 56743469, 57013823, 57177889, 57375139, 57980963, 58020581, 58091653, 58107953, 58366619, 58572593, 59088739, 59160317, 59704529, 59816347, 60114073, 60496231, 60949807, 61089089, 61363157, 61552901, 61575539, 61589579, 61974541, 62155259, 62324861, 62444033, 62552489, 62725253, 63359161, 64085921, 64087411, 64353493, 64843237, 65029997, 65040751, 65314439, 65366051, 65420917, 65702393, 65947213, 66117679, 66640253, 66854549, 67149403, 67296517, 67489091, 67715653, 67959743, 68030449, 68428379, 68495347, 68970457, 69315427, 69374167, 69375203, 69505109, 69912431, 70006253, 70078549, 70498907, 70514141, 70717291, 70850641, 71364053, 71370853, 71756029, 71760109, 72168857, 72418187, 72422393, 72504457, 72519631, 72534029, 72673213, 72760297, 73022273, 73115993, 73179193, 73440439, 73644101, 74143801, 74190419, 74543663, 74711779, 75374149, 75448801, 75460849, 75957857, 76297087, 76424609, 76456141, 76720291, 76828823, 77250497, 77438461, 77444701, 77511487, 77540017, 77675639, 77844287, 78050209, 78440119, 78562307, 78712681, 78958211, 79477127, 79522043, 79556513, 79833133, 80054363, 80286407, 80468587, 81397777, 81434501, 81536501, 81594283, 81608981, 81738799, 81811589, 82087813, 82319411, 82542419, 82742243, 82761961, 82764371, 82817039, 82892633, 82905047, 83127119, 83407327, 83610599, 83880829, 84083011, 84159917, 84255251, 84487439, 84733919, 85415249, 85468223, 85478369, 85637089, 86504879, 86688269, 87055763, 87077527, 87281011, 87303817, 87517271, 87615019, 87737701, 88551439, 88826693, 88903379, 88948439, 89006641, 89146619, 89391959, 89591959, 89473777, 89602771, 89819413, 90997241, 91384849, 92027977, 92305589, 92519951, 92707619, 92782441, 93117217, 93573091, 93831383, 94113781, 94874159, 94912583, 95401417, 95517517, 95532289, 95640361, 95663761, 95708237, 95992103, 96282569, 96711581, 97069493, 97163797, 97165001, 97283321, 97312819, 97353379, 97518247, 97551143, 97792117, 97864961, 97994641, 98188099, 98240249, 98285017, 98372203, 98451193, 98482651, 98643439, 98701003, 98750609, 98954621, 98977741, 99041179, 99157987, 99196763, 99425279, 99595919, 99778351, 99954053 };
    boolean is_isolated(int x) {
        for (int y : isolated) if (x == y) return true;
        return false;
    }
    public String isReachable(int[] source, int[] target) {
        String answer = "";
        for (int i=0; i<source.length; ++i) {
            if (source[i] == target[i]) { answer += "1"; continue; }
            if (source[i] == 89391959 && target[i] == 89591959) { answer += "1"; continue; }
            if (target[i] == 89391959 && source[i] == 89591959) { answer += "1"; continue; }
            if (is_isolated(source[i]) || is_isolated(target[i])) { answer += "0"; continue; }
            answer += "1";
        }
        return answer;
    }
}

Complexity :
Since we submit hard-coded solution the complexity will be 
O(NM)
N : Number of queries
M = 408 nodes size of isolated[] array