SleepyShashwat's blog

By SleepyShashwat, history, 2 years ago,

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:

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

• +167

| Write comment?
 » 2 years ago, # |   +15 How to solve the C problem with dfs?
•  » » 2 years ago, # ^ |   +8 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)
•  » » 2 years ago, # ^ |   +5 Pure dfs (I didn't use 2-SAT + SCC)98303696
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 Great solution! What would be its time complexity?
•  » » » 2 years ago, # ^ |   0 Why it is correct ?
•  » » » 2 years ago, # ^ |   +31 Hacked(the time complexity on the test case i found is $O(n^2m^2)$).
•  » » 2 years ago, # ^ |   0 oh, I tried and i failed T_T
 » 2 years ago, # |   +6 Nice Problem Set :). Got to learn few new things.
•  » » 2 years ago, # ^ |   +35 Happy to hear that!
 » 2 years ago, # |   +29 D was a nice one :)
•  » » 2 years ago, # ^ |   0 Could you please explain D?
•  » » » 2 years ago, # ^ |   0 solution is explained well, I don't sure that I can explain better :)
•  » » » » 2 years ago, # ^ |   0 already understood. Thank you!
•  » » » 2 years ago, # ^ |   0 See the video editorial!! It will help !!
•  » » » » 2 years ago, # ^ |   0 Thank you! I didn't know that. It really helps me!
•  » » » 2 years ago, # ^ |   0 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$ .
•  » » » » 2 years ago, # ^ |   0 Thank you for your explanation! I got it.
 » 2 years ago, # | ← Rev. 2 →   +20 D was very good (well, every problem was very good actually). Looking forward to your next rounds!
•  » » 2 years ago, # ^ |   0 Could you please explain D?
•  » » » 2 years ago, # ^ |   +17 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).
•  » » » » 2 years ago, # ^ |   +18 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 TheBigBool 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!
•  » » » » » 2 years ago, # ^ |   0 I like it either!
•  » » » » » 8 months ago, # ^ |   0 Thanks Theo830 And The BigBool you both explain intuition really very well :) that helps me to understand intuition behind the problem
•  » » » » 2 years ago, # ^ |   +3 Thank uuuuu!
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 .................................................
 » 2 years ago, # |   +8 Is there anyone who solved problem C using 2SAT method?
 » 2 years ago, # | ← Rev. 2 →   0 Good questions
 » 2 years ago, # |   +21 C is so elegant, I can't believe I missed that observation
•  » » 2 years ago, # ^ |   0 exactly, tried everything except the most basic solution
 » 2 years ago, # |   +3 Nice editorial SleepyShashwat. No BS, straight to the point and easily understandable.
 » 2 years ago, # |   0 Well, I came up with observation for C just before I enter here :(
 » 2 years ago, # |   +6 Such a good problemset, but it's quite a pity that it unrated :-(
 » 2 years ago, # |   0 problems are soo elegant
 » 2 years ago, # |   0 I have a doubt on C. I am not sure of my solutions time complexity. Could anyone please prove it or hack it. 98306400
 » 2 years ago, # |   0 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.
•  » » 2 years ago, # ^ | ← Rev. 3 →   +3 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.
•  » » » 2 years ago, # ^ |   0 Ohh yes understood. Thank you so much
 » 2 years ago, # | ← Rev. 2 →   +3 A great problemset ! Requires creativity & clever observations .
 » 2 years ago, # |   0 Nice problem set.
 » 2 years ago, # |   0 The problem set was really nice! Looking forward to more contests from you peeps! :)
 » 2 years ago, # |   +11 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?
 » 2 years ago, # | ← Rev. 5 →   0 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 v(n); map mp; int flag = 0; for(int i=0; i>v[i]; if(mp.find(v[i])!=mp.end()){ flag=1; cout<<"YES"<
•  » » 2 years ago, # ^ |   +1 You don't read the entire array, so the next element after breaking becomes $n$ of the succeeding test case.
 » 2 years ago, # | ← Rev. 3 →   0 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
•  » » 2 years ago, # ^ |   0 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.
 » 2 years ago, # | ← Rev. 2 →   +1 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.
 » 2 years ago, # |   0 when will rating will get updated ?
•  » » 2 years ago, # ^ |   +3 Never
 » 2 years ago, # |   +3 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$. SolutionBasically output any arithmetic progression having even difference. This works because subarray of any AP is an AP and sum of an AP is given by $(\text{first term} + \text{last term})*(\text{length of AP})/2$. As $\text{first term} + \text{last term}$ is even, the sum is divisible by its length.
 » 2 years ago, # | ← Rev. 2 →   0 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.
 » 2 years ago, # | ← Rev. 2 →   +94 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 years ago, # ^ |   +29 Ali_Tavakoli orz
 » 2 years ago, # |   0 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?
•  » » 2 years ago, # ^ |   0 $4 \oplus 4 \oplus 4 = 4$, not $0$.
 » 2 years ago, # |   0 Can you help me explain Problem B?
•  » » 2 years ago, # ^ |   0 Sure, which part exactly?
•  » » » 2 months ago, # ^ | ← Rev. 3 →   0 please ignore this comment
 » 20 months ago, # |   0 I am not getting problem D.
 » 6 months ago, # |   +3 Where can i practice these puzzle problems like 1438C — Engineer Artem? and why are the tags at problem C so weird? constructive algo + 2-SAT + FFT + chinese theorem + flows !!
 » 2 months ago, # |   0 For problem B what if n == 3 b = {1,1,3} there is no solution please tell me if i am right or wrong if wrong tell why