AtCoder Grand Contest 016
Difference between en3 and en4, changed 1,405 character(s)
[AtCoder Grand Contest 016](http://atcoder.jp/) will be held on Sunday [(time)](http://www.timeanddate.com/worldclock/fixedtime.html?iso=20170618T2100&p1=248). The writer is [user:sugim48,2017-06-17].↵

[Contest Link](https://agc016.contest.atcoder.jp/)↵

[Contest Announcement](https://atcoder.jp/post/117)↵

The point values will be 300 — 700 — 700 — 1000 — 1400 — 1600.↵

Let's discuss problems after the contest.↵




UPD: Sorry, the editorial will be delayed. We didn't have much time to prepare mainly because I was in hacker cup...↵

I'll add some quick comments here.↵

A.↵

<spoiler summary="Spoiler">↵
Try all characters from 'a' to 'z', and assume that we want to get a string that consists only of this character. What greedy strategy should we follow?↵
</spoiler>↵

B.↵

<spoiler summary="Spoiler">↵
Suppose that there are $C$ colors in total. Then, each $a_i$ must be either $C$ or $C-1$, and it means that the difference between the maximum and the minimum is at most one. Do some case-analysis using this fact.↵
</spoiler>↵

C.↵

<spoiler summary="Spoiler">↵
Suppose that $H$ is not a multiple of $h$. Put a positive number in a cell if its row-number (0-based) is a multiple of $h$, otherwise put a negative number. Can you choose the "positive number" and the "negative number" properly?↵
</spoiler>↵

D.↵

<spoiler summary="Spoiler">↵
Create a new cell that keeps the xor of all elements. Each operation can be considered as a swap between this cell and another element in the sequence. Reduce it to a graph problem.↵
</spoiler>↵

E.↵

<spoiler summary="Spoiler">↵
Can you get YES/NO for a given pair of vertices (or more generally, a given set of vertices) in $O(M)$? Restate it in terms of graphs, then find an $O(NM + N^3)$ solution.↵
</spoiler>↵

F.↵

<spoiler summary="Spoiler">↵
The task is about grundy numbers. Can you get $O(bell_number(N))$ solution by trying all possible grundy-number sequences? Can you reduce it to $O(3^N)$ by DP?↵
</spoiler>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English rng_58 2017-06-19 20:31:26 13 Tiny change: ') is ready except for D.\n\nI'll ' -> ') is ready.\n\nI'll '
en6 English rng_58 2017-06-19 05:01:14 2 Tiny change: 'xcept for E.\n\nI'll ' -> 'xcept for D.\n\nI'll '
en5 English rng_58 2017-06-19 05:00:36 140
en4 English rng_58 2017-06-18 17:01:01 1405
en3 English rng_58 2017-06-18 16:51:59 164
en2 English rng_58 2017-06-17 20:34:44 43 Tiny change: 'ntest.\n\nBy the way, the writer is currently flying.' -> 'ntest.\n\n'
en1 English rng_58 2017-06-17 20:08:56 522 Initial revision (published)