PATHSUMS - Editorial

PROBLEM LINK:

Practice
Contest

Setter: Shahjalal Shohag
Tester: Rahul Dugar
Editorialist: Ishmeet Singh Saggu

DIFFICULTY:

Easy

PREREQUISITES:

Ad-hoc and DFS/BFS

PROBLEM:

You are given a tree with N nodes. You have to assign each node i an integer A_i such that :

  • 1 \leq A_i \leq 10^{5}.
  • For each simple path containing 2 or more nodes, let’s denote the set of nodes in this path by S. Then \sum_{v \epsilon S} A_{v} is not divisible by|S|

EXPLANATION:

So we have to make the sum of the values of the nodes on the simple path non-divisible by the number of nodes on the path.

For simplicity let us consider a simple path and represent the sum of the values of the nodes as Sum and the number of nodes as Len. So we can represent Sum = p*Len + r, where p and r are integers and r < Len, so we have to assign values to the nodes such that for any simple path r is non-zero. One way to do this is to root the tree at any node and assign value x to all nodes at even depth and value x+1 to all nodes at odd depth, where x lies in the range [1, 10^5)). Now let us see what will happen when we do the above assignment. If we choose a path with the number of nodes = Len, some nodes will contribute x and some nodes will contribute x+1 so the Sum = Len*x + y, where y is the number of nodes which have value x+1 and note that for any path with the number of nodes greater than or equal to 2, y will always be less than the number of nodes in the path (Floor( \frac{Len}{2} ) or Ceil( \frac{Len}{2} ) to be exact as values of the nodes in the path will take value x and x+1 in alternation) , which will make the Sum non-divisible by the Len leaving the remainder y.

One example will be to root the tree at node 1 and we can assign value 1 to all nodes at even depth and value 2 to all nodes at odd depth.

TIME COMPLEXITY:

  • Time complexity per test case is O(N).

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
 
const int N = 105;
 
vector<int> g[N];
int d[N];
void dfs(int u, int p = 0) {
  d[u] = d[p] ^ 1;
  for (auto v: g[u]) {
    if (v != p) {
      dfs(v, u);
    }
  }
}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  assert(1 <= t && t <= 200);
  while (t--) {
    int n; cin >> n;
    assert(2 <= n && n <= 100);
    for (int i = 1; i < n; i++) {
      int u, v; cin >> u >> v;
      g[u].push_back(v);
      g[v].push_back(u);
    }
    memset(d, 0, sizeof d);
    dfs(1);
    for (int i = 1; i <= n; i++) {
      cout << d[i] + 1 << ' ';
    }
    cout << '\n';
    for (int i = 1; i <= n; i++) {
      g[i].clear();
    }
  }
  return 0;
} 
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
const int mod=998244353;
//const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
 
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int powm(int a, int b) {
	int res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
 
 
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
 
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
 
vi gra[105];
int total=0;
int ans[105];
void dfs(int fr, int at) {
	total++;
	ans[at]=ans[fr]^3;
	for(int i:gra[at])
		if(i!=fr)
			dfs(at,i);
}
void solve() {
	total=0;
	int n=readIntLn(1,100);
	fr(i,1,n)
		gra[i].clear();
	rep(i,1,n) {
		int u=readIntSp(1,n);
		int v=readIntLn(1,n);
		assert(u!=v);
		gra[u].pb(v);
		gra[v].pb(u);
	}
	ans[1]=1;
	dfs(1,1);
	assert(total==n);
	fr(i,1,n)
		cout<<ans[i]<<" ";
	cout<<endl;
}
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(8);
	int t=1;
//	cin>>t;
	t=readIntLn(1,200);
	fr(i,1,t) {
		solve();
	}
	assert(getchar()==EOF);
#ifdef rd
	cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
	return 0;
}
 
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
 
vector<vector<int>> graph;
vector<int> value;
 
void dfs(int node, int parent, int d) {
	if(d % 2) value[node] = 2;
	else value[node] = 1;
	for(auto i : graph[node]) {
		if(i == parent) continue;
		dfs(i, node, d+1);
	}
}
 
void Solve() {
	int N;
	cin >> N;
	graph.clear();
	graph.resize(N+1);
	value.assign(N+1, 0);
	for(int i = 1; i < N; i ++) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	dfs(1, -1, 1);
	for(int i = 1; i <= N; i ++) {
		cout << value[i] << " ";
	}
	cout << '\n';
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int test_case = 1;
	cin >> test_case;
	for(int i = 1; i <= test_case; i ++) {
		Solve();
	}
	
	return 0;
} 

VIDEO EDITORIAL:

Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed. :smile:

1 Like

This post was flagged by the community and is temporarily hidden.

Recovered losses from Long Challenge. Me too XD

1 Like

Could someone please tell me where I am going wrong ?
I am taking the following approach.
I assign a 5 digit prime number P to all non-leaf nodes and 2*P to leaf nodes.
My theory is that, along any path of depth d nodes the sum will be (d+1)*P --> dP+P which can never be divisible by d. But this approach gives me wrong answer.
What is wrong with this approach ?

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

Simple BFS . Assigning 1 and 2 alternatively level wise

8 Likes

I’ve used 1-2 colouring approach. but it was showing the wrong answer. please have a look at my solution. let me know what went wrong.

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

What about storing 100 prime numbers greater than 100, which can be obtained from net, and printing it , hope it passes all test cases.(based on input conditions)

I’ve also used 1-2 coloring approach but it gives WA

vector<vector> adj(101);
vector color(101,0);
vector vis(101,0);
void dfs(int u,int par,int c){
	 if(vis[u])return;
	vis[u]=1;
	color[u]=c;
	int x;
	if(c==1)x=2;
	else x=1;
	for(int i:adj[u]){
		if(i!=par)dfs(i,u,x);
	}
}
signed main(){
    setIO("");
    int t;cin>>t;
    while(t--){
    	int n;cin>>n;
    	adj.clear();
    	vis.clear();
    	color.clear();
    	for(int i=0;i< n-1;i++){
                int u,v;cin>>u>>v;
    		adj[u].pb(v);
    		adj[v].pb(u);
    	}
    	dfs(1,-1,1);
    	for(int i=1;i<=n;i++)cout<<color[i]<<" ";
    	cout<<"\n";
    }
    return 0;
}

please let me know what was wrong with my code

Can anyone say me where i am wrong see only solve and dfs functions
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define endl “\n”
#define mod 1000000007
// #define mod 1
// vectorv1,v2;
// int dp[10001];
// int ans=0;
// map<int,int>m;
// set<pair<int,int>>s;
vectoradj[101];
vectorvis(101,false);
int dis[101];
// string s1,s2;
int power(int x,int y)
{ int temp;
if(y==0)
return 1;
temp=power(x,y/2)%mod;
if(y%2==0)
return (temp%modtemp%mod)%mod;
else
return ((x%mod)
((temp%mod*temp%mod)%mod))%mod;
}
void dfs(int n,int f)
{ vis[n]=true;
if(f==0)
dis[n]=2;
else
dis[n]=1;
for(auto i:adj[n])
{ if(vis[i]==true)
continue;
if(f==0)
dfs(i,1);
else
dfs(i,0);

}
}
void solve()
{
int n;
cin>>n;
for(int i=1;i<=100;i++)
{
adj[i].clear();
vis[i]=false;
}
for(int i=1;i<=n;i++)
{
int a,b;
cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(1,1);
for(int i=1;i<=n;i++)
cout<<dis[i]<<" ";
cout<<endl;
}

signed main()
{ ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen(“input1.txt”,“r”,stdin);
freopen(“output1.txt”,“w”,stdout);
#endif

int t;
cin>>t;
//t=1;
for(int i=1;i<=t;i++)
{
solve();
}

return 0;

}

This might work, but chances are very very thin that it will be AC. Let’s say that it works for one test case, somehow, but it very likey to fail on others. sum of primes does not imply prime. very often you will find the opposite.

Hello, i participated in yesterday’s Cook off challenge. I have a doubt regarding this question (PATHSUMS to be exact) and I’d really appreciate it if someone helped me out.

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

This is my solution, as you can see I’m getting WA. I checked the editorial, i have used the same approach they have used( assigning a value of 1 to a parent node and 2 to its neighbors and so on), just a different way of representing the tree/graph (In the video they have used adjacency list, I on the other hand have used a vector of pairs)

Example Input :
2
7
1 2
4 6
3 5
1 4
7 5
5 1
3
1 2
2 3
Output that I’m getting :
1 2 1 2 2 1 1
1 2 1

I have stored the tree in a vector of pairs. then initialized a countArr of size n by -1 and two more vectors names parent and descendant. Initially i pushed 1 to the parent arr and initialized countArr[0] to 1. then checked for all the descendants for that parent and made the countArr of that descendant to 2, then checked for their descendants and so on till there are no nodes left.

Thank You.

What does this statement do ?

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

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

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

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.

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

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

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.

Oh such a stupid mistake.
Thanks a lot

1 Like