Блог пользователя chokudai

Автор chokudai, история, 3 года назад, По-английски

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 года назад, # |
  Проголосовать: нравится -28 Проголосовать: не нравится

SpeedCoder

»
3 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

How to solve E and F?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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 года назад, # ^ |
      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 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve E please ;.;

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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 года назад, # ^ |
      Проголосовать: нравится 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 года назад, # |
  Проголосовать: нравится +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 mindblowing

P.S : Open at your own risk.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 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 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Something sacred.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Lol, try searching broken profile dp

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 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 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

»
3 года назад, # |
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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 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 года назад, # ^ |
      Проголосовать: нравится 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 года назад, # ^ |
      Проголосовать: нравится +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 года назад, # |
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 -

  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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 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 года назад, # ^ |
        Проголосовать: нравится +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 года назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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