Keshi's blog

Codeforces Global Round 17 Editorial
By Keshi, 3 years ago, In English

1610A - Anti Light's Cell Guessing

Idea: Anti-Light, Preparation: DeadlyCritic

Hints
Solution
Implementation

1610B - Kalindrome Array

Idea: Davoth, Keshi, Preparation: AmShZ, Keshi

Hint
Solution
Implementation

1610C - Keshi Is Throwing a Party

Idea: Keshi, Preparation: Keshi

Hints
Solution
Implementation

1610D - Not Quite Lee

Idea: DeadlyCritic, Preparation: DeadlyCritic

Hints
Solution
Implementation

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

Idea: AmShZ, Preparation: AmShZ

Hints
Solution
Implementation

1610F - Mashtali: a Space Oddysey

Idea: AliShahali1382, Preparation: AliShahali1382

Hint
Solution
Implementation

1610G - AmShZ Wins a Bet

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

Hints
Solution
Implementation

1610H - Squid Game

Idea: Tet, AliShahali1382, Preparation: AliShahali1382

Solution
Implementation

1610I - Mashtali vs AtCoder

Idea: AliShahali1382, Preparation: AliShahali1382

Solution
Implementation
  • Vote: I like it
  • +175
  • Vote: I do not like it

Comments Comments (79)
| Write comment?
»
3 years ago, # |
  Vote: I like it +87 Vote: I do not like it

errorgorn cluck cluck cluck!

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +49 Vote: I do not like it

    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

    → Reply
»
3 years ago, # |
  Vote: I like it +54 Vote: I do not like it

Btw just saying, the story in D was about the fact that we didn't have D $$$7$$$ days before the contest, because of the testers' feedback and also because the fact that I didn't solve C and D until about then, I decided to add D to fix the gap, it wasn't perfect however. Hopefully made the round better.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it +94 Vote: I do not like it

Just a little suggestion: we should use $$$\geq$$$ and $$$\leq$$$ instead of $$$>=$$$ and $$$<=$$$ to make the editorial more pleasant to read.

→ Reply
»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

In problem I, am I the only person who actually solved the AtCoder problem in contest without looking at it?

→ Reply
»
3 years ago, # |
  Vote: I like it +22 Vote: I do not like it

I think hint 3 from problem D is missing the sum symbol on the RHS.

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

136659229 Can anyone tell me what is wrong in this code of B (Kalindrome Array). All similar codes got AC.

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

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

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

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

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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.

        → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        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.

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

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

        → Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

For problem C if the constraints supported O(N*N),then would DP work?

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

    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.

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

      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]]!

      → Reply
»
3 years ago, # |
← Rev. 5   Vote: I like it -17 Vote: I do not like it

vscode txdy

→ Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I cant understand D's explaining gcd(c1,c2,…,ck)=g s=∑ ci(ci−1) / 2 i= (1...k) when g is odd s % g == 0 && ci / 2 % g == 0 why how to explain c1 = 3,c2 = 9

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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

    → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How is the below solution wrong for problem B? I am not able to figure out the test case.

136636817

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

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

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

    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!

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    You might get WA on this test:

    5

    1 3 2 4 1

    Edit: the result is correct, my bad

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone pls explain the even case in problem D ?

→ Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can anyone E in detail? I am not able to understand hint 1 properly.

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

    We know that an array is bad if it has a terrible subsequence. If the length of our terrible subsequence is bigger than 3, then we can remove some elements and it will remain terrible.

    So the array of three elements is terrible of a[1] < AVG < a[2]. If a[1] != a[2], then a[1] always smaller then AVG. So now we need to check AVG < a[2] -> (a[1] + a[2] + a[3]) / 3 < a[2] -> a[1] + a[2] + a[3] < 3 * a[2] -> a[1] + a[3] < 2 * a[2] -> a[3] — a[2] < a[2] — a[1]. If in our array exists three elements (i < j < k) such that a[k] — a[j] < a[j] — a[i] then our array is bad. If we take the first element as i, our a[j] — a[i] will be maximized, and if we take two consecutive j and k then our a[k] — a[j] will be minimized. We can only check all consecutive j and j + 1 if a[j+1] — a[j] < a[j] — a[1], and if it's true in at least one j then our array is bad if it's always false then our array is good.

    Hope I understand the hint and explained it correctly.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      Yes after reading above, It became clear that only checking the tuple of the form A_1,A_i and A_(i+1) is sufficient and it will account for all the possible tuples. Also, we can show that if make sure no such tuple exists, then for any subsequence, its difference array will be non-decreasing. Hence all subsequence will be good too.

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I did read and tried to understand several explenations to C. But still do not get how or why the check "is it possible to invite x persons" works.

What is needed to understand that kind of logic?

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

    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

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

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

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

      how does selecting a prefix is better than a subsegment of size x from the group. like when do you know when to skip a person as taking him would not be beneficial for the future selections?

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

        When we are checking for valid persons to select we check for both a and b not just one of them, so when we're at the i-th person if he's valid we take him, if we didn't take him we will end up taking another person who's equal to him since the other person will fulfill the same conditions for both a and b.

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

        Look at it like this, If you want to invite $$$k$$$ person, then if you wanted to invite a person $$$x$$$ as $$$y$$$-th poorest in the party, then for a specific $$$k$$$ and $$$x$$$, the possible $$$y$$$-s form a segment, let's say from $$$l_x$$$ to $$$r_x$$$. After this you can use Monotonic Stack + Lazy (i.e. keep a vector $$$v$$$ such that $$$v_i$$$ is equal to if we invite $$$i$$$ friends, how many more rich person we can add, then add friends one by one and keep $$$v$$$ updated in $$$O(logn)$$$), hopefully understandable.

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

      Ahhhh...ok.

      Basically we maintain a sorted set of choosen persons, then check in order of richness each single person.

      We accept that persons if that persons constraints are so that it fits the next free position in the set of choosen persons.

      Thanks for explaining.

      → Reply
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      thank you brdr

      → Reply
»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

I hope this doesn't get down-voted For problem D, I didn't get the solution proposed above. However, I was thinking of a solution from another angle. Firstly, Odd numbers can can have a sum of 0 by itself so we can have any number of odd numbers in our sequence, Even numbers can have a sum of 0 for sure if there is at least 1 odd number in the sequence since O+E = O. The problem I couldn't figure out, When can E numbers alone (Without any odd number in the sequence) have a sum of 0 I don't know if anyone solved it in this approach, and is it possible this way or the only solution is the one in the editorial?

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

    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

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +40 Vote: I do not like it

I have an alternate solution for G without hashing.

136722671

lemma 1
solution
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    My solution 136674351 is a bit different.

    solution
    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    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 $$$i$$$. We represent this solution by computing for every $$$i$$$ the position $$$p_i$$$ of the first bracket contained in the optimal solution for the suffix starting at $$$i$$$. Reconstructing the solution for the suffix from the $$$p_i$$$ is easy: the first bracket in the solution is at position $$$p_i$$$, and the remainder is the optimal solution for the suffix starting at $$$p_i+1$$$ (which we can reconstruct recursively).

    How do we compute $$$p_i$$$? If the bracket at position $$$i$$$ is ), then $$$p_i = i$$$ 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 $$$p_i = i$$$ since we cannot remove this bracket by Lemma 1. So, the only case remaining is that the suffix starting at position $$$i$$$ looks like (s)t where s is a valid bracket sequence. Let $$$j$$$ 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 $$$i+1$$$.
    • 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 $$$j$$$.

    Since we know the optimal solutions starting at position $$$i+1$$$ and $$$j$$$, we can simply compare them character by character (using the values $$$p_i$$$) to decide which is lexicographically smaller, but this has a runtime of up to $$$O(n^2)$$$.

    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 $$$O(n \log n)$$$.

    Why is this?
    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain hint 3 in problem D, I can't understand what x is here and how we are arriving at the given equation? Thanks in advance!!

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

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

    → Reply
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Here are the video Solutions to the first 4 problems of the round in case you prefer that.

→ Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

problem H was given 2100 rated tag(its a mistake ig). Anyone know how problem rating works.

→ Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

who can explain the problem D,the solution can't understand。

→ Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Thanks for pointing out the typos.

→ Reply
»
3 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Problem I is just the normal Hackenbush problem on a graph with cycles .

You can turn a cycle into a node using "Fusion Principle". And implement it using Heuristic Merging of sets in O(nlog^2) .

submission:136731363

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -11 Vote: I do not like it

My ideology for the first who have any problem -> as in question we have given that computer hide some cells and on query (suppose k) are done and it will return the k values that will be the distance of hidden cells from the cells that are done by user as query

manhattam formula is important-> |a1-a2| + |b1-b2|;

Think Yourself
Case 1
Case 2
Case 3
→ Reply
»
3 years ago, # |
  Vote: I like it +73 Vote: I do not like it

.
→ Reply
»
3 years ago, # |
← Rev. 9   Vote: I like it -35 Vote: I do not like it

..

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a way to solve problem F using Euler cycle/Euler path idea?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody give link/info on why the solution to $$$x_1.c_1 + x_2.c_2 ... x_n.c_n - \ \sum_{i=1}^{n} c_i.(c_{i - 1} - 1)/2 = 0$$$ is when $$$g = gcd(c_1, c_2 ... c_n)$$$ divides $$$c_i.(c_{i-1})/2$$$ as specified on Hint 4 of Problem D

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

    Search this on google "Linear Diophantine Equation". you will get that.

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

[deleted]

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Otherwise, we remove a black edge, in which case you can show the parity of grundy changes(this one is easy to prove and left for the reader).

Have no idea how to prove it, can someone help? Also, how does it help proving that this exact grundy number is not reachable?

→ Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Can anyone explain the solution of F?? I can not understand the editorial.

→ Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

So ci(ci−1)/2 has a reminder equal to (2^l) − 1 modulo (2^l). All the other terms ci(ci−1)/2 were divisible by (2^l) except these, so if the number of such ci-s is even, then their reminders sum up to 0 modulo (2^l) then c is good, and not otherwise.

Not able to understand this line in editorial of problem D can anybody help?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

DeadlyCritic if gcd(c1,c2,…,ck)=g, then if g divides s, the array is good, otherwise it's not. Can you explain the prove or just the name of this theoram. I am unable to prove it.

→ Reply
»
3 years ago, # |
  Vote: I like it +31 Vote: I do not like it

AliShahali1382 errr.... I think on problem F there seems to be no input with $$$n,m > 100000$$$. I submitted a hack with $$$n=m=300000$$$ and the validator says $$$n \leq 100000$$$. I think the statement has wrong constraints....

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Oh, damn! Yes, it was supposed to be 100000. It was a mistake in problem statement :(( However, that doesn't affect the solutions.

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -18 Vote: I do not like it

The explanation for D looks so complex for a 2000-rated problem

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +21 Vote: I do not like it

I'm so shocked the official solution of F is not Euler cycle!

solution

Btw, the inspiration comes from this AGC problem

→ Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

First of all, I want to apologize for bringing this old blog into the recent post tab.

Now, My Question is what is the difference between the approaches for WA submission and AC submission (code differ in only pal() function) for the problemB.

My Approach

Helping in the approach might help you too. To know some dark side of palindromic arrays.

P.S: I have already read the editorial, and what worries me is that editorial say the same approach as my WA submission :(

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

    Something to do with Java's Integer caching, apparently.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The editorial of problem H has wan my applause.

Good job!

→ Reply
»
3 years ago, # |
  Vote: I like it +40 Vote: I do not like it

Actually I have a much simpler approach to problem H.
Link
And if you implement the nlog lca in my code with the Method of Four Russians you will get a solution with O(n) time complexity.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +30 Vote: I do not like it

    I now have a method to improve my code to O(n) without even calculating the lca.
    We only need to find the successor of the x in the path from x to y where x is the ancestor of y, which can be done in O(n) time complexity with dfs.
    I have no idea why I didn't discover such a simple optimization the first time.

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

    Here 's my code.
    It's currently the fastest solution on CF.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

for problem I, it seems like that we break the tree in two parts:

1.consider node u, if there's no pinned node in its subtree, then we make grundy^=grundy(u)

2.otherwise, the grundy is the parity of number of black edges

however, in 1., why we can take the subtree of a grey edge out and consider it singly?

could anyone please explain it for me?thanks in advance.

→ Reply