Codeforces Global Round 17 Editorial

1610A - Anti Light's Cell Guessing

Idea: Anti-Light, Preparation: DeadlyCritic

1610B - Kalindrome Array

Idea: -zeus-, Keshi, Preparation: AmShZ, Keshi

1610C - Keshi Is Throwing a Party

Idea: Keshi, Preparation: Keshi

1610D - Not Quite Lee

Idea: DeadlyCritic, Preparation: DeadlyCritic

1610E - AmShZ and G.O.A.T.

Idea: AmShZ, Preparation: AmShZ

1610F - Mashtali: a Space Oddysey

Idea: AliShahali1382, Preparation: AliShahali1382

1610G - AmShZ Wins a Bet

Idea: AmShZ, Keshi, Preparation: AmShZ, Keshi, alireza_kaviani, AliShahali1382

1610H - Squid Game

Idea: Tet, AliShahali1382, Preparation: AliShahali1382

1610I - Mashtali vs AtCoder

Idea: AliShahali1382, Preparation: AliShahali1382

Comments (64)

• 15 hours ago, # ^ |

  ← Rev. 3 →  

  +49

  lol in all seriousness, no hard feeling about it. as a fellow problemsetter i also understand how hard it is to create strong pretets for problems because theres no way you can kill every possible weird thing people do

  i still remember in RAIF round there was the A had some condition like if (a==0 || b==0) and someone wrote if (a*b==0). Theres no way anyone will be able to predict that lol

  honestly, i enjoyed this contest. having FGHI to jump around and finally solving G was really fun, thanks for setting this contest :)

  update:

  now we are both stupid chicken

  • 13 hours ago, # ^ |

    

    shit! what a stupid hack test

    • 13 hours ago, # ^ |

      ← Rev. 2 →  

      +28

      You should see this too...

      In fact this thing TLEs on n=40 locally most of the times but cf reruns TLE submissions so I had to make n larger.

      K*re khar

• 8 hours ago, # ^ |

  It kinda fixed the gap according to the numbers, and imo it is a decent problem. Won't ask for more from problem D in a div 1+2.

  P/S: It indeed made the round better.

  • 8 hours ago, # ^ |

    Thanks for your feedback. Makes me happy.

• 17 hours ago, # ^ |

  Thanks!

• 17 hours ago, # ^ |

  Thanks!

• 15 hours ago, # ^ |

  Integer's cache so that your '==' could be wrong.use int is ok.

  • 14 hours ago, # ^ |

    Thanks, It solved my problem. But I never faced such type of problem with Integer before. What was the reason now?

    • 14 hours ago, # ^ |

      The reason is simple you can't compare two objects with ==, cause it checks their references equality, instead you have to use the equals method.

    • 14 hours ago, # ^ |

      ← Rev. 2 →  

      +3

      Integer will cache value between -127 to 128, and you can use '==' within this scope.if beyond this scope you should use 'equals' instead of '=='.For more details, you can see the source code of Integer.

    • 13 hours ago, # ^ |

      The reason is not coding in IDEA or ignoring IDEA's warning about objects comparison

• 16 hours ago, # ^ |

  Yes, we can do something like this. dp(len) denotes if the length of the sequence is len, then what is the maximum count of right_most elements that we can add to this sequence. And for each i, with dp(len) we can update dp(len+1) if dp(len) > 0.

  • 15 hours ago, # ^ |

    I don't think 1-d DP will work, solely because the value of b[i]'s can differ and can produce different output, so I was asking about a solution based on dp[n][b[i]]!

• 15 hours ago, # ^ |

  I guess it should have been, "If g is odd ci(ci-1) % (2g) == 0"
  Second para of This Comment might help

• 15 hours ago, # ^ |

  Me neither. Neither I understand what is "x" in x1c1+x2c2+…+xkck. I would understand it if the equation would be (x1c1 + c1/2) + (x2c2 + c2/2) + ... + (xkck + ck/2). For example if c1 would be 4, we can get sums like 2, 6, 10, ..., no 4, 8, 12, ...; or is "x" supposed not to be integer?

  Another point:∑i=1kxici=−sum is it supposed to be ∑i=1kxici=−s or what is "sum"?

  Btw sorry for formatting, but I don't know how it works on CF

• 15 hours ago, # ^ |

  136659229 Same happened with me. Whereas all similar codes got AC.

• 11 hours ago, # ^ |

  Same, Got WA on 3414th token.

  Works with primitive type. OR, using Integer.equal(Integer) when comparing elements from list of Integer wrapper class also works. Not sure why!

  • 9 hours ago, # ^ |

    Yeah exactly.

• 11 hours ago, # ^ |

  ← Rev. 3 →  

  +1

  You might get WA on this test:

  1 3 2 4 1

  Edit: the result is correct, my bad

• 14 hours ago, # ^ |

  To break it down: We are going to invite X persons, and they are already sorted from poorer to richer from 1 through n We keep a counter of how many we invited until now : cnt

  When we are going to the i-th person we check for two things 1. we know we already invited cnt poorer persons (Since all people before i-th are poorer than him) if (b[i] >= cnt) then this condition is fulfilled 2. we know if we invited this person we are going to invite another (X-cnt-1) people (X: total invited, cnt: currently invited, 1: the i-th person himself) if(a[i] >= X-cnt-1) then this condition is fulfilled If both conditions are fulfilled, we invite this person and increase cnt by 1 after going through all n people, if (cnt >= X) then we can invite X people

  Hope this helps you

  • 10 hours ago, # ^ |

    Thanks, I couldn't understand this part from editorial, I really appreciate you helping in the comments.

• 14 hours ago, # ^ |

  I did solve it in the way you described, and interestingly the answer to your question is the same condition as the editorial arrives at- if you bucket the even numbers by the maximum power of two that divides them, then to create a bad sequence, you need to have an odd number of elements from any one bucket, zero elements from the buckets below it, and any combination from the bucket above.

  For example, if we have 2, 2, 4, 4, 8, 8, 16, 16, 48

  We bucket it as follows {2, 2}, {4, 2}, {8, 2}, {16, 3}

  And the number of bad sequences u can create is -

  select odd number of 2's and no restriction on other buckets: 2C1 * 2^7

  select no 2's, odd number of 4's, and no restriction on other buckets: 2C1 * 2*5

  and so on.

  Solution: 136657523

  • 14 hours ago, # ^ |

    ← Rev. 2 →  

    0

    Never mind, I get it now. Thanks a lot

• 14 hours ago, # ^ |

  You can suppose that number 2 means 2x+1, number 4 means 4y+2 and number 6 means 6z+3, your purpose is that you should make their sum equal to zero, you can solve it with Bezout theorem.

  • 13 hours ago, # ^ |

    Thanks a lot

• 13 hours ago, # ^ |

  My solution 136674351 is a bit different.

  solution

• 10 hours ago, # ^ |

  My solution uses a similar kind of idea (see 136678450):

  Lemma 1: We only delete contiguous valid bracket sequences

  Proof sketch

  Then, let's move from right to left and compute the optimal solution for a suffix starting at position . We represent this solution by computing for every the position of the first bracket contained in the optimal solution for the suffix starting at . Reconstructing the solution for the suffix from the is easy: the first bracket in the solution is at position , and the remainder is the optimal solution for the suffix starting at (which we can reconstruct recursively).

  How do we compute ? If the bracket at position is ), then since we cannot remove this bracket. So, assume that the bracket is (. If there is no matching ) bracket in the string, we will again have since we cannot remove this bracket by Lemma 1. So, the only case remaining is that the suffix starting at position looks like (s)t where s is a valid bracket sequence. Let be the position where the suffix t starts (which we can compute using a stack).

  To obtain a solution for the suffix (s)t, there are just two cases:

  • Either we include the first ( bracket, in which case we have to append the optimal solution for the suffix s)t, which is the suffix starting at position .
  • Or we delete the first ( bracket, in which case we have to delete the entire substring (s) and we will only keep the optimal solution for the suffix t, which is the suffix starting at position .

  Since we know the optimal solutions starting at position and , we can simply compare them character by character (using the values ) to decide which is lexicographically smaller, but this has a runtime of up to .

  Instead, notice that the solution where we keep the first ( bracket looks like (s')t' where s' is some subsequence of s, and t' is the optimal solution for the suffix t. So, we actually ask whether (s')t' is lexicographically smaller than t', and we can already decide this after looking at all characters of (s'):

  • If (s') is not a prefix of t', we know due to our comparisons which string is smaller.
  • If (s') is a prefix of t', I claim that (s')t' is smaller. This is because removing the prefix (s') from t' would also be a valid solution for the suffix t, but must be larger than t' by the optimality of t'. Therefore, it is easy to see that appending another copy of (s') to the beginning of t' will make the string even smaller.

  I claim that if we use this optimization, the code runs in time .

  Why is this?

• 4 hours ago, # ^ |

  I described how to arrive at the equation in the complete solution, it basically means we move the -th sequence, times(i.e. add to all the elements in the -th sequence). If it's possible to find -s such that the sum of resulting set of sequences is , then they will satisfy the equation. Also the other way around. (i.e. if it's possible to find such -# that the equation holds, then the resulting set of sequences after moving the -th sequence times, satisfies the second property in the statement)

• 10 hours ago, # ^ |

  Thank you

• 3 hours ago, # ^ |

  For Case 3, we cannot query cells in opposite corners. An example is given in the notes for the problem's test cases. There are multiple cells on the board with the same distance from the opposite corners. We have to query the cells on one side of the board. For example, (0, 0) (0, n-1) or (0, 0) (0, m-1).

• 7 hours ago, # ^ |

  If you find the minimum i(say i1) then if you get another i(say i2) after this where ai2 != an+1-i2 then you will check whether you can make it ai2 == an+1-i2 by removing ai2 or an+1-i2 (you can remove ai2 only if ai2 = ai1 or an+1-i2 only if an+1-i2 = ai1). Hope you get it.

• 7 hours ago, # ^ |

  If you find the minimum i(say i1) then if you get another i(say i2) after this where ai2 != an+1-i2 then you will check whether you can make it ai2 == an+1-i2 by removing ai2 or an+1-i2 (you can remove ai2 only if ai2 = ai1 or an+1-i2 only if an+1-i2 = ai1). Hope you got it.