ZhouShang2003's blog

By ZhouShang2003, 3 months ago, In English

1991A — Maximize the Last Element

Hint
Solution
Code

1991B — AND Reconstruction

Hint
Solution
Code

1991C — Absolute Zero

Hint 1
Hint 2
Solution
Code

1991D — Prime XOR Coloring

Hint
Solution
Code

1991E — Coloring Game

Hint
Solution
Code

1991F — Triangle Formation

Hint
Solution
Code

1991G — Grid Reset

Hint 1
Hint 2
Solution
Code

1991H — Prime Split Game

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
  • Vote: I like it
  • +164
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +83 Vote: I do not like it

so zengminghao told me during the round that problem I can be found at https://www.brand.site.co.il/riddles/200802q.html

Fortunately, it seems it has affected almost no one. Sorry for this unfortunate coincidence though :/

»
3 months ago, # |
  Vote: I like it -92 Vote: I do not like it

D is nice

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

    Worst problem I've ever seen.

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

    D feels more like a math problem rather than an algorithmic one. I don't think it's a good problem. :(

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

      Why?

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

      It's not mathy at all

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

      It’s not something mathy it’s just a puzzle.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        $$$3$$$ and $$$4$$$ are also connected, as $$$3 = 11_2, 4 = 100_2, 11_2 \oplus 100_2 = 111_2 = 7$$$, which is prime.

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          In D sample test case with n = 6, the edges are (1, 2), (1, 4), (3, 4). Then we can color vertices 1 as c1, 2 as c2, 3 as c1, and 4 as c2. So only 2 colors are needed so how is the answer 4 with coloring (1 2 2 3 3 4)? Please correct where I am wrong.

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

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

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

      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

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 ?

        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

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

      4 color theorem doesn't apply here. Consider $$$K_5$$$ where the chromatic number is 5.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    D was like Goodbye 2023, u either saw the pattern or cried

  • »
    »
    3 months ago, # ^ |
      Vote: I like it -34 Vote: I do not like it

    I believe anyone can't get the solution unless you know the four color theorem :(

»
3 months ago, # |
  Vote: I like it +181 Vote: I do not like it

imo, D wasn't so good

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

    D is going on bullet point 1 of my suicide note

    • »
      »
      »
      3 months ago, # ^ |
      Rev. 2   Vote: I like it +28 Vote: I do not like it

      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.

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

        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.

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

        $$$K_4$$$ appears as a subgraph for $$$n \geq 6$$$ as $$$(1,3,4,6)$$$ is completely rigorous...

        • »
          »
          »
          »
          »
          3 months ago, # ^ |
          Rev. 2   Vote: I like it +13 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          3 months ago, # ^ |
          Rev. 2   Vote: I like it +1 Vote: I do not like it

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

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I’ve got the same idea.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    D was like Goodbye 2023, u either saw the pattern or cried

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

If you're wondering about about the connection between XOR and modulo 4, you can upsolve CF15C : Industrial Nim

Update: I also created a video and practice contest on this idea.

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

quite a few constructives

  • »
    »
    3 months ago, # ^ |
    Rev. 3   Vote: I like it -50 Vote: I do not like it

    constructiveforces

    edit: A master copy pasted the exact same comment from me and got +38. What are the downvotes for??

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      so, you confirm that you just copy-pasted it and expect upvotes

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      ratism?

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Maybe if you didn't edit your comment and whine about receiving downvotes, your comment would be in the green now

»
3 months ago, # |
  Vote: I like it +24 Vote: I do not like it

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

»
3 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Problem E is so similar to this Problem.

»
3 months ago, # |
  Vote: I like it +10 Vote: I do not like it

I can't note that $$$4\mid \left(a\oplus (a+4k)\right)$$$. So sad.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why does 4∣(a xor (a+4k))? Is there an easy way to see this?

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

      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.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 months ago, # |
  Vote: I like it +38 Vote: I do not like it

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

»
3 months ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

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;

}

~~~~~

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

Why is the title of problem C "Maximize the Last Element"? Shouldn't it be "Absolute Zero"?

UPD: Changed.

»
3 months ago, # |
  Vote: I like it +76 Vote: I do not like it

A round full of ARC&AGC problems. :)

  • »
    »
    3 months ago, # ^ |
      Vote: I like it -25 Vote: I do not like it

    F could maybe be AGC A so I struggle to understand you since 3 problems don't make a full round. Is it sarcasm?

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

      F is too ugly to be in AGC.

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
3 months ago, # |
Rev. 4   Vote: I like it +4 Vote: I do not like it

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.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Very cool, much more intuitive. I like it.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
3 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Enjoyed the round a lot, especially D and E are great. Thanks to coordinators, authors and testers!

»
3 months ago, # |
  Vote: I like it +46 Vote: I do not like it

Human intelligence round

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

    I think G is very Tang (I don't know how to say it in English?

»
3 months ago, # |
  Vote: I like it +7 Vote: I do not like it

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 :(

»
3 months ago, # |
  Vote: I like it +52 Vote: I do not like it

No evaluation of good or bad but problem D strikes me as utterly absurd.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
3 months ago, # |
  Vote: I like it -33 Vote: I do not like it

D is a good problem, I like it very much!

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

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.

»
3 months ago, # |
  Vote: I like it +30 Vote: I do not like it

Constructive Forces.

»
3 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it
WA - E

same solution as editorial. why still WA ??

upd: got it. thanks

»
3 months ago, # |
  Vote: I like it +9 Vote: I do not like it

anyone tried colouring graph greedily in the problem D ???

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

    yeah, when you do that it makes a weird pattern:

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

      been there, and it touches 36, at n = 2054... and then we don't need any more colour than 36 till n = 2 * 1e5.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C Video Editorial

https://youtu.be/wsD3l8J1Hog

»
3 months ago, # |
  Vote: I like it +18 Vote: I do not like it

G killed me, maybe guessing that the construction is not that hard will help next time

»
3 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.me/contest/1991/submission/273218080

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

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 possible

https://codeforces.me/contest/1991/submission/273238586

Edit: 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

»
3 months ago, # |
  Vote: I like it +17 Vote: I do not like it

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.

»
3 months ago, # |
  Vote: I like it +24 Vote: I do not like it

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.

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

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

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      all odd numbers >= 5 are colored with color 1, so i am using all 4 colors available.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

My cool (imo) solution to G :

Lets keep a buffer of size K * K at top left

The right section of K * (M — K) will be my V-placing zone

The bottom section of (N — K) * K will be by H-placing zone

We normally put any H or V in their respective zones, except for when the zones are full, then we use the buffer

Lets call a H block => buffer has a H type thing

H full => we cant place H in its zone

V 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 that

1) 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

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This looks equivalent to the editorial solution, prioritizing resets in the editorial is the same as maintaining the buffer here.

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

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.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain the odd/even logic for D?

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

      my thought process:

      xor of same-parity numbers is even, which is usually not prime

      so the most greedy approach would be to divide in two groups – even and odd

      of course it doesn't work, e.g. 1^3=2

      We 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 two

      Let'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 editorial

      after writing it up I guess there are still some strange observations, but well, problem is mathy

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh that's actually much more straightforward than I thought. That's a lot more intuitive than I thought.

»
3 months ago, # |
  Vote: I like it +50 Vote: I do not like it

ZhouShang2003, could you please share how the checker for problem D is implemented?

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

    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!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The most cool thing was proving that range greater than equal to 48 will always be yes.

»
3 months ago, # |
  Vote: I like it -12 Vote: I do not like it

Swap D and E

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I clearly am doing something wrong while writing code. My question is whether anyone can tell me what :pleading_face:

»
3 months ago, # |
  Vote: I like it +5 Vote: I do not like it

So many constructive problems, I got stuck on D for 10 minutes and nearly failed to get positive delta

»
3 months ago, # |
  Vote: I like it +37 Vote: I do not like it

Problem D could've been erased from the contest

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

" 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

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it
    $$$ 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) $$$
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

»
3 months ago, # |
  Vote: I like it +44 Vote: I do not like it

D is a piece of shit

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?" .

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
3 months ago, # |
  Vote: I like it -45 Vote: I do not like it

worst contest ever

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

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

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

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

Problem D

Constructive forces .

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In F why do we need to use both algorithms would only either one of them not work to check for triangles?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can find counter examples to both algorithms if used alone:

    If only using algorithm 1 (6 consecutive elements), you will miss [1, 1, 2, 3, 10, 10, 11].

    If only using algorithm 2, you will miss [1, 1, 2, 2, 2, 2].

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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_5

If 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

Sub

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, # |
  Vote: I like it -6 Vote: I do not like it

D is the kind of problem that makes you burn the whole world down.

»
3 months ago, # |
  Vote: I like it +20 Vote: I do not like it

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)

»
3 months ago, # |
  Vote: I like it +163 Vote: I do not like it

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!

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

    Agreed, i enjoyed every problem except F.

    Upsolved H, that too was excellent

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      3 months ago, # ^ |
      Rev. 2   Vote: I like it +27 Vote: I do not like it

      you are not supposed to guess it

      editorial is badly written for D

      all 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 colours

      Observe 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

  • »
    »
    3 months ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    Who asked?

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

      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.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

constructive round

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

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

    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.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

There are too many constructive problems!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.me/contest/1991/submission/273321133

can anyone please help me figure out whats wrong with this . the logic seems to be same as that of the editorial.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain why am i getting MLE in this?

273351492

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if the difference is 4 between a and b , a<b , then always the first two bits of the a and b will be the same (since we are adding on the 3rd bit on the a and that can only affect bits who are higher or equal to 3rd bit of a). since the first 2 bits are equal , first two bits of a^b is 00 , and you can only represent each number as a multiple of 4 if their first 2 bits is 00(you can shift it 2 times which is equilavent to dividing it by 4 , if first 2 bits is not 00 while shifting you will lose some true bits which means number will be rounded down)

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 on

    Suppose 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<=i<j<=m such that a[i]+a[j]>x. 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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in ques 2 why are we taking or?

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In D, in the tutorial it is stated for more than 6 nodes we need 4 colors. But if there is a triangle in the graph, we need 3 colors, how is this ensured that there will be no triangle in the graph.