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

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

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
  • Проголосовать: не нравится

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -28 Проголосовать: не нравится

SpeedCoder

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

How to solve E and F?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

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

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

How to solve E please ;.;

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

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

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

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +14 Проголосовать: не нравится

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

»
5 лет назад, скрыть # |
← 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!

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

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

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

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

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

»
5 лет назад, скрыть # |
← 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

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +36 Проголосовать: не нравится

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

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

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

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

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

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

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