PATHSUMS - Editorial

editorial
, , , , , ,
13

What does this statement do ?

14

Dude, you can do something like this. It looks easy to me than your approach.
https://www.codechef.com/viewsolution/39005710

15

oh sorry it was a copy paste mistake what I did there was

for(int i=0;i<n-1;i++){
cin>>u>>v;

my code works fine for samples and someother tests which I have created

16

Its correct but only with a little change if you will see carefully you need to assign them in a recursive manner so it will be better if you would use dfs instead of iterated version because the tree is not always supposed to be a chain … My solution
ignore that sieve part that wasnt of much use hope it helps :slight_smile:

1 Like
17

I was trying to solve the problem using 0-1 coloring but it seemed to be failing in some testcases. But when i changed the coloring method to 1-2 keeping rest of the code same all the tc passed. Can anyone explain me a test case where 0-1 strategy might be failing. Thankyou.

18

Hi, I used the same 1-2 coloring approach using bfs but was getting WA. Can anyone look into my code?

https://www.codechef.com/viewsolution/39033786

19

Won’t work. Take a two node tree. Assign any two primes and the sum is even.

20

did u assigned 0 1 as values? that won’t work as Ai is in the range [1,1e5]. hence 0 1 isn’t valid.

21

Oh such a stupid mistake.
Thanks a lot

1 Like
22

simply assign 1 to the root and after that do a dfs search and assign 2 to a node if its parent has value 1 and assign 1 if its parent has value 2.

23

Clear your graph too, after each test case.

1 Like
24

Don’t know what is wrong with this code…simple BFS…

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long int
#define fast_io ios_base::sync_with_stdio(false)
#define endl "\n"
using namespace std;
vector<int>graph[100];
int dis[105] = {0};
int odd=1,even=2;
void bfs(int u, vector<bool>visited, vector<int>&ans)
{
	visited[u]=true;
	queue<int>q;
	q.push(u);
	while (q.size() != 0)
	{
		int current=q.front();
		q.pop();
		
		for(auto it:graph[current])
		{
			if(visited[it]==false)
			{
				visited[it]=true;
				q.push(it);
				if(ans[current]==1)
					ans[it]=2;
				else
					ans[it]=1;
			}

		}
	}
}


int main()
{
	fast_io;
	ll t;
	cin >> t;
	while (t--)
	{
		ll n;
		cin >> n;
		graph[n + 1];


for(int i=0;i<=n;i++)
	graph[i].clear();

		for (int i = 1; i < n; i++)
		{
			int a, b;
			cin >> a >> b;
			graph[a].push_back(b);
			graph[b].push_back(a);
		}

		vector<bool>visited(n , false);

		vector<int>ans(n);
		ans[0] = 1;
		ans[1] = 2;
		bfs(1, visited, ans);
		for(int i=1;i<=n;i++)
			cout<<ans[i]<<" ";
		cout<<endl;








	}




	return 0;
}
25

The path not necessarily starts or ends at a leaf node. Take 1->2->3 as an example. You assign P to 1 and 2, and 2P to 3. 1->2 is also a valid path, whose length is 2 and sum is 2P which is divisible by 2.

26

Found the issue, I missed to clear my map after every test case.

27

Here is my dfs approach Solution link:- CodeChef: Practical coding for everyone

28

Yea it worked thanks
A small mistake during costed a lot :laughing:

1 Like
29

@ibhaskarbisht make vector ans and vis of size n+1, your code will get accepted

30

Change your vector visited and ans size from n to (n+1) :slight_smile:

31

Such a nice question

32

I did same but got WA.