PATHSUMS ,October 2020 cookoff , Unofficial Editorial

editorial
, , ,
1

Div 1 : “CodeChef: Practical coding for everyone”
Div 2 : “CodeChef: Practical coding for everyone”
My solution : “CodeChef: Practical coding for everyone”

Approach:-

Just assign value = 2 , for all even level nodes and value = 1 to all odd level nodes

Proof :

Let consider the path between two nodes whose length is even (>=2)

so what will be the pattern for value -

2 1 2 1 2 1
OR
1 2 1 2 1 2

means if path length is X then “2” occurs X/2 times and “1” also occurs X/2 times

total sum of this path values = (X/2)*2 + (X/2)*1 = (X + X/2) which is not completely divisible by X [path length] (as (n/2)%n !=0 it will be n/2 take n =6 then n/2 = 3 => 3%6 !=0 )

Now let consider the path between two nodes whose length is odd (>=3)

so what will be the pattern for value -

2 1 2 1 2
OR
1 2 1 2 1

means if path length is X then “2” occurs (X+1)/2 times and “1” occurs X/2 times
or “2” occurs X/2 times and “1” occurs (X+1)/2 times and in both case it will not completely divisible by X [ path length ] .

int vis[MAX];
vi adj[MAX];
lli depth[MAX];
void clear(lli n)
{
    loop(i,n+1)
    {
        vis[i]=0;
        adj[i].clear();
        depth[i]=0;
    }
}
void bfs(lli src)
{
    vis[src]=1;
    queue<lli>q;
    q.push(src);
    depth[src]=0;
    while(!q.empty())
    {
        lli u = q.front();q.pop();
        for(auto xt : adj[u])
        {
            if(!vis[xt])
            {
                vis[xt]=1;
                q.push(xt);
                depth[xt] = depth[u]+1;
            }
        }
    }
}

int main(){
fastio
lli t=1;
cin>>t;
while(t--) {
    lli n;
    cin>>n;
       
    loop(i,n-1)
    {
        lli x,y;
        cin>>x>>y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    bfs(1);
    lli a[n+1]={0};
    FOR(i,1,n+1)
    {
        if(depth[i]%2)
        {
            a[i]=1;
        }
        else
            a[i]=2;
    }
    FOR(i,1,n+1)
        cout<<a[i]<<" ";
    cout<<endl;
    clear(n);
  }
return 0;
}
4 Likes
2

To be precise we do a level order traversal on the tree and assign 1 for the odd level and 2 for even (or) assign 2 for the odd level and 1 for even, so here he used bfs to get the level and assign the values accordingly.

1 Like
3

Just do BFS and find depth of each node after that assign 2 and 1 (or 1 and 2) for alternate level nodes.

1 Like
4

instead of finding depth each time, u can pass an array as an argument to ur bfs function and assign the values while you are pushing it in the queue right?

5

Check my code , I did only single time BFS and then it will calculate Depth of each node.

6

oh…k bruh

7

I didn’t understand, if there is a specific pattern to store it in the array and print.
can we directly print
1 2 1 2 1 2…n times ?

8

No , u don’t know whether the node number 2 is on odd level or even level , according to u , node number 2 is always at odd level.

9

I did simple one dfs

1 Like
10

nope you get it wrong, the pattern is you need to assign the opposite parity to the children’s value

1 Like
11

Great Doggo . :grin:

12

How you had observed that pattern I had tried but not able to find out :disappointed_relieved:

13

Take a paper and draw a graph for the first test case. Now assign 1 to each node on the odd level and 2 to each node on even level or vice-versa. Try out every path until you are convinced.

14

just hit and try bro , and also after observing i proved in my copy and coded it . I m unable to solve 4’th one as not observe the specific pattern in 4’th . :frowning_face:

15

A simple BFS won’t work here. You need to do DFS as the assigning of node values depend upon the depth of nodes from the root.
In my case, BFS failed so I went for DFS.

16

i brute forced by assigning values lol

17

yupp bro, I tried so hard for 4th one but no pattern,

1 Like
18

Check my code .

19

OK bro I am thinking in same way but that 1,2,1 idea had not strike in mind i am thinking in term of odd even

1 Like
20

1-2 idea is also odd even

1 Like