chokudai's blog

By chokudai, history, 5 weeks ago, In English

We will hold AtCoder Beginner Contest 175.

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

We are looking forward to your participation!

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

»
5 weeks ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

chokudai Please upload the English editorials so that we noobs can learn from them. Still waiting for this one's.

»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

The contest starts in ~40 mins, see you on the leaderboard :)

»
5 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve F?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it
    Solution for F
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      Actually only prefix or suffix of given strings can be the "remaining part", so the number of nodes is just O($$$N * \max|S|$$$)

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hi,

      How can you tell when it's impossible to form a palindrome string from Dijkstra? From your demonstration, you have a finite amount of states to explore, so after running them out you would print -1.

      I get that you have to choose a string at most once for a certain half. (from 21 choose 2, either is a palindrome or not, so it's not worth putting it in both halves), but still, you would have to reuse them in a way that is hard to implement.

      Thank you!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to remove TLE in D? My code gives TLE due to large K but how can i make my solution batter? any hints will help alot.thanks in advance!

My Code
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The constraints on k are too big here for the time complexity to be O(k). Think O(N^2)

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you explain the O(n^2) approach? Thanks.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        It is by finding cycle in permutation. Although I could not debug my code. It was showing WA on 4 cases

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Here's a clue by if it can help. Hint

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            Lol. Only after reading your comment I realised this problem has $$$N \leq 5000$$$ not something closer to $$$N \leq 10^5$$$. Nevertheless it can be solved in $$$O(n log n)$$$ and it's not that much harder.

            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Hey I_love_chickpea, can you explain how D can be done $$$O \left( n \log\left( n \right) \right)$$$ ?

            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              How to solve it in O(n logn)

              • »
                »
                »
                »
                »
                »
                »
                »
                5 weeks ago, # ^ |
                  Vote: I like it +16 Vote: I do not like it
                O(n log n) solution for D
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Thanks I_love_chickpea.

                  For those who are facing difficulty in understanding relationship between max-subarray sum and this problem.Here is explanation :

                  In $$$O \left( { n }^{ 2 } \right)$$$ approach we are trying to start our cycle from each element of array which means we are traversing same permutation cycle from different starting points which is not at all required but optimal starting point can be found by solving max-subarray problem on that cycle.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  cis_pie

                  I understand your point that for same cycle we are doing lot of recalculation. But what is not clear is how to actually avoid that using subarray sums, can you please elaborate the solution a bit more if you have understood?

              • »
                »
                »
                »
                »
                »
                »
                »
                5 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Here is a tutorial for the subarray sum part. https://www.geeksforgeeks.org/maximum-sum-subarray-of-size-range-l-r/

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

                In short, store for each k=0,1,,log n, precalculate some information from a node v for every path of length $$$2^k$$$ - $$$sum_{k,v}$$$ for sum of the path - $$$maxi_{k, v}$$$ for maximum prefix sum of the path and use them like Digit DP

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

          Same happened with me

»
5 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

Should have rushed for E before D.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i agree

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      I took 25 minutes to do E and 65 minutes to do D. If I rushed for E earlier, my position would have been a lot better.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it +8 Vote: I do not like it

        Your score would be same and the penalty is the time of your last submission. So you solve E first or D first, how will it affect your position?

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

please, anyone, find what's bug in my solution in D (it's giving WA on 4/42 test cases)

https://atcoder.jp/contests/abc175/submissions/15952579

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    submission i am also getting WA on same test cases .

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I had the same problem, but figure this out:

    You do the first cycle of length A, and then you find out you can do B more of those cycles.

    Do all of them: B, and then brute force the rest of the steps?

    no

    Do B-1 of them, and brute-force the rest. The B-th cycle might be the last complete cycle, and so you are missing out on some update_max calls on those 4 WA.

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Getting 4 cases wrong on D. Can anyone suggest any corner case I am failing to include? Thank you :)

Submission

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +45 Vote: I do not like it

    If k % cycle_length == 0 then reduce number_of_cycles by one and for last cycle see if adding some nodes only makes answer better or not

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You have done exactly my mistake. WA
    AC
    let's say, cycle length is 5 and k is 17. Then, you need to check two things, max val till 5 operation, total cycle sum * 3 + maxval till 2 operation. Hope you get the mistake.

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

      I am getting WA on 2 test cases in problem D.

      My solution

      It's on test case 2 and 22.

      Anyone else got the same error ?

      UPD: I was taking the maximum answer in the prefix of the cycle before even considering what the value of k is.

      How silly of me :'-(

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      could u plz explain why u did k-- in the beginning??

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Crap

Same 4/44 WA in D as people above

And failed to fit E into timelimits with python

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

    For E, You must be writing recursive dp. I also got TLE at first but then got an AC in java with same logic. I saw many people get AC with python but using iterative bottom up dp.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      nope It is bottom-up. It's just a matter of small optimizations inside the loops

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In E, we cant greedily chose the value to be taken. How to go ahead with the DP approach ?

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

    dp[k][i][j] get k items on i-th row and j-th column

    for evert kk, i, j

    ckmax(dp[0][i + 1][j], dp[kk][i][j]);
    ckmax(dp[kk][i][j + 1], dp[kk][i][j]);
    
    if (val[i + 1][j] != 0)
      ckmax(dp[1][i + 1][j], dp[kk][i][j] + val[i + 1][j]);
    if (val[i][j + 1] != 0 && kk < 3)
      ckmax(dp[kk + 1][i][j + 1], dp[kk][i][j] + val[i][j + 1]);
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Isn't that too cache-inefficient? It doesn't really matter in this problem I guess, but I can't see why you have used k,i,j instead of i,j,k. Is there any particular reason or just the dp that came into mind?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        In most time dp[10][100000] is faster than dp[100000][10], because of Spatial Locality。It may be cache friendly.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh, didn't know that.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ah, I see. I thought your for loops were i, j, k but if you had k, i, j, then you would indeed have spatial locality.

          Since I had dp[r][c][4] and iterated over i, j, k it amounts to the same thing. (I think? If wrong, please point it out.)

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Right.

            But In this problem we have 3 dimensions, so it may not have too much difference...

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$dp[i][j][k]$$$ be the answer till cell $$$(i, j)$$$ using $$$k$$$ items in row $$$i$$$, transitions are pretty straightforward.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      So straightforwared that you can tell with understandable words?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        The state is CurRow, curCol, CurNoOfItems

        The transitions are:

        if curNoOfItems is 3, then we only can go to the next row, and reset number of items to zero.

        if curNoOfItems less than 3: we have four options:

        1. Either we do not take it and move to the next item in the same row.
        2. Either we do not take it and move to the next row and resetting number of items to zero.
        3. Either we do take it and move to the next item in the same row (increasing no of items by 1)
        4. Either we do take it and move to the next row and resetting number of items to zero.

        Hope that will help. You can look at my code here: My Submission

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks, now I understood.

          My basic error was in "but at most three for each row". I tried to solve for at most three at all.

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

please can anyone try to explain E? I tried using dp and got 10 WA. made dp[r][c][4]. dp[i][j][0], dp[i][j][1], dp[i][j][2] for storing 3 greatest value in row and dp[i][j][3] for storing max sum obatined till r-1 rows. Here is my submission.

Can anyone tell what's wrong in my solution?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried this, too. But it is wrong idea. If you get on two paths say { 100, 50, 50 } and { 100, 70, 0 } you cannot say what is "better" because it depends on whhich numbers will follow later.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also did something similar. dp[i][j][k] denotes the maximum amount if I choose k items in i'th row after the index j. Here k can have only 3 values,.... 1,2,3. Here is my submission :https://atcoder.jp/contests/abc175/submissions/15941327. As we want to maximise our answer, k=0 state is unnecessary. Finally our answer should be max({dp[1][1][1],dp[1][1][2],dp[1][1][3]}). Note: we start calculating dp values from bottom.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Getting WA on D in 4 Test Cases...Can anyone help me out here? Link: https://atcoder.jp/contests/abc175/submissions/15955049

»
5 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

Missing AnandOza and Geothermal's editorial.

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

In problem C-

using

if((x-k*d)>=0)
cout<<(x-k*d)<<endl;

gives WA on 10 tcs but using

if(x/d>=k)
cout<<(x-k*d)<<endl;

gives AC.

Can someone plz help, by giving an example where the 1st one fails.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how can i print any index value of a set???? it's possible in c++????

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's possible if you use Policy-Based Data Structure, though generally, some other alternative would work too.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

So, How to solve F?

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I am getting WA on 2 test cases in problem D.

My solution

It's on test case 2 and 22.

Anyone else got the same error ? Someone please tell me where have done the error.

UPD: I was taking the maximum answer in the prefix of the cycle before even considering what the value of k is.

How silly of me :'-(

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For D :

Took me couple of "ifs" to code correct logic Submission.

Can someone explain better way to do this?

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Getting WA on D in 3 Test Cases...Can anyone help me out here? Link: WA on TC 7,11,22

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it
    Fully Commented Code
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
»
5 weeks ago, # |
  Vote: I like it +32 Vote: I do not like it

My screencast of the round, where I clutch out F, draw an ugly chocolate bar for a grid, and explain solutions to all problems (A-F) in video format.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Thanks for the screencast. In problem D , what's the use of below code, why only the first f0r(i, n) doesn't work ?

    if (cval > 0) {
    		cur += (k / csize - 1) * cval;
    		rem %= csize;
    		rem += k;
                  }
    
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      The way of implementing I describe in the solutions is better than what my code represents, and that edge case doesn't arise. What I did in the code was, instead of counting the number of possible cycles after fixing the last few moves, I first made as many cycles as possible then found the best way to make the last few moves. This is wrong because it may make one too many cycles.

      The test case I find in the video which makes that part of code necessary is:

      3 7
      2 3 1
      13 15 -27
      

      where the optimal strategy is to start at position $$$3$$$, ride the cycle once, then end at position $$$2$$$ ($$$5$$$ moves). Without that section, the code won't even consider that as a possibility, and instead start at $$$1$$$, make two cycles, and end at $$$2$$$ ($$$7$$$ moves).

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Gotcha! I missed this case.

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

        Can you please help me in problem E. I did DP and quite of problems of it but couldn't do E because of that 3 moves constraint.

        Can you help in transitions and how that extra cell K in dp is working?

»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Am I the only one who gets demotivated by questions like todays D?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me with this submission on problem D? It gave WA in only two cases. I have no idea what's wrong with this :(

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Getting runtime error for some big cases for problem E can anyone tell what's wrong with this

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

any fault for problem E in my submission https://atcoder.jp/contests/abc175/submissions/me

»
5 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

I wrote an unofficial editorial from problem A to E. If you have any question, please give me comments and let me know. I’m going to write unofficial editorials for ABC, so don’t forget to check them out. The link for this contest is https://wordpress.com/read/feeds/108186275/posts/2862983275

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I have AC code for D https://atcoder.jp/contests/abc175/submissions/15996588

Store values of up to 5000 moves in DP table.

If K <= 5000, you can get the maximum value from the DP table.

Otherwise, the maximum value can be found in several cases. (Checkable on link)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

IF Anyone Need Detail explanation for D Here