We will hold AtCoder Beginner Contest 209.

- Contest URL: https://atcoder.jp/contests/abc209
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210710T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: blackyuki
- Tester: penguinman
- Rated range: ~ 1999

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

SpeedCoderHow to solve E and F?

Solution for E:

Editorial (don't look at the sample code, it's broken rn)

Basically, you convert the strings into a graph, where a node connects $$$i$$$ and $$$j$$$ if $$$s_j$$$ starts with the same $$$3$$$ characters that $$$s_i$$$ ends with. Then you do topological sort to get the order you do dp updates, and then do dp on the graph.

Can you share your code? The editorial uses a different method than Toposort. edit: I was unfamiliar with kahn's algo for toposort.

I died in the process to get my solution for E work even on samples. :waturr:. How to do E ?

How to solve E please ;.;

I had the intuition to form a directed graph in E. Can't think of anything else.

Yes, I was also going on that path, from a node we need to see whether there is a dead-end node (from where no further words exist such that they start with the last 3 characters) at an odd distance, but I was not able to optimize this processes.

I also had the intuition to form a graph then construct the edges in 52^5(forgot to remove the useless letters in-between) instead of 52^3, such a silly mistake

Can you share your process? Thanks

I only got to that part

Exactly same idea as E 787C - Berzerk

The editorial of F mentions

insertion dpa new technique to me. So I googled it to find some good CF blog. The results google gave were mindblowingP.S : Open at your own risk.

The search results depends of your country and of your own search history, I got results in french, what do most people see?

Something sacred.

If I had to use one word: po*n. I hope you got the meaning. Man, my father came just when I opened the link. Pray for me.... @DontLookBack @bcollet and everyone who reads it.

Lol, try searching broken profile dp

It's a literal translation from Japanese term 「挿入DP」, so there's no doubt the term is not known. I'm curious, what is this kind of DP called in English?

That was what I was trying to find out :)

For E, I found the explanation of https://cp-algorithms.com/game_theory/games_on_graphs.html quite useful.

I failed B lol. A lesson learned:

`Yes/No`

letter case matters on Atcoder.I tried SCC + DP on E, but it didn't work for most of the cases (but it worked on samples and my edge cases, I couldn't find a case that it failed on).

Also, chokudai, please fix whatever happened to the sample code in E's editorial (code was accidentally put as LaTeX, so something like

`int`

became an integral symbol).Update: Thanks chokudai!C, what is the proof that we can resort c[] without changing the result?

Suppose A, C are two sequences such that 1 <= A_i <= C_i, A_i != A_j (the two conditions listed in the bullets in the problem statement)

Then if you apply the same permutation to A and C, they continue to satisfy the two conditions.

let P be a permutation which gets from C to sorted C, let $$$l_1,...,l_n$$$ a solution to the original problem, a permutation of l according to P will give you a solution to sorted C and conversely you can get back a solution to C from solution to sorted C.

it's a one-to-one function between the two set of solutions so they have same size.

Suppose at some i array C has value C_i. Now let there be x elements in the array C (other than i) whose value is less than or equal to C_i. This implies the number of possible values for i will be reduced by x which is (C_i — x).

Notice when we sort x did not change, so our answer won't change at all.

Plus we'll also get the value of x (which is i-1) effortlessly as a bonus ;)

I had the following idea for E.

for every i there is a directed edge to j such that pref_j == suff_i (considering only 3 chars). Now from every i we'll go to its children in following priority -

base case :- if for some i if there are no child nodes then 1st player will win when he'll start from i.

But this didn't worked. Is any issues with this approach? Can anyone point out my mistake? Thanks in advance.

PS : here's the submission in case you want to see the implementation for errors or something Submission

notations used:- 0 -> loose,1 -> draw, 2 -> win

One thing that I faced is, In this approach total no of edges in your graph in worst case is around N^2 which will not fit in time limits. Refer the editorial for optimal way of graph construction.

In that case shouldn't it give TLE rather than Wa? Can anyone help me with a test case where it fails?

Thanks in advance :)

The sample code in editorial E was fixed. We are sorry for the poor work.

Can you please upload the test cases for this contest in dropbox.

Thanks!

E can also be solved with eliminating vertex with 0 outgoing edge, much like agc027_c.

Could anyone tell me whether we can solve the task E with Trie?

How to solve C if the condition is $$$A_{i} \neq A_{i + 1}$$$ instead of $$$A_{i} \neq A_{j}$$$?