isaf27's blog

Editorial for Technocup 2022 — Elimination Round 2 and Codeforces Round #755 (Div. 1, Div. 2)
By isaf27, history, 3 years ago, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +40
  • Vote: I do not like it

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

This was one of the most unbalanced rounds ive been in but div2D was pretty cool i guess

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

My solution for Div2D/1B.


This was the main observation of solution (and the coolest part about this problem for me)

Now, Let's do a binary search to find k.

length of segment [j, k] = k - j + 1 = query(1, k) - query(1, k-1) + 1.

j = k - query(1, k) + query(1, k -1)

you can repeat this for [i, j-1] to figure out i.

code

I also tried to explain my thought process, hope it helps. :D

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

    I think that's exactly the editorial solution

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

      oh really, I didn't carefully read the editorial.
      I saw this "Finaly, we can solve quadratic equation for k−j+1 and get k." and closed, lol.

      I didn't do anything like that (quadratic equations scary) and it seems they binary searched on i.
      It is much cleaner and quite different IMO

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

        Theyre just optimizing for the query count in a weird way. In practice you could've just have asked an extra query to figure out the size of the other part is.

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

          Oh, my bad then.
          I actually saw some people solving with some similar solution (turning the problem into some quadratic equation) in the contest. So I felt lazy to carefully read it. My bad

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

speedforces and implementionforces

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

For problem D div 2, I don't know what went wrong with my submission at 135395991 (it received a Query Limit Exceeded), since I had the same approach and even took some time to reduce 2 binary searches down to 1. I then changed my binary search implementation (135421249), and got Accepted, but I still don't know why my old implementation of binary search used much more queries though.

I hope somebody could tackle my code and find out what's wrong with my old implementation. And I still feel pretty bad for having been so close to D, I could've been promoted to pupil. But overall, nice problem and great contest!

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

    What you were doing was an incorrect implementation of binary lifting.

    The idea of binary lifting is that you have a condition that will be fullfiled by jumping a values less or equal $$$x$$$, but not bigger or equal to $$$x + 1$$$ (in your case, that condition is that the query from $$$1$$$ to $$$n-x$$$ to get the entirety of the reversed segments). But since $$$x$$$ can be represented in binary, we can progressively make jumps in all powers of two in decreasing order.

    For example, lets say that $$$x = 1011001_2$$$. Our program could first try $$$1000000_2$$$ and it would work, so we jump that ammount. Then, it would try $$$100000_2$$$ and it would fail, because $$$1100000_2 > 1011001_2 <=> 1100000_2 > x$$$. Then it would try $$$10000_2$$$ and it will work, because $$$1010000_2 <= 1011001_2 <=> 1100000_2 <= x$$$. This algorithm will find the exact x we're looking for in $$$log(n)$$$ steps.

    However, in your algorithm, since youre not working with clean powers of two, you have to keep using the same value until it doesnt fit anymore, but in a case where you would have to use each value exactly once it would waste queries. For example, if $$$x = 111111_2$$$ your algorithm could try $$$100000_2$$$ once, it would work, then it would try it again, it wouldnt work, and then you try $$$10000_2$$$, it works, then you try again, it doesnt anymore...

    That way you end up doing $$$log(n)*2$$$ queries, or $$$60$$$ queries, which doesnt pass.

    Because of the map optimization you did preventing the same query to be answered twice, just changing to powers of two already works: 135543351, but ideally you should not have the while in the first place: 135553555

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

      Woah, I've been implementing binary search like this for ages and never realized what I did was wrong. Today I learned something, thanks for pointing out.

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

Video Editorial of A

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

For Div1D, we can just do dfs and use map to store answer.

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

    I passed with the same method

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

      The complexity is similar to the std.

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

        Certainly. I just make every character as the next appeared one in the LCS then it passed

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

I seem to get a runtime error for Div1C, which I can't reproduce locally for the same test case- anyone have ideas on what could be wrong?

https://mirror.codeforces.com/contest/1588/submission/135533102

UPDATE: I was able to edit the logic for modifying the map to get A/C but unable to see what the issue was. New submission- 135560689

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

I see... you guys have developed a new LaTeX formula usage.

It's normal for beginners to not use $$$\log$$$ instead of $$$log$$$. But when I see lonely =s and <s are excluded from the great union form by the $$ delimiters, my eyes blurred, poor little symbols.

Things all changed when you wrote binomial coefficients as $$$\Large (_2^{k - j + 1})$$$, a very impressive and revolutionary act. Now I can write Stirling numbers so easily: $$$\large [_2^{k - j + 1}]$$$ and $$$\large \{_2^{k - j + 1}\}$$$, forget about \brace and \brack, great job guys!

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

Bonus! I used Dinic to solve problem C!

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

For 1584D - Guess the Permutation there is easier solution. Instead of using [x, n] ranges, let's take a look at ranges [1, x].

  • Notice, that starting from k number of inversions never change, because all numbers after k is greater than k, so they can't produce any inversions. So, using binary search over x we know k after around 30 queries.
  • Then, notice that new value at position k is actually j, because this is how we reverse things. And before it there is exactly (k — j) numbers which are greater than j. So, if we ask [1, k — 1] we get number (k — j) and it's easy to derive j from it. This require single additional query (if you don't cache results).
  • Notice that for [1, j — 1] works same approach: at position (j — 1) stands i. And before it there is exactly (j — 1 — i) numbers which are greater than i. So if we ask [1, j — 2] we get number (j — 1 — i) and it's easy to derive i from it. This require two additional queries in case when range [j, k] is not short.

So, it require around 33 queries in total. No binomial coefficients involved, no quadratic equations envolved.

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

Different algorithm for 2D:

  • First do the query [1,n] and find the total inversion $$$TS$$$.

  • Lets try to find the position of $$$j$$$.

  • Lets do query in the form [1,x]. Suppose we get $$$S$$$.

  • How to know $$$x<j$$$ or not?

  • If $$$S==TS$$$ it definitely is not.

  • If $$$S==0$$$ it definitely is.

  • Otherwise lets try to find a integer solution to the equation $$$\frac{p*(p-1)}{2}=S$$$ for $$$p>1$$$

  • If we can't find a solution then definitely $$$x>=j$$$. If we can find a solution , it is likely that $$$x<j$$$ but we can't be sure because there may also be a solution to $$$\frac{p*(p-1)}{2}+\frac{q*(q-1)}{2}=S$$$ where $$$p>1$$$ and $$$q>0$$$. So lets do the query [1,x-p+1] and get the sum $$$QS$$$.

  • If $$$QS==0$$$ then $$$x<j$$$. And we can find $$$i=x-p+1$$$. Once we find the value of $$$i$$$, we can later use it to check whether $$$x<j$$$ or not by checking whether $$$x-p+1==i$$$ or not.

  • Otherwise $$$x>=j$$$ and we continue with binary search.

  • According to my intuition there are not so many cases we would encounter where we can find integer solutions to both the equations $$$\frac{p*(p-1)}{2}=S$$$ and $$$\frac{p*(p-1)}{2}+\frac{q*(q-1)}{2}=S$$$ for $$$p>1$$$ and $$$q>0$$$. Thus we won't be doing double queries that much, at least until finding the value of $$$i$$$, after which we won't be needing double queries any more. And we have 40 queries which means 7-8 extra queries.

**I have not proven the correctness the algorithm yet and there may exist hack cases

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

    This is exactly what I did. I'm glad I found someone else with the same solution as me lol. As you said, I don't know how to prove it though.

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

div. 2 E $$$c_i^l = a_i^l - a_{i - 1}^l + \ldots + (-1)^{i-1} \cdot a_1^l = a_{l+i-1} - a_{l+i-2} + \ldots + (-1)^{i-1} \cdot a_{l} = c_{l+i-1} + (-1)^{i-1} \cdot c_{l - 1}$$$

Doesn't $$$c_i^l$$$ mean $$$c_{l+i-1}$$$ ?

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

    Yes, $$$c^{l}_{i} = c_{l+i-1}$$$. I think you might be getting confused as to why there is that $$$(-1)^{i-1}\cdot c_{l-1}$$$ term in the end. Notice how the last term in the expansion of $$$c^{l}_{i}$$$ is $$$(-1)^{i-1}\cdot a_{l}$$$, not $$$(-1)^{l+i-2}\cdot a_{1}$$$ :

    $$$c^{l}_{i} = a^{l}_{i} - a^{l}_{i-1} + ... + (-1)^{i-1}\cdot a^{l}_{1} = a_{l+i-1} - a_{l+i-2} + ... + (-1)^{i-1}\cdot a_{l}$$$ (As written in the editorial)

    We can write the above as:

    $$$c^{l}_{i} = (a_{l+i-1} - a_{l+i-2} + ... + (-1)^{l+i-2}\cdot a_{1}) - ((-1)^{i}\cdot a_{l-1} + (-1)^{i+1}\cdot a_{l-2} + ... + (-1)^{l+i-2}\cdot a_{1}) = c_{l+i-1} - (-1)^{i}\cdot c_{l-1} = c_{l+i-1} + (-1)^{i-1}\cdot c_{l-1}$$$

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

What is "efinegraph" in Strange LCS ?

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

    nothing, that's most likely just a typo version of "define graph".

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

Problem C can be done in O(N) without sorting. Code

Explanation : Just count the frequency of each number then for each number it's enough to check this condition :

extra[x] + cnta[x] >= cntb[x]. (extra[x] here defines frequency of x-1 left over in the array a.)

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

1589E - Game with Stones can be solved using "Venice Technique" or whatever you call it. 135753412

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

    Hey can you please explain the idea. I find the code a bit difficult to understand

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

imo it would be better to make elimination rounds with full tests and not pretests, because it isn't just matter of rating, many people can be eliminated because of terrible pretests like in this round.

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

Just wondering for Eligible Segments. You have a constraint that $$$R$$$ being changed by $$$10^{-2}$$$ will not affect the answer. How did you write the validator to check that hacks do not violate this constraint?

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

    Let's just check, that the answers for $$$R - 10^{-2}$$$ and $$$R + 10^{-2}$$$ are equal.

    The answer increases then $$$R$$$ increases, so this works.

    I hope it was a good way to avoid double issues.

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

Hey guys, in problem Div2-E/Div1-C, I'm getting MLE on test 37 here and I'm not able to see why. Can someone help me?

Code: https://mirror.codeforces.com/contest/1588/submission/135797278

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

    I guess deque takes up a lot of space. From what I've read, in libstdc++ it allocates memory in blocks of 512 bytes. Testing deque<int> on codeforces, it seems that even when declared empty in a global variable it takes up a huge amount of memory (around 600 bytes), and if you add even one element it's size becomes around 1100 bytes.

    Changing deque to vector results in AC: https://mirror.codeforces.com/contest/1588/submission/135885469

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

      That's exactly it, tnx a lot!!

      The implementation with deque takes more than 10 times more memory than the vector one.

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

no one's wondering where the tutorial of 1588F - Jumping Through the Array goes?

or someone just gives a short explanation

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

Could you please publish some STDs to make the solution easier to understand?

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

I have another idea for 1589E - Game with Stones 136087401. Find all l for r(r -> count(l)). s[i] = k * x[i] + b. After taking i-th rock apply k_new = -k, b_new = k * b + s[i], and lets encode every s[i] as x[i], so after taking j-th rock, k * x[i] + b — gives addition for every rock in [i, j], and then delete every x, s.t. k * x[i] + b < 0. Because k = +-1, we can find such x, kx + b = 0, and then xs that we must delete will be x + dir, x + 2 * dir, x + 3 * dir, etc. For every rock we must add count of xs that kx + b = 0

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

Div 1D can be solved in $$$O(|\Sigma|^2 2^n)$$$.

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

In editorial of 2E, shouldn't it be $$$C^l_i<0$$$ if and only if $$$C_{l+i−1}<(−1)^iC_{l−1}$$$ instead of $$$C^l_i<0$$$ if and only if $$$C_{l+i−1}<(−1)^{i-1}C_{l−1}$$$

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

can anyone tell whats wrong in my approach for problem C. Two Arrays .... I am first matching all the already matched elements of array b with array a and deleting them simultaneously from both arrays. Then I am matching the remaining elements of array a with remaining elements of array b by adding 1 to them...If some element is not matched I am printing "NO". Else after end of loop I am printing "yes".

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

    here is my code...136264178

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

    For 3,4 and 2,3 you can see that 2 will match to 3 and the other 3 will match with 4. In your solution 3 and 3 will match and live happily ever after but what about 2 and 4?:)

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

For Div2E. the problem reduces to finding the nearest position on suffix which is strictly less than some $$$x$$$. Can some one please explain in a bit more detail as to how to do it?

→ Reply