maroonrk's blog

AtCoder Regular Contest 157 Announcement
By maroonrk, history, 22 months ago, In English

We will hold AtCoder Regular Contest 157.

The point values will be 300-500-600-600-700-900.

We are looking forward to your participation!

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

Comments Comments (30)
| Write comment?
»
22 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Same day with Codeforces Round 853 (Div. 2) with 35 minutes break. Hope I'll not be too tired to take part in both contests.

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

A question: why ARC contests are held on Saturdays recently? I'm a little confused since they were held on Sundays before.

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +80 Vote: I do not like it

    There is no deep reason behind it. When choosing a date, I check available dates and ask writers their preferences. Also, I don't think there is a strong tendency toward Saturday. It's just that the recent two ARCs are on Saturday.

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

For every ARC, I pay attention to whether the first question is worth 300 points or 400 points. This time, it is 300. Thanks.

→ Reply
»
22 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Scoring distribution looks nice:)

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

RP++

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

RP++

→ Reply
»
22 months ago, # |
  Vote: I like it -20 Vote: I do not like it

have got lots of penalties :C

also find C and D have similar statement :)

→ Reply
»
22 months ago, # |
  Vote: I like it -15 Vote: I do not like it

omg XY Round

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

Is the Writer a fan of sex chromosome? There are much XY in problems! By the way, these remind me of the biological knowledge I have learned!

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

It's AtCoder Regular Corner-case again.

→ Reply
»
22 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Finally get a minor +8 rating.

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

New writer, nice round.

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

D: My solution works in 5*10^8 heavy operations. Have no idea why it passed.

E: I felt like my solution works in 10^12. Definitely had no idea why it passed during the contest. Realized it only afterward.

Good round, but I feel like a cheater :) For me it was yoloforces.

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

    E: doesn't your solution work in sum over all vertices (leaves in the left subtree) times (leaves in the right subtree)? If so, it is clearly at most (number of leaves) choose 2 per test case.

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

      Yes. Indeed. But for some reason, I did not understand it during the contest. even though I specifically counted the number of leaves in subtrees and I knew this idea before. Probably my brain was just not working during the contest.

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

B is such a penalty hell. Feel lucky to get AC just on time.

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

How to generate a test in F where the matching characters are far from each other?

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

    It was brute force. I generated all the 3^N instances for small N, and observed the structure of such evil instances. Then, I generated all (or many random) instances with the structure for large N, and pick desired ones. The testcases include instances that need to match characters with distance 14, and I'm not sure whether this is maximum or not under N <= 50.

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
      ← Rev. 3   Vote: I like it +10 Vote: I do not like it

      In the following instances, x/y means both characters are X/Y, respectively, and z means one is X and the other is Y. When N = 4, there is an evil instance "zxyz" appearing in the editorial, for which we need to match two Xs appearing 2nd and 4th to obtain the solution "XX". When N = 8, there is an evil instance "zyyxzyxz", for which we need to match two Xs appearing 1st and 4th to obtain the solution "XYYXX". Most of such evil instances are of form "z*z*z*...*z", where each * is independently xy, yx, xxy, xyy, yxx, or yyx. Thus, I checked many of such instances for large N.

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

Is there a reason why $$$N$$$ is $$$10^4$$$ (e.g. not $$$3000$$$) in problem E? Which solutions does $$$N = 10^4$$$ cut off?

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it +21 Vote: I do not like it

Solved A-D. This time the difficulty is truly "regular".

A: If XX=n-1 or YY=n-1, answer is true, otherwise (XY+YX)>=1 must hold. Also for each block of consecutive Y, it will contribute +1 to both XY ans YX (unless it's on the left endpoint, contribute +1 to YX, or on the right endpoint, contribute +1 to XY) and in every situation |XY-YX|<=1 must hold. In fact, these necessary conditions are also sufficient.

B: First check corner cases for k==0 or k==n. Otherwise, if k<=cnt(x), we need to flip some x to y. If we flip XXY->XYY or YXX->YYX, cnt(YY) will increase 1, and if we flip YXY->YYY, cnt(YY) will increase 2. Therefore we can find all consecutive X-blocks (excludes these on the endpoints), sort them from small to large and fill them greedily. if k>cnt(x). we need to flip all x to y, and flip (k-cnt(x)) original y to x. We can do similarly by finding consecutive Y-blocks.

C: DP. We notice that {1, t+1, (t+1)^2} = {1, t+1, t^2+2*t+1} = {{1, 0, 0}, {1, 1, 0}, {1, 2, 0}} * {1, t, t^2} (where * denotes the matrix multiplication). Let t=cnt(YY) of a single path, and dp[i][j]={sum(1), sum(t), sum(t^2)} where sum is over all paths end at (i, j). When transit from (i-1, j) to (i, j), if s[i-1][j]==s[i][j]=='Y', we need to do a linear transfrom on dp[i-1][j]: from {t1, t2, t3} to {t1, t1+t2, t1+2*t2+t3}, similarly for (i, j-1) to (i, j). Then we just need to let dp[i][j]=dp[i-1][j]+dp[i][j-1].

D: We need to divide the grid into R*C blocks where R*C=cnt(Y)/2, R<=h, C<=w, and each block contains exactly 2 Y. We can do this by 2D prefix-sum and try all divisors of cnt(Y)/2.

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

After reading editorials of problem B, I feel that idea of handling the case when num(x)<k is so clever and impressive! During contest, I didn't find out such a simple "transformation", and failed solving this case. Cool problem and solution, thank you atcoder team!

UPD: Oops, it seems that somehow I read problem B as "find out the longest substring consisiting of letter Y". Now, for case num(x)>k, I use a similar greedy algorithm by changing Y to X from longer segment to smaller segment and get AC as well.

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it +26 Vote: I do not like it

I am still confused about problem D. In the editorial it states "$$$k \le 80$$$, $$$ky \le 6.1 \times 10^7$$$". But why is that true? $$$y$$$ can be up to $$$2000^2 / 2$$$. For example, the number $$$1965600$$$ is suitable. It has $$$288$$$ different divisors which brings $$$ky$$$ to be $$$\approx 5.6 \times 10^8$$$. Am I missing something?

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

screencast

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

Can anyone tell me why my submission https://atcoder.jp/contests/arc157/submissions/39214632 get WA for 8 testcases? Thanks!

→ Reply