Pyqe's blog

By Pyqe, 13 months ago, In English

2A. Goals of Victory

Author: nandonathaniel
Developer: nandonathaniel

Tutorial

2B/1A. Helmets in Night Light

Author: ArvinCiu
Developer: gansixeneh

Tutorial

2C. Joyboard

Author: Pyqe
Developer: gansixeneh

Tutorial

2D/1B. Effects of Anti Pimples

Author: Pyqe
Developer: Pyqe

Tutorial

2E/1C. Autosynthesis

Author: Pyqe
Developer: Pyqe

Tutorial

2F/1D. Lexichromatography

Author: Pyqe
Developer: Pyqe

Tutorial

2G/1E. Ball-Stackable

Author: Pyqe
Developer: Pyqe

Tutorial

1F. Indefinite Clownfish

Author: Pyqe
Developer: Pyqe

Tutorial

1G. Clubstep

Author: Pyqe
Developer: Pyqe

Tutorial
  • Vote: I like it
  • +107
  • Vote: I do not like it

| Write comment?
»
13 months ago, # |
  Vote: I like it +9 Vote: I do not like it

[Reposting] for anyone interested in video editorials for A, B, C and D: https://youtu.be/3gP74cSjhwg?si=bl1lMboWq4O2dPgg

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

A small correction for A: it has to be the negative of the sum of the present teams, not just the sum.

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

    Whoops, sorry about that! It's fixed now

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

Good Editorial!

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

In div1-D, did anyone try directly calculating unequal part ?

It should be for these 3 cases: inequality at odd occurrence of value, at even occurrence, and inequality due to insufficient length

My submission I've added comments.. Answer differs by one, struggling to find the reason. Would highly appreciate if anyone can help

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

    In case it gives any clue..

    I had checked for this particular test-case, execution doesn't get to 3rd case.. gets to first & second

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

In problem 2E, is it neccessary to push the parent vertex immediately if the current vertex is white? If it is, can anyone explain it for me? I've tried to push the vertex only when it's indegree is 0 and get WA on test 4.

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

    I have the same issue as yours and I am also confused. Why would this change the answer? Does the order in which the vertices are pushed change the answer? I thought we were doing a BFS except that we stop when we encounter a cycle.

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

      Actually, I now do understand why my solution didn't work. Try this test case:

      6
      2 3 4 1 2 3
      

      A possible solution is

      3
      1 2 3
      

      The problems with pushing the vertex into the queue only if it's indegree is 0 is that some of the vertices in the cycles have to be assigned "black" before we iterate through the cycles.

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

    It's not really necessary to handle it like that. But I chose to do it like that in order to easily handle the case where the colours in the cycle is forced (it happens when at least one child of a vertex in the cycle is white).

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

How to solve problem 2E/1C with 2-sat?I tried a lot of times but still wa on 4. And how to solve it with flow?

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

For problem A it should be negative of the sum.

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

For calculating the equal ways in 1D, if some $$$a_i$$$ occur odd times, impossible to equal, else we can think for each value x, $$$a_{i_1}=a_{i_2}=\dots=a_{i_{2k}}=x$$$, x have k segments $$$[a_{i_1},a_{i_2}]$$$, $$$[a_{i_3},a_{i_4}]$$$,$$$\dots $$$. For all segements, if one contains another, impossible to equal, if two segments for value x and y intersect, their order will be the same. Only need to use some easy data structure to search the segments.

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

Can Anyone share some problems similar to 2-D.

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

Can Someone Explain this part in more detail~ In order to calculate g(w) for all desired values of w , we need to iterate the elements of a from the biggest value to the smallest value. Each element we iterate, we iterate every index that is a factor of the index of the current element and mark those indices as group 1 while we keep track of the value of c .

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

Very good problems!

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

I really enjoyed the problems ! They felt beautiful and creative. Congrats to the authors !

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

I think there is a typo in 1877B — Helmets in Night Light tutorial.

residents with the smallest values of ai first. Using the fact that ai ≥ 1, we can deduce that we will always have a resident with an available share.

Should be

residents with the smallest values of bi first. Using the fact that ai ≥ 1, we can deduce that we will always have a resident with an available share.

Values of b represent the cost, and since all ai >= 1 we can always have that cheap person to tell atleast 1 other person.

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

    That's right! It was a mistake. It should be fixed now

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

Is Problem G a Geometry Dash reference? Lol.

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

    Yes, it is! Glad you noticed :D

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

    Yeah, I actually came up with the idea of that problem when playing an insane demon level in the game lol

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

    You guys should make more problems like this lol, would be interesting to see

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

UPD: Never mind

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

Alternative solution for div2-D:

For each element $$$a_i$$$, define the value $$$m_i$$$ — maximum in $$$a$$$ over all indices which are multiples of $$$i$$$.

Consider that some elements are colored black. If we suppose that the answer for such coloring is $$$m_i$$$, then the answer does not change while coloring black other indices $$$j$$$ such that $$$m_j \leq m_i$$$, so the answer to the problem is $$$\sum\limits_{i = 1}^n 2^{i-1} \cdot m_i$$$ over a sorted array $$$m$$$.

To calculate $$$m_i$$$, let's use the idea of sqrt decomposition:

  1. If $$$i > \sqrt{n}$$$, then we can go over all multiples $$$i, 2i, ..., \lfloor\frac{n}{i}\rfloor i$$$ and find $$$m_i$$$ in $$$O(\sqrt{n})$$$.
  2. If $$$i \leq \sqrt{n}$$$, then let's use dynamic programming. Define $$$dp_{i,j}$$$ as the maximum value over indices $$$i, i + j, i + 2j, ...$$$. To calculate this, the transition between states is quite simple: $$$dp_{i,j} = max(a_i, dp_{i + j,j})$$$. After that, the desired value for $$$m_i$$$ will be stored in $$$dp_{i,i}$$$. Since we only need $$$j \leq \sqrt{n}$$$ to calculate the answer, all the values can be obtained in $$$O(n\sqrt{n})$$$.

Therefore, the total complexity is $$$O(n\sqrt{n})$$$.

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

    then we can go over all multiples $$$i,2i,...,⌊n/i⌋i$$$ and find mi in O(n−−√)

    This takes $$$O(n/i)$$$, so $$$O(n\log n)$$$ in total

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

      Oh, you're right, thank you!

      So there's no need for dp, and the solution is even simpler and more efficient.

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

        i came up with this solution too, tbh i find this much more intuitive/simpler than the solution in the editorial

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

    Bro u made it more difficult:P

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

I have an alternative solution for G that runs in $$$O((n+q)(\log{n} + \log{\max{x}}))$$$.

Same as editorial, to answer a query $$$(l,r,x)$$$, we take $$$x$$$ and run through gates $$$r$$$ to $$$l$$$ sequentially, where gate $$$i$$$ is the function $$$f(x)=\min{(a_i,\lfloor \frac{x+a_i}{2} \rfloor)}$$$. We can retrieve the answer after computing the sum of results after running each gate.

Suppose all queries have $$$r=n$$$. Then we can get some solution sketch like this: gradually increment $$$x'$$$ from $$$0$$$ to $$$10^9$$$, while maintaining $$$ans_i$$$ for $$$1 \le i \le n$$$, where $$$ans_i$$$ is the result of $$$x'$$$ after running through gates $$$n$$$ to $$$i$$$. Then, to answer a query $$$(l,r,x)$$$, we just pick the moment we have $$$x'=x$$$, and we take the sum of $$$ans_i$$$ for $$$l \le i \le n$$$.

To maintain $$$ans_i$$$, we can store a set of active gates, which are gates $$$i$$$ that have $$$a_i \le ans_{i+1}$$$. Once a gate is activated, it will never be deactivated. Obviously, if gate $$$i$$$ is not active, then $$$ans_i = ans_{i+1}$$$. So by knowing positions active gates, we can divide the $$$ans$$$ array into continuous blocks of equal value. Now, when we increase $$$x$$$ by $$$1$$$, we update the $$$ans$$$ array in a similar fashion as how we would do $$$+1$$$ on a big integer represented in binary. This takes $$$O(1)$$$ amortized. We then check, for each changed value of $$$ans_i$$$, whether it would activate some gates. This can be detected by RMQ, and we can have a $$$O(\max{x}+n\log{n})$$$ idea.

To improve, we can compute the next value of $$$x'$$$ which either activates a gate or we need to answer a query of that value, instead of increasing $$$x'$$$ one by one. This improves the time complexity to $$$O((n+q)(\log{n} + \log{\max{x}}))$$$.

Finally, let's think of how to also handle queries with arbitrary $$$r$$$. Let's say we have a query $$$(l,r,x)$$$, If at any moment we manage to have $$$ans_{r+1}=x$$$, then we are very happy as we can get what we want by just computing sum of $$$ans_i$$$ for $$$l \le i \le r$$$. So we can just modify the previous solution to detect the next important $$$x$$$ that either activates a gate, or hits some $$$ans_{r+1}=x$$$.

But there might be some ugly situation where we have cooked $$$x'$$$ up to $$$10^9$$$, but $$$ans_{r+1}<x$$$ still holds. Now, the funny trick is that we realise at this moment, all queries with $$$r=n$$$ are already answered, and gate $$$n$$$ is already activated. So, we can simply pretend gate $$$n$$$ never exist, and repeat our process with the new $$$x'$$$ to be $$$ans_n$$$. By the time we removed all the gates, we would have already found out the answer for all queries.

The data structure details are not too ugly, but it took me a long time to implement...

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

In 2E/1C, "For each white element, there cannot be any white element with a value equal to the index of that black element.", should it be "For each white element, there cannot be any white element with a value equal to the index of that white element."

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

Could anyone please tell me the logical difference between these codes: 237306441 and 237304555? Both codes have the same logic.

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

can someone explain why I am getting TLE on this submission_A?