How to solve the C problem with dfs?

Nice Problem Set :). Got to learn few new things.

D was a nice one :)

D was very good (well, every problem was very good actually). Looking forward to your next rounds!

Is there anyone who solved problem C using 2SAT method?

I did so good and was about to submit my answer for C when I got that "Unrated" notification, it broke my heart lol

Good questions

C is so elegant, I can't believe I missed that observation

Nice editorial SleepyShashwat. No BS, straight to the point and easily understandable.

why does my score always still static?

Well, I came up with observation for C just before I enter here :(

Such a good problemset, but it's quite a pity that it unrated :-(

can anyone please explain the editorial of b

Great Contest, yet unrated imao!xD!!

hints for D?? confusing for me

Nice problem set.

problems are soo elegant

I have a doubt on C. I am not sure of my solutions time complexity. Could anyone please prove it or hack it. 98306400

I need proof for a magical part as suggested in an editorial in Problem-D. How the last element will automatically be the same by applying operations for the first n-1 elements.

Can someone give a testcase where below code for B fails?

#include <iostream>
 
using namespace std;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {-1, 1, 0, 0};
int m, n;
long long arr[101][101];
 
bool check(int x, int y, long long k) {
	if( x < 0 || y < 0 || x >= n || y >= m) return true;
	for(int i = 0; i < 4; i ++) {
		int a = x + dx[i];
		int b = y + dy[i];
		
		if(a < 0 || b < 0 || a >= n || b >= m) continue;
		if(arr[a][b] == k) return false;
	}
	return true;
} 
int main() {
	int t;
	cin >> t;
	while(t --) {
		cin >> n >> m;
		
		
		for(int i = 0; i < n; i ++) {
			for(int j = 0; j < m; j ++) {
				cin >> arr[i][j];
			}
		}
		
		for(int i = 0; i < n; i ++) {
			for(int j = 0; j < m; j ++) {
				if(!check(i,j,arr[i][j])) {
					if(check(i, j,  arr[i][j] + 1)) {
						arr[i][j] += 1;
					} else if( i >= 1 && arr[i - 1][j] == arr[i][j] && check(i - 1, j,  arr[i][j] + 1)) {
						arr[i - 1][j] += 1;
					} else if(j >= 1 && arr[i][j - 1] == arr[i][j] && check(i, j - 1,  arr[i][j] + 1)) {
						arr[i][j - 1] += 1;
					} else if(i < n - 1 && arr[i + 1][j] == arr[i][j] && check(i + 1, j,  arr[i][j] + 1)) {
						arr[i + 1][j] += 1;
					} else if(j < n - 1 && arr[i][j + 1] == arr[i][j] && check(i, j + 1,  arr[i][j] + 1)) {
						arr[i][j + 1] += 1;
					}  	
 				}
			}
		}
		for(int i = 0; i < n; i ++) {
			for(int j = 0; j < m; j ++) {
					cout << arr[i][j] << " ";
			}
			cout << endl;
			
		}
	}
	return 0;
}

It seems to work for all tests I did.

A great problemset ! Requires creativity & clever observations .

Nice problem set.

I saw solutions of some people for the problem C. I have no idea what the heck they are doing, my O(n^2) solution works great for that problem. Can anyone tell me why to write such a long solution for an easy problem like this?

The problem set was really nice! Looking forward to more contests from you peeps! :)

Is there any math to know how reasonably sure we can be that we have the 2 children of the root after $$$q$$$ queries in problem F? Is 420 deliberately chosen or is it just a meme number?

I learnt a lot, good problems SleepyShashwat

In problem B I am using map to check whether there are duplicates but getting runtime error, pls tell me why is it so?

int main(){
    int tc;
    cin>>tc;
    while(tc--)
    {
        int n;
        cin>>n;
        vector<int> v(n);
        map<int,int> mp;
        int flag = 0;
        for(int i=0; i<n; ++i){
            cin>>v[i];
            if(mp.find(v[i])!=mp.end()){
                flag=1;
                cout<<"YES"<<endl;
                break;
            }
            mp[v[i]]++;
        }
        if(flag==0)
            cout<<"NO"<<endl;
   }
    return 0;
}

https://codeforces.com/contest/1438/submission/98367651

dont know why my solution is not passing test case 2 for problem C :( can anyone help??thanks soltn :https://pastebin.ubuntu.com/p/m7rG5Rkj5y/ UPD:i got my mistake

Can someone help me, what is wrong with this solution: https://ideone.com/i5dfs2

I have a different approach for problem E.

Let's denote psum[i] as the sum of A[j], for all 1 <= j <= i.

First, we can notice that a + b >= a ^ b. So, we can compute all pairs of indexes l and r, such that A[l] + A[r] >= psum[r-1] — psum[l]. There are at most nlogn of this pairs, because for a fixed l, the valid r's need to be at least two times bigger than the previous one, so there are at most logn for a fixed l, and the worst case is something like 1, 1, 1, 1, 2, 4, 8, ...

Then we can find all such pairs in the following way. First, with simple transformations we can show that a pair is valid if A[r] — psum[r-1] >= -A[l] — psum[l]. Then we can maintain a set of pairs (-A[l]-psum[l],l) and iterate over it while the condition remains true, and for each of these pairs we can check if A[l] ^ A[r] = psum[r-1] — psum[l] and count the number of good pairs.

when will rating will get updated ?

Here's a bonus problem for A: What if the numbers have to be pairwise distinct? Take $$$n < 1000$$$ and the numbers you output must be less than $$$5000$$$.

In problem B, for the test case array-{1 2 3}, why is the answer NO, as we have {1,2} and {3} as subarrays having same sum.

Could someone explain Pro. F about the std answer "Let c1 and c2 be the two most frequently returned nodes — these are the children of the root. ". Thanks a lot.

I wonder why this sentence is true. Problem statements only defines how "u,v,w" return when w is the root of the tree, but does not define how to return when w is not the root.

There are 2^18-1=262143 possible roots. When we randomly ask 420 times, almost all the asks is ineffective, I think.

I kind of understood the approach for problem D but still, I am not able to code it. Can some help me with this?

so there's a funny and unproven solution for task C by Ali_Tavakoli :

for every pair of adjacent elements, we check whether they are equal or not, if they are equal we randomly change one of them which hasn't been changed yet. After we check all the pairs, we check whether the matrix is good or not, if the matrix is good then we have an answer and we are done, if not we will repeat this process until we find a good matrix. he has no proof for this solution but by doing at most 400 repetitions of the algorithm above, he managed to pass the sys tests.

Stupid comment ahead I think i might have misunderstood the question "1438D — Powerful Ksenia". So, please help me out here. Let's say the array is 1 2 3 4 Now, the operations are as follows: 1 2 3 4 (initial array) -> 0 0 0 4 -> 0 4 4 4 -> 0 0 0 0. Number of operations = 3, and all array elements are equal. After looking at the editorial, XOR of the above array is 4 and the array length is even. So, answer is "NO". What am i missing?

Can you help me explain Problem B?

can we solve E using trie?