Keshi's blog

By Keshi, 2 weeks ago, In English

1610A - Anti Light's Cell Guessing

Idea: Anti-Light, Preparation: DeadlyCritic

Hints
Solution
Implementation

1610B - Kalindrome Array

Idea: -zeus-, 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
  • +168
  • Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it +87 Vote: I do not like it

errorgorn cluck cluck cluck!

  • »
    »
    13 days 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

»
2 weeks 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.

  • »
    »
    13 days 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.

»
2 weeks 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.

»
13 days 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?

»
13 days ago, # |
  Vote: I like it -9 Vote: I do not like it

Lol! Testcases in ques.3 were pretty dumb..

»
13 days 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.

»
13 days 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.

  • »
    »
    13 days 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.

    • »
      »
      »
      13 days 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?

      • »
        »
        »
        »
        13 days 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.

      • »
        »
        »
        »
        13 days 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.

      • »
        »
        »
        »
        13 days 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

»
13 days 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?

  • »
    »
    13 days 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.

    • »
      »
      »
      13 days 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]]!

»
13 days ago, # |
Rev. 5   Vote: I like it -17 Vote: I do not like it

vscode txdy

»
13 days 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

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    13 days 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

»
13 days 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

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

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

  • »
    »
    13 days 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!

  • »
    »
    13 days 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

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone pls explain the even case in problem D ?

»
13 days 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.

  • »
    »
    12 days 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.

    • »
      »
      »
      12 days 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.

»
13 days 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?

  • »
    »
    13 days 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

    • »
      »
      »
      13 days 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.

    • »
      »
      »
      12 days 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?

      • »
        »
        »
        »
        12 days 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.

      • »
        »
        »
        »
        12 days 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.

    • »
      »
      »
      12 days 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.

»
13 days 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?

  • »
    »
    13 days 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

  • »
    »
    13 days 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.

»
13 days 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
  • »
    »
    13 days ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    My solution 136674351 is a bit different.

    solution
  • »
    »
    13 days 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?
»
13 days 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!!

  • »
    »
    13 days 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)

»
13 days 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.

»
13 days 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.

»
13 days ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
13 days ago, # |
  Vote: I like it +10 Vote: I do not like it

Thanks for pointing out the typos.

»
13 days 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

»
13 days 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
  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
13 days ago, # |
  Vote: I like it +73 Vote: I do not like it

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

In problem B, why do we have to find only the minimum i that ai≠an+1−i? What about the next i's where ai != an+1-i? EDIT : I understood why

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Your text to link here... Can anyone tell me what is wrong with this code? I am unable to see the test case in which it is giving WA (Problem B).

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

First time to solve C in a contest! "A" was weird not gonna lie but for me the contest was very interesting :D

»
13 days ago, # |
Rev. 9   Vote: I like it -35 Vote: I do not like it

..

»
13 days ago, # |
Rev. 2   Vote: I like it -18 Vote: I do not like it

.

»
13 days 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?

»
13 days 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

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

[deleted]

»
12 days ago, # |
Rev. 3   Vote: I like it -16 Vote: I do not like it

Can anyone tell what's wrong with my solution for pro cbblem B ...? 136659778 }

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Brother don't just copy-paste your code in the forum like you have done. No one will read the code above and you will be downvoted like hell. to share your code you can share the submission link of that code, that will be better.

»
12 days 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?

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey!!

Can anyone please explain some other way to solve B (Can we use 2 pointer approach?).

»
12 days 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.

»
12 days 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?

»
12 days 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.

»
12 days 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....

  • »
    »
    11 days 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.

»
10 days 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

»
9 days ago, # |
Rev. 2   Vote: I like it +11 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

»
2 days ago, # |
  Vote: I like it -8 Vote: I do not like it

For D,

x1c1+....+xkck = S

if g = gcd(c1,...,ck) and g divides S then equation has a solution.

Is there any specific name for this theorem?