SleepyShashwat's blog

By SleepyShashwat, history, 13 days ago, In English

Thank you for participating, and I hope you enjoyed the problems! Once again, we're sorry about the round being unrated.

Also, here are video editorials by BRCode:

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

This problem was set by Anti-Light and prepared by knightron00

Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it
  • +159
  • Vote: I do not like it

»
13 days ago, # |
  Vote: I like it +15 Vote: I do not like it

How to solve the C problem with dfs?

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    for each cell u can find a boolean relationship with the other 4 adjacent cells,for eg. if we say a normal cell is A and a cell which is to be incremented is A' then we have to check for each neighbouring cells, say both are equal (v1=v2) then the condition would be (v1 and v2')or(v2 and v1') as one of them must be incremented, similarly we may check if v1=v2+1 and so on..., what we do next is use the associative and distributive property of these boolean expressions and write them in a form ((a or b) and (c or d)) , which if u are familiar with 2sat problems,this can be solved using 2 dfs (kosaraju's algo or some other scc algo)

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I didn't understand how to convert it into 2-sat. can you explain in more detail? thanks in advance.

      • »
        »
        »
        »
        9 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        for each and every cell a and its neighbour b,there are 3 cases.... 1)b==a,in this case,only one is allowed to increase,so (a xor b),this accounts for 4 edges(i.e; !a->b,!b->a,b->!a,a-!b) in imiplication graph. 2)b==a+1,it is not allowed to increase a and letting b same,so !(a and !b),this accounts for 2 edges(i.e; a->b,!b->!a). 3)b>a+1,no restirction in this case since a,b can increment or stay the same.

        There after,we can assign values to these variables using 2-SAT method.

        my solution

        • »
          »
          »
          »
          »
          9 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you for your explanation! got it.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Pure dfs (I didn't use 2-SAT + SCC)

    98303696

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    oh, I tried and i failed T_T

»
13 days ago, # |
  Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    Happy to hear that!

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I didnt get why we reversing the array in the E problem as we fixing left point then it will automaticlly calculate all possible r ??

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        We don't cover all possible values of r, we stop once the sum crosses a certain value depending on the value of a[l]. Now consider the following testcase

        1 1 1 1 1 1 5

        When l is at position 1, k is 0 (assuming position of LSB to be 0). Start moving r from position 3. At r = 4, the sum between l and r is 2, which is not smaller than 2 ^ (k+1). So we break the loop there itself without counting the subarray [1,7] (the entire array) which is actually a good subarray.

        Now if the array is reversed we'll start at l = 5 and the sum will be less than 2 ^ (k+1) till we reach the end, thus including it in the result

        • »
          »
          »
          »
          »
          12 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          How we got the intution that for particular l we have to iterate till sum less then 2^(k+1) ??

          • »
            »
            »
            »
            »
            »
            12 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            If k is the position of MSB in the maximum of a[l] and a[r], then the value of their xor will always be < 2 ^ (k+1), so it is pointless checking subarrays having their sum >= 2 ^ (k+1)

            • »
              »
              »
              »
              »
              »
              »
              12 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              But in this algo we were checking by setting l and traversing how can we guarantee about r may be at some point sum increase but then after that other point the r has higher msb then sum can fall in between also ?

              • »
                »
                »
                »
                »
                »
                »
                »
                11 days ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                I think that since we are traversing 2 times(once after we reverse) in the first time we think of the bit set in l as max set bit b/w l and r and after reverse we think of bit set in r as max .

»
13 days ago, # |
  Vote: I like it +29 Vote: I do not like it

D was a nice one :)

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please explain D?

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      solution is explained well, I don't sure that I can explain better :)

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      See the video editorial!! It will help !!

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you! I didn't know that. It really helps me!

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Let us understand with example . Suppose $$$n = 5$$$ and array is $$$a_1,a_2,a_3,a_4,a_5$$$ , then do following operations :

      Choose indices 1,2,3 and say $$$b_1 = a_1⊕a_2⊕a_3$$$. Thus $$$a_1,a_2,a_3$$$ will be replaced by $$$b_1$$$.

      Thus resultant array will be $$$b_1,b_1,b_1,a_4,a_5$$$.

      In second operation choose indices 3,4,5 and suppose $$$c_1 = b_1⊕a_4⊕a_5$$$. Thus resultant array will be $$$b_1,b_1,c_1,c_1,c_1$$$ . Now do the third operation by choosing indices (1,2,5) and fourth operation (3,4,5) and finally you will get array $$$c_1,c_1,c_1,c_1,c_1$$$ .

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you for your explanation! I got it.

»
13 days ago, # |
Rev. 2   Vote: I like it +20 Vote: I do not like it

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

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please explain D?

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      Let us assume that N is odd and a window of 1 x 3 that moves on the 1 x N given array. The window starts from i=1 and moves forward by +2 in each step, precisely, the left end moves on the odd position after each step until the rightmost end is at N. So, in general we can observe the pattern with N=7, let, A = [a, b, c, d, e, f, g], then after applying the above operation(move window at i=1,i=3,i=5), you will get the following array B = [x, x, y, y, z, z, z]. So, now we will again apply the above "window" operation from i = N - 2(right end) and move downwards on the odd points until the left end of the window touches i=1. So the final array will be C = [z, z, z, z, z, z, z]. Total number of operations are n/2 + n/2 = n-1 (assumed that n is odd).

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it +18 Vote: I do not like it

        If $$$N$$$ is even then you must think a little more. First it's easy to notice that the xor of the whole array stays the same in all the progress. Then in an correct array with all its elements equal the xor of its elements is 0. So if the xor of its elements it's not equal to 0 then it's impossible. Else you can make the same approach that smit_5300 mentioned above without using the last element. You will end with $$$A = [a,a,a,...,a,b]$$$ (odd number of a and one b). So the xor of the whole array is a xor b and because the xor of the whole array is 0 then a is equal to b and we don't need to make other operations.

        PS:Really like that problem!

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Thank uuuuu!

  • »
    »
    12 days ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    .................................................

»
13 days ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
13 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Good questions

»
13 days ago, # |
  Vote: I like it +21 Vote: I do not like it

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

»
13 days ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

why does my score always still static?

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
13 days ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please explain the editorial of b

  • »
    »
    13 days ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    It says that in order to represent any power of 2 except (2^0) you need at least one duplicate element(except the power itself)

    Say for some subarray we got : 2^1 + 2^3 + 2^4.

    Now in order to equate it to some other non intersecting subarray, we will have to split these powers. Make a simple tree for say 2^4. Where for each child the value is half the parent.

    You will notice to represent 2^4 for any combination of powers of 2 you need to repeat atleast 1 power.

    In the worst case 2^4 = 2^0 + 2^0 + 2^1 + 2^2 + 2^3 (Select only one node from each level of tree and then 2 nodes from the last). Now iff all distinct exponents are present then we cannot split any power of 2 and so we can never equate any subarray in the first place, so answer is NO,

    else YES(Select the any 2 repeating elements, we can do that because of constraint l1<=r1 < l2<=r2).

    I wonder what the solution would have been if the constraints were 1 <= l1 < r1 < l2 < r2 <= n

»
13 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Great Contest, yet unrated imao!xD!!

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

hints for D?? confusing for me

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice problem set.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

problems are soo elegant

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    12 days ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    Since xor of all elements is zero and since you consider first (n-1) in case of even.
    So you will make first (n-1) elements equal to a particular number let that be x.
    Now let us consider xor of all the elements:
    X=x ^ x ^ x... (n-1) times ^A[n].
    we know since n is even n-1 will be odd.
    So x^ x^ x .. (n-1) times will be x.
    X=x^A[n]
    Since we ensured that X must be 0.
    Property={ a^a=0)
    So
    0=x^A[n];
    so A[n]=x;
    so we have proved all the elements are equal to x.

»
12 days ago, # |
  Vote: I like it -26 Vote: I do not like it

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.

»
12 days ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

A great problemset ! Requires creativity & clever observations .

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice problem set.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
12 days ago, # |
  Vote: I like it +11 Vote: I do not like it

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?

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I learnt a lot, good problems SleepyShashwat

»
12 days ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You don't read the entire array, so the next element after breaking becomes $$$n$$$ of the succeeding test case.

»
12 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Such greedy cannot work here. If you find two cells with same value obviously you need to increment one of it. But to decide which one you need to know about the other cells.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try this test case->
    1
    4 4
    1 1 2 3
    1 1 2 3
    1 1 2 3
    1 1 2 3
    There are a lot of issues with your approach. Try and think in terms of parity of element of the matrix, and how it changes
    PS-Also, it is better to give a link to your submission, or atleast mention which problem it is.

»
12 days ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

when will rating will get updated ?

»
11 days ago, # |
  Vote: I like it +3 Vote: I do not like it

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$$$.

Solution
»
11 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    10 days ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Because not directly compare 1+2 and 3, but 2^1+2^2 and 2^3 instead.

»
10 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 days ago, # |
Rev. 2   Vote: I like it +86 Vote: I do not like it

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.

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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?