chokudai's blog

By chokudai, history, 3 months ago, In English,

We will hold AtCoder Beginner Contest 149.

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

We are looking forward to your participation!

Update: Due to the troubles in judging, this contest will be unrated. Sorry for the inconvenience.

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

»
3 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Please note the unusual start time. It starts one hour before the usual start time. :)

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My submission for problem D is had stuck on test 58

Can you please fix it

»
3 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Nice. Now the round is unrated. (First time solved 4 tasks);_;

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

admin:Due to the troubles in judging, this contest will be unrated.

»
3 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Can anyone clarify what F wants us to do, the language is unclear to me?

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

    S is the smallest subtree that contains all the black vertices. You need to calculate the expected value of the white vectices in S.

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

      Aaahhhh, got it, I mistook it for "S is the smallest subtree containing only black vertices".

»
3 months ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve E?

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

    It can be solved using FFT, but there is a binary search solution too.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    First you could binary search over the minimum value of pair sum such that count of all pairs satisfying this criteria is more than equal to M.To find count of such elements in each binary search check, you could use 2 pointers, one for maximum and the other for minimum and get the total elements satisfying the condition. After binary search we have the minimum pair sum so that total count of all pairs having more or equal sum is at least M. Say this minimum is 'Min'.So for pair sum more than equal to Min + 1, has count less than M.Sum up all such pairs with pair sum more than equal to Min + 1. And for the remaining pairs to make the count = M, we add that Min required number of times to the answer.

»
3 months ago, # |
  Vote: I like it +8 Vote: I do not like it

has anyone wrote dp solution of D??

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

    No mine is greedy.

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

      Can you tell me about your greedy approach. Even I tried greedy but after test case #12 every 1 out of 3 test cases are giving wrong answer.

      • »
        »
        »
        »
        3 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        So what i was doing is first win all the first 'k' games and store the answers of these games in a vector. Now starting from K+1 game check the condition that i — k does not contradict your winning hand. If it does add a '?' to the vector to make sure that this should not decrease the number of wins. We dont care what this '?' is.

        Code

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

        Greedily i think you could go for segregating all r,p, and s elements and storing their indices.Iterate over segregated indices and greedily mark the position ,say i, as winning position if the position i<k(0 based indexing) or (i-k) has not been marked as the same move, and incrementing answer by the power of very move.

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it -10 Vote: I do not like it

        Just check if s[i — k] == s[i] -> then you cannot add the score and assign s[i] = (something character you like).

        else add the score.

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

        My bad, just a small mistake cost we WA.

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

        Iterate all characters t[i], if t[i] != t[i-k] just plus scores to the answer, otherwise assign t[i] with a character which is different from original t[i] and t[i+k].

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

    I think you could generate K dp's representing dp over different indices mod K.

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

      can you elaborate it further ??

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

        If you split indices on the basis of their mod value with respect to K, then we require consecutive indices of a group should not have same move.So with only a maximum 3 choices at each point, you could run a (N*3) dp for each group to get maximum answer for each group.

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

    Yep me.

    Whenever i-k is same as i pick maximum of dp[i-1][rock], dp[i-1][paper], dp[i-1][scissor] and change ith element to '$' so that next i+k you can use any of rock, paper and scissor again.

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

    Yeah I did: https://atcoder.jp/contests/abc149/submissions/9215384

    Pretty much you separate into k strings and consider each one independently.

  • »
    »
    3 months ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    here is mine

    the source is pretty much self explanatory i guess. here is the main idea,

    if str[i]== str[i-k] //for i>k
        dp[i] = max(dp[i-k], dp[i-1])
        str[i]='0'
     else dp[i] = dp[i-1] + (points gained from current win)
    

    Edit: complexity : O(N)

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by chokudai (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain the solution of D. I thought it was dp but couldn't figure out the states as i am very very weak in dp. :(

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

    let dp[i][j] be the maximum score witch you can get if we will provide only i%k-th, k+i%k-th... i-th games and on i-th game you will use j-th hand(if j=1 Rock, if j=2 Scissors, if j=3 Paper). dp[i][j]=dp[i-k][1]+dp[i-k][2]+dp[i-k][3]-dp[i-k][j]. answer is: max(dp[n][1],dp[n][2],dp[n][3])+...max(dp[n-k+1][1],dp[n-k+1][2],dp[n-k+1][3]). code: https://atcoder.jp/contests/abc149/submissions/9217025

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why rating has not updated yet?

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve question E? I got wrong .

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Please explain how to solve F in more details. I'm unable to understand editorial

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E using binary search?