maroonrk's blog

By maroonrk, history, 8 months ago, In English

We will hold AtCoder Regular Contest 173.

The point values will be 400-500-600-700-800-1200.

We are looking forward to your participation!

  • Vote: I like it
  • +135
  • Vote: I do not like it

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

Excited!

»
8 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Excited!

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

Too hard. Only solved ABC.

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

problem B is very simplified version of this problem (104730J - Путёвка на Острова Кука) this problem asks you to split 3n points in n non-degenerate triangles or report that it's impossible

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

Damn I got WA*2,AC*142 on E... ): ): ):

»
8 months ago, # |
  Vote: I like it -92 Vote: I do not like it

ABCD is so easy (for me) that I solved them in 1 hour.

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

    How to do D?

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

      Answer is Yes when the graph is strongly connected and either both positive and negative cycles exist in graph or neither of them exist in the graph.

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

        And the graph is always strongly connected I believe. It says it in the problem given any node s you can reach node any node t which basically describes strongly connected graph.

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

I tried doing C by binary search and segment tree, but got TLE. I wanna know does the intended solution uses sparse table instead?

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

    Oof, and here I was thinking that Sqrt-Decomposition could work :3

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

      No, it only needs std::set and a little bit observation.

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

        Thanks, will try to figure that 👍

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

      Sqrt how? Did you have any idea?

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

        My approach could be implemented with segment trees as well. I'd just scrapped them earlier for some reason so went with SqrtDecomposition.

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

    This task has simple implementation.

    Assume, we are looking at some element $$$x$$$ in the permutation. There are elements that are smaller that it — we will mark them as $$$-$$$, and elements, that are greater — we will mark it as $$$+$$$. So we have this picture: $$$[-+--+x++--+-]$$$.

    Now, when the answer is greater than $$$3$$$? Well, if we have $$$[-x+]$$$ or $$$[+x-]$$$ or $$$[-+x]$$$ or $$$[+-x]$$$ or $$$[x-+]$$$ or $$$[x+-]$$$. When the answer is greater than $$$5$$$? If we have $$$[-+x-+]$$$ or $$$[+-x+-]$$$ or $$$[+-+-x]$$$ etc.

    So, now we see, that we need to find the smallest segment, that has $$$--$$$ or $$$++$$$ at one of its ends. We can stand at $$$x$$$ and just move to some direction and calculate number of $$$-$$$ and $$$+$$$. Once these numbers are not equal, we found a candidate for answer for this direction. Notice, that answer can be in one of two forms: $$$[...x]$$$ and $$$[...x.]$$$, where $$$.$$$ is one element. But the second form can't be for first and last elements, so we need to "if" it.

    Why can we just iterate, without any optimization? Well, I don't know. I first tried to create a bad test, and thought, that worst answer is $$$O(n \cdot \log{n})$$$. Then I whote a stress, which, if I understood correctly, showed even $$$O(n)$$$.

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

      Thanks, I think I had the same idea, but struggled a lot in debugging the ifs. I will try it again anyways.

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

      Instead, you can store a set $$$S$$$ of $$$i$$$ such that $$$sign[i] = sign[i+1]$$$, and use the $$$j \in S$$$ closest to the left and the right of the index being considered. You can keep track of that set by testing positions in increasing order of $$$p_i$$$. You should also first test that $$$sign[x-1]$$$ and $$$sign[x+1]$$$ are opposite signs when testing $$$x$$$.

      Of course, the first and last positions are special cases that can be solved by iterating.

      This way the solution is clearly $$$O(n \log n)$$$ without much thinking/stress testing.

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

      I think it is actually O(n), and it is what I did in contest as well.

      The main observation is that if you an $$$x$$$ where the answer is very large, this means in your notation it will look like $$$[...-+-+-+x-+-+-+...]$$$ with many alternating + and -. But then, for each of those + or -, notice that the answer is always EXACTLY 3. For example, if I am looking at $$$-+-$$$, then the + has two numbers around it that are provably smaller, so if I take that window of 3, the + cannot be the median.

      This means that you get an amortized O(n) solution if you just implement it in the most straightforward way!

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
8 months ago, # |
  Vote: I like it +24 Vote: I do not like it

As many people just kept guessing and got the key conclusion in problem E, it would be much more interesting if we are actually required to prove the conclusion, but this can't be done in reality anyway. Still it's a very good problem and I liked the way to get to the result step by step.

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

    What was your approach to E? I backtracked $$$n=6$$$, found out that we cannot construct $$$2^6-1$$$, then gave up lol.

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

      The only countercase is when $$$n=6,10,14,\cdots$$$, in which case you can't use all elements.

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

    I can confirm that spam submitting with random condition on N without proving works

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

    can you please explain me the solution to E. I can not understand the editorial.

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

imo, B<C<<A

btw, AC A on 118min is NICE!

»
8 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Out of first three problems, the problem A was the hardest for me. It has two topics, which I implement worst at all — the digit dp and the binary search.

I hope, one day, I will learn how to implement them.

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

    Actually,neither of the topics is required. However,I do agree that A is harder than C,for i spend 80 minutes on A and only 30 minutes on C.

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

      How did you solve A if you didn't use digit dp + binary search?

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

        https://atcoder.jp/contests/arc173/submissions/51137481 Hi bro can u pls tell why this is giving RTE for A.. its working fine on local

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

          There's too much code to debug but I noticed you're keeping hi as 1e13, that's not sufficient, you need to keep hi as 1e18

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

        First, total number of neq numbers is $$$9^i$$$ for a number with $$$i$$$ digits. So you can determine the number of digits of the answer. Subtract the number of numbers which have fewer digits than the answer from $$$K$$$.

        Then determine the number for each of the digits. For the $$$i$$$ th digit, iterate through $$$0$$$ to $$$9$$$, excluding the number which equals to the previous digit. Each number gives a contribution of $$$9^{i-1}$$$. Subtract it from $$$K$$$,until if subtracted, $$$K$$$ becomes smaller than $$$0$$$ and you get the answer for the $$$i$$$ th digit.

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

    I never use digit dp in normal form because you can always fix the first smaller digit and then write dp without any restriction.

    anyways this problem is much more easier check this code

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

How to solve B?

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

After bricking miserably on A and B, I proceeded to misread D and didn't realize that the edges were directed. D'oh!

That being said, I solved C by wishfully thinking that the sum of answers are not that large (probably in the order of $$$O(n)$$$). Checking if the answer could be a certain value $$$v$$$ is quite simple: if the current element is $$$x$$$, we represent each element $$$y$$$ as the sign of $$$y - x$$$. Then, all the subarrays with length $$$v$$$ must have sum $$$0$$$. Notice that all subarrays will have sum $$$0$$$ if the leftmost subarray has sum $$$0$$$ and the other subarrays are a cyclic shift of that subarray. We can check this by maintaining a hash in a segment tree.

Can anyone prove why the sum of answers is small, though?

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

    The answer consists of 3 parts:

    1. $$$P_1$$$ and $$$P_n$$$ $$$\implies$$$ just two such points, the sum bounded by $$$2n$$$.
    2. $$$P_i$$$ being local max or min on segment $$$[P_{i - 1}, P_{i + 1}]$$$ $$$\implies$$$ answer for such points is $$$3$$$, so the sum is bounded by $$$3n$$$.
    3. The remaining points $$$\implies$$$ the only non-trivial case.

    Consider subsequence of all points falling under case (3). Let $$$P_a$$$ and $$$P_b$$$ be two such consecutive points. Then, it can be proved that answer for both of the points does not exceed $$$b - a + 3$$$. Consider e.g. case $$$P_a < P_b$$$. Since $$$P_b$$$ does not fall under case (2), we have either $$$P_{b-1} > P_b$$$, or $$$P_{b+1} > P_b$$$. Consider e.g. case $$$P_{b+1} > P_b$$$, then $$$P_a < P_b < P_{b+1}$$$. This implies that $$$P_a$$$ cannot be the median of both segments $$$[P_a, \dots, P_{b-1}]$$$ and $$$[P_a, \dots, P_{b+1}]$$$ simultaneously. So, one of these segments would give the answer for $$$P_a$$$. (If the segments have even length, you might add element $$$P_{a-1}$$$ to them to obtain segments of odd length).

    So, the answer for all such $$$P_a$$$ does not exceed the doubled distance between the leftmost and the rightmost of them, plus a constant overhead for each pair of consecutive such points. In total this is bounded by $$$5n$$$.

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

how to solve task A

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

    Write a function which given a number K, let's you know how many numbers <= K exist which are Neq numbers. You can use digit dp for it.

    Next, use binary search on this function to find the smallest number which gives K as the answer.

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

      Is there any standard approach to solving problems like A?

»
8 months ago, # |
  Vote: I like it -33 Vote: I do not like it

Corner cases are fucking.

I think these tests should be put in the samples.

My solution for problem C is almost correct, but I didn't consider the case that $$$i = 1,n$$$, I got no points.

I hate this contest.

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

I wrote an $$$O(m^2)$$$ sulotion for D and it got TLE at first. https://atcoder.jp/contests/arc173/submissions/51130486

»
8 months ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

I think B can actually be solved when $$$N = 10^5$$$. Correct me if I was wrong.

Spoiler