chokudai's blog

AtCoder Beginner Contest 209 Announcement
By chokudai, history, 3 years ago, In English

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!

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

Comments Comments (32)
| Write comment?
»
3 years ago, # |
  Vote: I like it -28 Vote: I do not like it

SpeedCoder

→ Reply
»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

How to solve E and F?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

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

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

      → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E please ;.;

→ Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

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

    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

    → Reply
»
3 years ago, # |
  Vote: I like it +60 Vote: I do not like it

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 mindblowing

P.S : Open at your own risk.

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

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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Something sacred.

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      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.

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

    Lol, try searching broken profile dp

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

    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?

    → Reply
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

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!

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

C, what is the proof that we can resort c[] without changing the result?

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

    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.

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

    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.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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 ;)

    → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

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 -

  1. try find a child from where win is guaranteed (i.e. if opponent is at that node, he'll definitely loose)
  2. try find a child from where draw is guaranteed (i.e. if opponent is at that node, he cannot win no matter what )
  3. 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 Submission

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

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

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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 :)

      → Reply
»
3 years ago, # |
  Vote: I like it +36 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

→ Reply