chokudai's blog

By chokudai, history, 3 months ago,

We will hold AtCoder Beginner Contest 209.

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

We are looking forward to your participation!

• +40

 » 3 months ago, # |   -28 SpeedCoder
 » 3 months ago, # |   +16 How to solve E and F?
•  » » 3 months ago, # ^ |   +1 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.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +3 Can you share your code? The editorial uses a different method than Toposort. edit: I was unfamiliar with kahn's algo for toposort.
 » 3 months ago, # |   +1 I died in the process to get my solution for E work even on samples. :waturr:. How to do E ?
 » 3 months ago, # |   0 How to solve E please ;.;
 » 3 months ago, # |   +6 I had the intuition to form a directed graph in E. Can't think of anything else.
•  » » 3 months ago, # ^ |   +3 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.
•  » » 3 months ago, # ^ |   0 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
•  » » » 3 months ago, # ^ |   0 Can you share your process? Thanks
•  » » » » 3 months ago, # ^ |   0 I only got to that part
•  » » » » 3 months ago, # ^ |   0 Exactly same idea as E 787C - Berzerk
 » 3 months ago, # |   +60 The editorial of F mentions insertion dp a 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.
•  » » 3 months ago, # ^ |   0 The search results depends of your country and of your own search history, I got results in french, what do most people see?
•  » » » 3 months ago, # ^ |   +1 Something sacred.
•  » » » 3 months ago, # ^ |   +7 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.
•  » » 3 months ago, # ^ |   0 Lol, try searching broken profile dp
•  » » 3 months ago, # ^ |   0 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?
•  » » » 3 months ago, # ^ |   +3 That was what I was trying to find out :)
 » 3 months ago, # |   +14 For E, I found the explanation of https://cp-algorithms.com/game_theory/games_on_graphs.html quite useful.
 » 3 months ago, # | ← Rev. 2 →   +13 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!
 » 3 months ago, # |   0 C, what is the proof that we can resort c[] without changing the result?
•  » » 3 months ago, # ^ |   0 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.
•  » » 3 months ago, # ^ |   0 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.
•  » » 3 months ago, # ^ |   +1 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 ;)
 » 3 months ago, # | ← Rev. 3 →   +3 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 - try find a child from where win is guaranteed (i.e. if opponent is at that node, he'll definitely loose) try find a child from where draw is guaranteed (i.e. if opponent is at that node, he cannot win no matter what ) Otherwise 1st player will loose from current node. 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 Submissionnotations used:- 0 -> loose,1 -> draw, 2 -> win
•  » » 3 months ago, # ^ |   0 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.
•  » » » 3 months ago, # ^ |   +5 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 :)
 » 3 months ago, # |   +36 The sample code in editorial E was fixed. We are sorry for the poor work.
•  » » 3 months ago, # ^ |   0 Can you please upload the test cases for this contest in dropbox.Thanks!
 » 3 months ago, # |   0 E can also be solved with eliminating vertex with 0 outgoing edge, much like agc027_c.
 » 3 months ago, # |   0 Could anyone tell me whether we can solve the task E with Trie?
 » 4 weeks ago, # | ← Rev. 4 →   0 How to solve C if the condition is $A_{i} \neq A_{i + 1}$ instead of $A_{i} \neq A_{j}$?