[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,**: Now the [editorial will be delayed. We didn't have much time to prepare mainly because I was in hacker cup..](https://atcoder.jp/img/agc016/editorial.pdf) (check page 5) is ready except for E.↵
↵
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>↵
↵
↵
[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
↵
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>↵
↵
