maroonrk's blog

AtCoder Grand Contest 063 Announcement
By maroonrk, history, 17 months ago, In English

We will hold AtCoder Grand Contest 063. This contest counts for GP30 scores.

The point values will be 300-600-800-1200-1400-1700.

We are looking forward to your participation!

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

Comments Comments (14)
| Write comment?
»
17 months ago, # |
  Vote: I like it +49 Vote: I do not like it

Hope I can solve two problems!

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

Why this fails for problem B?

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

C is almost the same as this problem

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

    Can't see the problem without login

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

      You are given sequences of non-negative integers: $$$A=(A_1,A_2,\cdots,A_N)$$$ and $$$B=(B_1,B_2,\cdots,B_N)$$$。

      At first, $$$A_i=i$$$。 You can make operations for $$$2N+1$$$

      times:

      Operation 1: choose $$$x$$$, for every $$$i$$$, replace $$$A_i$$$ with $$$A_i + x$$$

      Operation 2: choose $$$x$$$, for every $$$i$$$, replace $$$A_i$$$ with $$$A_i \bmod x$$$

      you need to make $$$A=B$$$.

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

    Yes,yes,but this one is stronger. A direct copy will lead to one more operation.

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

In problem $$$B$$$ I firstly defined good subsegment incorrectly. It was "for all prefixes for all $$$i$$$ number of $$$i$$$ is greater or equal to number of $$$i + 1$$$". Surprisingly, it failed only half of tests. How to implement it? I scan from left to right and have starting positions of good segments, which end up in current position. I append to them new number. Some of them become not good. Those are suffix of segments (segments with rightmost left end). So this is like stack. To check, if top segment on stack should be removed, I have to ask number of $$$i$$$ and $$$i + 1$$$ on segment. For all $$$i$$$ I precalculate set of positions and do set::lower_bound to find them (Can we do it faster? I doubted, that it can get TL, but it did not). Finally, if current element is $$$1$$$, push this position to stack.

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

In the editorial for problem B, it is stated that

Suppose $$$a$$$ is generatable, and let $$$(1,2,…,k)$$$ be the maximum-length sequence of consecutive numbers starting at the rightmost $$$1$$$. No deletion will be performed to the right of this position until this $$$1$$$ is deleted (since we are looking at the rightmost $$$1$$$). Thus, if ($$$1, 2, ..., k'$$$) is the sequence that is deleted when this $$$1$$$ is deleted, then $$$k' ≤ k$$$ holds

But in this sequence for example: Let $$$a = 1, 2, 1, 2, 3, 3, 4, 5$$$

Then :

  • "$$$a$$$ is generatable"

  • $$$1, 2, 3$$$ is the "maximum-length sequence of consecutive numbers starting at the rightmost $$$1$$$". So now $$$k = 3$$$

  • Then I delete this sequence and left with $$$1, 2, 3, 4, 5$$$. So now "$$$(1,2,…,k′)$$$ is the sequence that is deleted when this $$$1$$$ is deleted". In this sequence $$$k' = 5$$$

But in the last statement, it is said that "then $$$k' ≤ k$$$ holds." Which is not true

Am I missing something here?

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

    I think the "$$$(1,2,...,k')$$$ is the sequence that is deleted when this $$$1$$$ is deleted" means what continuous subsequence was also deleted when we deleted $$$(1,2,...,k)$$$. For example, the continuous subsequence $$$(1,2)$$$ also got deleted when we deleted $$$(1,2,3)$$$, which means $$$k'=2$$$ for this particular case.

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

Problem D in tasks: Many CRT,and in hints:Many CRTs

→ Reply