### ZhouShang2003's blog

By ZhouShang2003, 7 days ago,

Hint
Solution
Code

Hint
Solution
Code

Hint 1
Hint 2
Solution
Code

Hint
Solution
Code

Hint
Solution
Code

Hint
Solution
Code

Hint 1
Hint 2
Solution
Code

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution
Code

## 1991I — Grid Game

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Hint 7
Hint 8
Solution
Code
• +164

 » 7 days ago, # |   +75 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } so zengminghao told me during the round that problem I can be found at https://www.brand.site.co.il/riddles/200802q.htmlFortunately, it seems it has affected almost no one. Sorry for this unfortunate coincidence though :/
 » 7 days ago, # |   -92 D is nice
•  » » 7 days ago, # ^ |   +204 Worst problem I've ever seen.
•  » » 7 days ago, # ^ |   +13 D feels more like a math problem rather than an algorithmic one. I don't think it's a good problem. :(
•  » » » 7 days ago, # ^ |   +21 Why?
•  » » » 7 days ago, # ^ |   +27 It's not mathy at all
•  » » » 6 days ago, # ^ |   +11 It’s not something mathy it’s just a puzzle.
•  » » » 6 days ago, # ^ |   0 for problem D for the test case where n = 4, shouldn't the answer be 2 because if we connect (1 with 2,3,4) we only need 2 colors, c1 for 1 and c2 for ( 2,3,4 ) each as they are connected to 1 and not with others.Please correct me if I'm wrong.
•  » » » » 6 days ago, # ^ |   0 $3$ and $4$ are also connected, as $3 = 11_2, 4 = 100_2, 11_2 \oplus 100_2 = 111_2 = 7$, which is prime.
•  » » 6 days ago, # ^ | ← Rev. 2 →   +2 D was so annoying, I spent literally the last 2/3 of the contest trying to make an efficient checker if a xor b is prime, but I missed the easy solution for x>=6 (due to the 4 colors theorem in math or smth like that).
•  » » » 6 days ago, # ^ |   +19 I didn't need a mathy theorem. All primes except 2 are odd, so there will only be edges between odd and even numbers so we can color odd and even in different colors, however the xor 2 will make an edge between numbers of same parity. We can build a graph for only odd numbers and one for only even numbers sith edges of xor 2 and color them like a bipartite graph
•  » » » » 6 days ago, # ^ |   0 can you explain little more. I get till you have even and odd separately and edges between even even and odd odd. But how to handle even — odd edges ?
•  » » » » » 6 days ago, # ^ |   0 Just color odd numbers with colors 1-2 , and even numbers with 3-4. This way there will never be two connected nodes such that one of them is odd and the other is even with the same color.
•  » » » 6 days ago, # ^ |   +6 4 color theorem doesn't apply here. Consider $K_5$ where the chromatic number is 5.
•  » » 6 days ago, # ^ |   -8 D was like Goodbye 2023, u either saw the pattern or cried
•  » » » 4 days ago, # ^ |   0 Downvoters are the ones who cried lol
•  » » 2 days ago, # ^ |   -8 I believe anyone can't get the solution unless you know the four color theorem :(
•  » » » 2 days ago, # ^ |   0 Your belief is false
 » 7 days ago, # |   +181 imo, D wasn't so good
•  » » 7 days ago, # ^ |   +30 D is going on bullet point 1 of my suicide note
•  » » » 7 days ago, # ^ | ← Rev. 2 →   +28 I came to that conclusion of minimum number of colors being 4 in a more rigorous way and paid dearly for it by being unable to implement it.I had this idea, let edges between $a$ and $b$ have the number $XOR(a, b)$ being a prime number say $p_1$. then let's take $3$ numbers $a, b, c$ where $b$ and $c$ have edges with $a$.then if $a$ and $b$ have edge with value $p_1$ and $a$ and $c$ have edge with value $p_2$ (and none of $p_1$ or $p_2$ is 2)then the associated edge number between $b$ and $c$ must be $XOR(p_1, p_2)$ but both of them are odd. so this $XOR$ must be even or perhaps $2$! if $XOR(p_1, p_2)=2$ and $XOR(a, d) = 2$; then $XOR(p_1, 2) = p_2$ and $XOR(p_2, 2) = p_1$ which implies that all $a, b, c, d$ are connected strongly and must have different colors. There can be no higher form of "strong" connection. (I assume it's trivial by now).I was first thinking about pruning a DFS/BFS like thing. I thought these $p_1$ and $p_2$ must be twin primes (ending with 01 and 11 in binary). Wrote a program to see how many such primes are and found they were less than 1400 till 200000, also did a bunch of weird stuff. but ultimately failed to do the thing.
•  » » » » 7 days ago, # ^ |   +20 I also tried so so many complex things. Actually, I reached conclusion that for n = 2 * 1e5, we need at maximum 36 colors, if we colour the graph greedily. And then implemented completely different thing. tried multiple appraoches, but all failed.
•  » » » » 7 days ago, # ^ | ← Rev. 3 →   +72 $K_4$ appears as a subgraph for $n \geq 6$ as $(1,3,4,6)$ is completely rigorous...
•  » » » » » 7 days ago, # ^ | ← Rev. 2 →   +13 My comment was partially supposed to be a rant, (I understand $(1, 3, 4, 6)$ is $K_4$) Perhaps I focused too much on proving it without assuming it. Had I assumed and then validated my assumption, I could have reached the solution.Edit: Perhaps rigor is not the word I should have used. but you get what I wanted to say, I just meant proving it without assuming it. (which I understand, is in no way more complete or anything).
•  » » » » » 7 days ago, # ^ | ← Rev. 2 →   +1 Also you ultimately prove your bound of $4$ by giving a valid construction. saying that $K_4$ appears as a sub graph for $n>5$ just tells that the number of colors cannot be less than $4$. (for $n>5$)you prove that it is in-fact, $4$, by providing a valid construction. (Just putting it here so that others don't confuse this statement with a completely rigorous proof).
•  » » » » 6 days ago, # ^ |   0 I’ve got the same idea.
•  » » 6 days ago, # ^ |   0 D was like Goodbye 2023, u either saw the pattern or cried
 » 7 days ago, # | ← Rev. 2 →   +19 If you're wondering about about the connection between XOR and modulo 4, you can upsolve CF15C : Industrial NimUpdate: I also created a video and practice contest on this idea.
 » 7 days ago, # |   +1 quite a few constructives
•  » » 7 days ago, # ^ | ← Rev. 3 →   -50 constructiveforcesedit: A master copy pasted the exact same comment from me and got +38. What are the downvotes for??
•  » » » 6 days ago, # ^ |   0 so, you confirm that you just copy-pasted it and expect upvotes
•  » » » » 6 days ago, # ^ |   0 I posted first.
•  » » » 6 days ago, # ^ |   -7 ratism?
•  » » » 6 days ago, # ^ |   0 Maybe if you didn't edit your comment and whine about receiving downvotes, your comment would be in the green now
 » 7 days ago, # |   +24 Probably my worst contest so far, I knew what to do but had some errors. Might need to take a step back and re-eval my approaches
 » 7 days ago, # |   +24 Problem E is so similar to this Problem.
 » 7 days ago, # |   +10 I can't note that $4\mid \left(a\oplus (a+4k)\right)$. So sad.
•  » » 7 days ago, # ^ |   0 Why does 4∣(a xor (a+4k))? Is there an easy way to see this?
•  » » » 7 days ago, # ^ |   +1 The last two bits of a and a + 4k are the same. So the last two bits of (a xor a+4k) are 0, which is the same as being divisible by 4.
•  » » 6 days ago, # ^ |   0 Maybe noting this instead is better: The least significant bit of a — b and a ^ b are the same. So their divisibility by a power of 2 is always the same.
 » 7 days ago, # |   +38 I can easily solve problems of E and F, but I struggled with problem D for a long time before coming up with a solution
 » 7 days ago, # | ← Rev. 2 →   -8 B can be solved like this also ~~~~~void Solve() { int n; cin >> n; vi a(n-1); cin >> a; vi ans; ans.pb(a[0]); for(int i = 1; i < n-1; ++i) { int num = a[i] | a[i-1]; if((ans.back() & num) != a[i-1]) { cout << -1 << nl; return ; } ans.pb(num); } ans.pb(a[n-2]); cout << ans << nl;}~~~~~
 » 7 days ago, # | ← Rev. 2 →   +8 Why is the title of problem C "Maximize the Last Element"? Shouldn't it be "Absolute Zero"?UPD: Changed.
 » 7 days ago, # |   +76 A round full of ARC&AGC problems. :)
•  » » 7 days ago, # ^ |   -25 F could maybe be AGC A so I struggle to understand you since 3 problems don't make a full round. Is it sarcasm?
•  » » » 7 days ago, # ^ |   +96 F is too ugly to be in AGC.
•  » » » » 6 days ago, # ^ |   0 Well, I meaned all the problems are very tricky as ARC&AGC problems. Of course they cannot form a full AGC round, but forming an ARC round is possible.
 » 7 days ago, # | ← Rev. 4 →   +4 Alternative solution for C (for the "YES" case):Until all values become zero, do this for each iteration: Get the minimum and maximum of the current array. Change the values of the array with x = (maximum+minimum) / 2; At each iteration the value of (maximum-minimum) reduces by a factor of 2. So we will achieve the desired result in at most ceil(log(maximum-minimum)) operations.
•  » » 6 days ago, # ^ |   0 Very cool, much more intuitive. I like it.
•  » » 4 days ago, # ^ |   0 I did same sort array, subtracting all elements with the mean of the first and last element and sorting again Repeat the process 40 times if last element =0 Print YES else NO
 » 7 days ago, # |   +17 Enjoyed the round a lot, especially D and E are great. Thanks to coordinators, authors and testers!
 » 7 days ago, # |   +46 Human intelligence round
•  » » 6 days ago, # ^ |   +24 I think G is very Tang (I don't know how to say it in English?
 » 7 days ago, # |   +7 D should have come after E I swear. I almost had E even though I only spent the last 30 mins on it, just didn't have time to get color assignment bugs sorted :(
 » 7 days ago, # |   +52 No evaluation of good or bad but problem D strikes me as utterly absurd.
•  » » 7 days ago, # ^ |   0 I think it's a perfect example of the current meta, where the first 3-4 problems are discrete math puzzles that are trivial to implement and only after them you get to the actual programming problems. Also not sure if this is good or bad
 » 7 days ago, # |   -33 D is a good problem, I like it very much!
 » 7 days ago, # | ← Rev. 2 →   0 For any unselected sticks between the chosen sticks, if there exists a stick to its left and a stick to its right that belongs to the same triangle, we can replace the rightmost stick of this triangle with the unselected stick.This is incorrect. Let's consider sticks 2, 4, 10, 11 and select non-consecutive 2, 10 and 11. Then we can't replace rightmost 11 with unselected 4 because 2 + 4 < 10. I think correct proof here should be something like: if we consider our triangle as two connected intervals left and right ([2;10] and [10;11]), then if the unselected stick is in the left interval (4 is in [2;10]) then we can replace the leftmost stick of the triangle with it, otherwise we can replace the rightmost.
•  » » 7 days ago, # ^ |   +3 leftmost will always work actually
 » 7 days ago, # |   +30 Constructive Forces.
 » 7 days ago, # | ← Rev. 3 →   0 WA - E#include using namespace std; #define ll long long #define pb push_back #define all(x) x.begin(),x.end() #define FastIO ios::sync_with_stdio(0);cin.tie(0); cout.tie(0); const ll N= 1e5+5; ll val[N]; bool vis[N], chk; vector even,odd; vector adj[N]; void dfs(ll u){ vis[u]= 1; if(val[u]==0) even.pb(u); else odd.pb(u); for(ll v: adj[u]){ if(vis[v]){ if(val[u]==val[v]) chk=0; continue; } if(val[u]==0) val[v]= 1; else val[v]= 0; dfs(v); } } int main(){ FastIO; ll T=1; cin>>T; while(T--){ ll n,m; cin>>n>>m; for(ll i=1;i<=n;i++){ adj[i].clear(); val[i]= 0; vis[i]= 0; } odd.clear(); even.clear(); for(ll i=0;i>x>>y; adj[x].pb(y); adj[y].pb(x); } // val[1]= 0; chk=1; // dfs(1); for(ll i=1;i<=n;i++){ if(!vis[i]){ val[i]= 0; dfs(i); } } // for(auto it: odd) cout<>x>>y; } } else{ cout<<"Bob"<>x>>y; if((x==1 || y==1) && oo
•  » » 7 days ago, # ^ | ← Rev. 2 →   0 I also have WA, can you please help why? edit: got it, thankyou!
 » 7 days ago, # |   +9 anyone tried colouring graph greedily in the problem D ???
•  » » 7 days ago, # ^ |   +13 yeah, when you do that it makes a weird pattern: pattern1 2 2 3 1 4 4 3 1 2 2 3 1 4 4 3 1 5 5 3 1 6 6 3 1 5 5 3 1 6 6 3 1 5 5 3 1 6 6 3 1 5 5 3 1 6 6 3 1 2 2 3 1 4 4 3 1 2 2 3 1 4 4 3 1 4 4 3 1 2 2 3 1 4 4 3 1 2 2 3 1 6 6 3 1 5 5 3 1 6 6 3 1 5 5 3 1 6 6 3
•  » » » 7 days ago, # ^ |   +11 been there, and it touches 36, at n = 2054... and then we don't need any more colour than 36 till n = 2 * 1e5.
 » 7 days ago, # |   0 Problem C Video Editorial https://youtu.be/wsD3l8J1Hog
 » 7 days ago, # |   +18 G killed me, maybe guessing that the construction is not that hard will help next time
 » 7 days ago, # |   +4 In H, it's possible to get AC without using FFT or bitset operations to find winning/good positions. Just generate all primes <= 2*10^5, find out if they're winning or losing, and sum every pair of losing primes (to find winning positions) and every pair of winning primes (for good positions).
 » 7 days ago, # |   0 can some body explain E and F? in E how it is biparitie and F would'nt it will be tle if for n queries there are there is multiple for loops ?plz explain
 » 7 days ago, # |   0 My another solution for $C$:Note $k$ is the maximum integer such that $2^k \le max(a_i)$. I subtract $x=2^k-1$ from all the numbers. In most cases, the highest position will drop. But there is one exception: $max(a_i)=2^{k+1}-1$. In this case, I will perform an additional operation — randomly select a number between $[1,2^k-1]$.It looks wrong in the worst case. But idk if it is hackable.https://codeforces.com/contest/1991/submission/273218080
 » 7 days ago, # | ← Rev. 2 →   0 I tried a long ahh time, but can someone tell me how is this wrong for problem E. Let alone out of bounds error because theres no way thats possiblehttps://codeforces.com/contest/1991/submission/273238586Edit: I found out, when clearing my adj list, i was clearing from 0 to n-1 instead of 1 to n :((Atleast I'm happy i wasnt wrong
 » 7 days ago, # |   +17 D: The sample says the answer is $4$ if $n=6$. So let's guess, in the general cases the answer is $4$ <- This is just a riddle.I couldn't find any rules yet, so tried around $n=20$ with Chromatic Number. Then I said the answer is $4$, so starting to consider construct $4$-coloring.I think it's somewhat natural, still it's a mascle approach.
 » 7 days ago, # |   +24 Different solution to F:For each right point you find the maximal left endpoint for which the answer is yes. It is easy to see that you can use the two pointer technique to compute this. We maintain a set (for its sorted order) and then moving the pointers basically amounts to inserting or removing from the set. To check whether a set is valid, treat it as a sorted vector and find the number of indices $i$ for which $a_i \lt a_{i-1}+a_{i-2}$; if it's at least 4 then we can show that two disjoint non-degenerate triangles exist, otherwise run a bruteforce. To make the solution efficient enough, we maintain the number of such indices throughout the insertions and removals, noticing that an element can only affect the state of at most three indices.
 » 7 days ago, # | ← Rev. 2 →   0 PLEASE REVIEW THIS ALTERNATE METHOD I USED FOR PROBLEM D.this code is what i made but it does not pass the system testing.let me explain in short what i have done.first of all, i can find the array of colors for n <= 5 myself. for n > 5, there will be two cases: n is odd or n is even.now if n is odd, it will never connect with vertex 1 (because odd ^ 1 = even ( >= 4) when odd >= 5, which are not prime) hence i can give color 1 to the all odd numbers after 3.we will have more subcases when n is even. n ^ odd can be prime but n ^ even can never be prime except when n ^ even is 2, which is only possible when n & 2 is 2 (that is, binary representation of n has 2 in it) and even is n — 2 (as it will have all the 1s and 0s at the same position except the 2nd bit).for checking with odd, we only need to care about 3 as it is colored with color 2, whereas all other odds are colored with color 1. Now we will keep track of the colors we have remaining. if n ^ 3 is prime, we will not have color 2. also if n ^ (n — 2) is prime, we will not have the color of vertex n — 2 as well. as we know that chances of n ^ odd being prime are significant, hence we assume that we do not have color 1 for n. so if n ^ 3 is not prime and n ^ (n — 2) is not prime or n ^ (n — 2) is prime but n — 2 has larger color (like 3 or 4) we will have color 2 free for n, else we will have color 3 free. else if n ^ 3 is prime we will have color 3 and 4 free for n (using the same logic).so we will never require more that 4 colors and no two connected vertices will have the same color.pls find any logical shortcoming in my answer, if there is any....
•  » » 7 days ago, # ^ |   0 If n >= 14, then any two vertices from (11, 9, 12, 14) are adjacent. It means, that they must be with different colors. But in your code for every i > 5 vertex i can be colored in colors 2, 3, 4.
•  » » » 6 days ago, # ^ |   0 all odd numbers >= 5 are colored with color 1, so i am using all 4 colors available.
•  » » 6 days ago, # ^ |   0 now if n is odd, it will never connect with vertex 1 this is correct hence i can give color 1 to the all odd numbers after 3 this is wrong.You failed to check that the odd numbers after 3 don't connect within themselves. And they do.We have $4k+1 \oplus 4k+3 = 2$ (this is because the binary representation is all the same except for the last 2 bits). Substitute in any integer $k>=2$ to get a pair of odd numbers both greater than 3 that connect, so no you cannot give the color 1 to all odd numbers after 3. And thus your entire solution fails.
•  » » » 6 days ago, # ^ |   0 A big F...thanks!
 » 7 days ago, # |   0 I would like to share another approach for Problem C : while the 40 operations are not over we will sort the array provided to us find the minima and maxima find the middle value and then use this middle value to form the new array and find absolute diff between array and mid and again sort the array till either all the values are 0 or the operations are over.My code:Have a look
•  » » 4 days ago, # ^ |   0 How is this giving optimal answer.
 » 7 days ago, # | ← Rev. 3 →   0 My cool (imo) solution to G : Lets keep a buffer of size K * K at top leftThe right section of K * (M — K) will be my V-placing zone The bottom section of (N — K) * K will be by H-placing zoneWe normally put any H or V in their respective zones, except for when the zones are full, then we use the bufferLets call a H block => buffer has a H type thing H full => we cant place H in its zoneV full and V block defined similarly If we can ensure V-zone full and H block doesnt happen simulatenously (and ofc its symmetric thing as well), we win However, its easy to do that1) if there is a H block, filling up V — zone naturally gets rid of that 2) if V — zone is full, there exists a row such that the row becomes full upon placing a H there
•  » » 6 days ago, # ^ |   0 This looks equivalent to the editorial solution, prioritizing resets in the editorial is the same as maintaining the buffer here.
 » 7 days ago, # |   +4
 » 7 days ago, # | ← Rev. 2 →   +28 D is ok-ish, don't think all the hate is justified. (though reasoning in the editorial is strange – looks way too observation-based while just thinking about xor of odd/even almost immediately provides a solution)But E imo is atrociously uninspiring – I couldn't believe that I understood the problem correctly until I got AC.
•  » » 7 days ago, # ^ |   0 Can you explain the odd/even logic for D?
•  » » » 7 days ago, # ^ |   +14 my thought process:xor of same-parity numbers is even, which is usually not primeso the most greedy approach would be to divide in two groups – even and oddof course it doesn't work, e.g. 1^3=2We know (at least from test case) that at some point we would need at least 4 groups, so let's try to divide both current groups in twoLet's just take odd numbers starting with one trying to avoid 2 as xor-sum of last two elements: 1, 5, 9, 13, 17...And at this point I got the solution from the editorialafter writing it up I guess there are still some strange observations, but well, problem is mathy
•  » » » » 7 days ago, # ^ |   0 Oh that's actually much more straightforward than I thought. That's a lot more intuitive than I thought.
 » 7 days ago, # |   +50 ZhouShang2003, could you please share how the checker for problem D is implemented?
•  » » 6 days ago, # ^ |   +27 ZhouShang2003 shared Bitwise Xor Convolution, which can be applied to the values of each color to validate that no two numbers of the same color have their XOR equal to a prime number. Thanks!
 » 7 days ago, # |   0 The most cool thing was proving that range greater than equal to 48 will always be yes.
 » 6 days ago, # |   -12 Swap D and E
 » 6 days ago, # |   0 I clearly am doing something wrong while writing code. My question is whether anyone can tell me what :pleading_face:
 » 6 days ago, # |   +5 So many constructive problems, I got stuck on D for 10 minutes and nearly failed to get positive delta
 » 6 days ago, # |   +37 Problem D could've been erased from the contest
 » 6 days ago, # |   0 " This ensures that any two vertices of the same color have a difference that is a multiple of 4, so their XOR is a multiple of 4"Can anyone explain for me this line
•  » » 6 days ago, # ^ |   +11 $4|(a-b)\\ a\bmod 4=b\bmod 4\\ a\operatorname{and} 3=b\operatorname{and} 3\\ (a\operatorname{and} 3)\operatorname{xor}(b\operatorname{and} 3)=0\\ (a\operatorname{xor} b)\operatorname{and} 3=0\\ 4|(a\operatorname{xor} b)$
•  » » 6 days ago, # ^ |   0 Or in a less mathy way, you can think of their binary numbers. If you add a multiple of 4 to a binary number, it never affects the first two bits. This is because every bit to the left of the first two bits is divisible by 4, and the first two bits aren't. So adding something divisible by 4 can't change the first two bits. That means the last two bits of A and A+4 are the same which means that they both become zero when we xor them. This makes it divisible by 4.
 » 6 days ago, # |   +36 D is a piece of shit
 » 6 days ago, # |   0 Hello,could you please tell me In Problem B’s answer ，what's the meaning of" If a（i-2） & a（i-1）=b(i-1)=1 , then a(i — 1)=1 ?" .
 » 6 days ago, # |   0 The idea I got in D after going through editorial was If we take two number x and x+4 and so on their xor is always gonna yield a number which is multiple of 4 , so we need only 4 color as it is the minimum non prime number , so we can arrange all the numbers in these way so that it will take only 4 numbers to color them.
 » 6 days ago, # |   -45 worst contest ever
 » 6 days ago, # |   +3 the editorial approach for C which nobody did in the contest is actually understandable like you can see why it will make all numbers 0 after at most 30 iterations but what most of people did is (max_element /2 ) which I spent 3hours trying to get how did they think about that and I reached nothing I think getting this idea require some strong knowledge in some math field
•  » » 6 days ago, # ^ |   0 I thought about it like this: Always choosing max_element/2 is the best option for narrowing all numbers in the array down, because there will never be number greater than the max if we chose max_element/2 as x prior, since there will be no number greater than abs(0-max/2), which is equal or lower than max-max/2. It is easy to understand that by choosing max/2 as x all the time, max will eventually be equal to 1, and since no number in the array is higher than max and all numbers have the same parity, when max==1, every number will be equal to 1, so when max turns 1, all you have to do is choose x as your next x and turn every number in the array to 0
 » 6 days ago, # | ← Rev. 2 →   +10 Problem DConstructive forces .
 » 6 days ago, # |   0 In F why do we need to use both algorithms would only either one of them not work to check for triangles?
 » 6 days ago, # |   0 It is not necessary to enumerate all sets of 6 consecutive sticks if the Algorithm 2 fails in F, we can only check 6 that are with the largest 3 that form a triangle
 » 6 days ago, # | ← Rev. 2 →   +11 Here's a cool idea for problem F in brute forcing the '6 consecutive' sticks to find 2 triangles. After sorting the range [l,r], we are dividing each set of 6 consecutive elements to 2 triangles... Each element could either be in triangle 0 or triangle 1. We hence want to be finding all permutations of [0,0,0,1,1,1] and mask them over the sticks..The best part is that, we only need to check for 3 masks and not all masks. these are: [0 1 0 0 1 1], [0 1 1 0 0 1], [0 1 1 1 0 0]. Why does this work?Consider the mask [0,1,0,1,0,1] and let the elements be v_0, v_1, .. v_5If this mask gave us two triangles it would mean: v_0 + v_2 > v_4 v_1 + v_3 > v_5 Note that if this is true, so is v_0 + v_2 > v_3 v_1 + v_4 > v_5 which is essentially mask [0,1,0,0,1,1]. This reduces the time taken immensely from TLE (5000 ms) to AC in 180 ms
 » 6 days ago, # |   0 I solved C in a alternate way :- Get the minimum and maximum ele in the array. Calculate the midpoint x between them by calculating the average. Apply the transformation ai = abs(ai-x). Perform this until all the elements becomes 0 or total num of operations exceeds 40.I am not sure why this works ,it may be hackable,but in this way I was able to normalize quicker on pen and paper. Here is the submission:- 273227608
 » 6 days ago, # |   0 My thought process behind solving Problem D 1991D - Prime XOR Coloring:In coloring problems with high constraints on the number of nodes, it's likely that the amount of needed colors in an answer is bounded by some number. I didn't immediately think that number would be $4$, but I kept this in the back of my mind.Now, since we can't obviously create all edges where the xor of the endpoints is prime, I tried thinking of special properties of the graph: 1. There is an edge $(1, p - 1)$ for all primes $p$. 2. Can two even numbers have an edge between them? No, because primes are all odd and the xor of two even numbers can never be odd. Similarly, the xor of two odd numbers is even because they both have their $0$-th bit set initially.Observation 1 wasn't too useful and observation 2 was wrong because I had forgotten about the only even prime number 2. But this reasoning was important because this meant that the only edges between odd numbers would be in pairs of complements where the $1$-th bit was set in one number and the $1$-th bit was off in the other. The same for even numbers. You can even print out these edges and draw them to visualize a small disconnected graph.Now the final observation is that all the remaining edges are between odd and even numbers. And because even nodes connected to each other need to have different colors (same for odd nodes), this meant that the new even-odd edges didn't require any coloring changes to the graph. This is also a construction with just $4$ colors for any $N$. Looking at the sample made it clear that I could manually handle cases with small $N$ and run my solution for larger $N$.
 » 6 days ago, # |   -6 D is the kind of problem that makes you burn the whole world down.
•  » » 6 days ago, # ^ |   0 I agree it.
 » 6 days ago, # |   +20 I felt E was better than D. Though I only got E a few minutes after the contest ended, it's a beautiful problem that lets you choose to play as Alice or Bob (although game is deterministic)
 » 6 days ago, # |   +153 Since authors are getting slammed for no reason, I'll have to state that problem D is a nice problem, and the round was generally enjoyable. Good job!
•  » » 6 days ago, # ^ |   +21 Agreed, i enjoyed every problem except F.Upsolved H, that too was excellent
•  » » 6 days ago, # ^ |   0 D is a problem that might be obvious for skilled xor-problem solvers and really hard to guess otherwise, and as E and F felt like D and E I don't see why it should've been here. This problem alone is good, but this contest might be better without it. Of course I am speaking knowing how many people solved each task, but still
•  » » » 6 days ago, # ^ | ← Rev. 2 →   +27 you are not supposed to guess iteditorial is badly written for Dall primes except 2 are odd => x, y cannot have an edge if parity(x) = parity(y), except for y = x ^ 2 divide into groups by parity, now every node has degree <= 1, trivially 2-colourable, combine to do 4 coloursObserve by samples n = 6 is already 4, so you're done. Great problem imo. Excellent to have n = 1...6 in samples, no guessing needed
•  » » 6 days ago, # ^ |   -12 Who asked?
•  » » » 6 days ago, # ^ |   +22 I am very sorry for this comment. I actually really enjoyed the round and problem D. I commented on it only as a joke and regret my decision.
 » 6 days ago, # |   0 constructive round
 » 6 days ago, # |   0 I have one question about problem D: Assume that we only need 2 color to color all node, the i-th node is color with color i%2+1 so that every node with same color will have the XOR is a multiple of 2. But this assumption is wrong because we can point out that vertices 1, 3, 4, and 6 form a clique. So that the minumun answer is 4 color. But it is possible that we can find a case that prove 4 color is wrong like the example above? Thanks in advanced.
•  » » 6 days ago, # ^ |   +11 No, because the counterexample is that 1 xor 3 = 2. 2 is a multiple of 2, but it is also prime.On the other hand, 4 is a multiple of 4, but 4 itself is not prime.
•  » » » 5 days ago, # ^ |   +18 I got it, thanks
 » 6 days ago, # |   0 There are too many constructive problems!
 » 6 days ago, # |   0 https://codeforces.com/contest/1991/submission/273321133can anyone please help me figure out whats wrong with this . the logic seems to be same as that of the editorial.
 » 6 days ago, # |   0 Can someone explain why am i getting MLE in this?273351492
 » 5 days ago, # |   0 How can we mathematically prove that a^(a+4k) will be a multiple of 4? Here ^ is XOR . Also does this hold only for powers of 2( 4 in this case)? a^(b+c) != a^b+a^c, otherwise it was trivial, let me know how do we come up with these proofs.
•  » » 5 days ago, # ^ |   0 if the difference is 4 between a and b , a
•  » » » 5 days ago, # ^ |   0 That helps! Thank you
 » 5 days ago, # |   +1 Right now the official code for H is broken, and gives a out of bound error. To fix it you must initialize bitset to MAXN+1 instead of MAXN.
 » 5 days ago, # |   0 Someone please explain the proof for F...Why it is always possible to form 1 triangle if we have at least 45 sticks. Also that fibonacci thing...that is not clear to me....please explain ..it will be helpful.
•  » » 14 hours ago, # ^ |   0 Lets say you want to create a longest sequence of numbers such that no three sticks can form a triangle. Suppose the sorted order is a[1], a[2], ..., a[n].Now, we know by triangle inequality a[1]+a[2]<=a[3] a[2]+a[3]<=a[4] ... so onSuppose we want to construct our sequence in this ascending order. It is obviously correct to choose the smallest number possible in the sequence. I.e. if our existing sequence is a[1], a[2], ..., a[m-1], a[m], then we want to put the smallest x such that x>a[m] and there does not exist indices 1<=ix. It is optimal to choose x=a[m-1]+a[m]. This is because choose anything smaller and we have a[m-1]+a[m]>x, so a[m-1], a[m], and x can be made into a triangle. Anything bigger and we are simply limiting our future terms in the sequence more.Now, the Fibonacci thing seems clear. By using this greedy strategy of choosing the smallest number possible for the next term in the sequence, we construct the sequence 1, 1, 2, 3, 5, 8, 13, ..., the fibonacci numbers.The 45 comes from the fact that F_45>10^9, which is the bound on the array values in the question.However, since the question asks for two constructing two triangles, we must use the number 48 instead, as we need 3 more numbers in our sequence to guarantee we can always construct two triangles
 » 3 days ago, # |   0 in ques 2 why are we taking or?