chokudai's blog

AtCoder Beginner Contest 175 Announcement
By chokudai, history, 4 years 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

Comments Comments (82)
| Write comment?
»
4 years 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.

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

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

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

How to solve F?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it
    Solution for F
    → Reply
    • »
      »
      »
      4 years 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|$$$)

      → Reply
    • »
      »
      »
      4 years 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!

      → Reply
»
4 years 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
→ Reply
  • »
    »
    4 years 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)

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

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

      → Reply
      • »
        »
        »
        »
        4 years 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

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

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

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years 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.

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

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

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

              How to solve it in O(n logn)

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

                  Thanks tribute_to_Ukraine_2022.

                  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.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years 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?

                  → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                4 years 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/

                → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                4 years 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

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

          Same happened with me

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

Should have rushed for E before D.

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

    i agree

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
      • »
        »
        »
        »
        4 years 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?

        → Reply
»
4 years 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

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

    submission i am also getting WA on same test cases .

    → Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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

→ Reply
  • »
    »
    4 years 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

    → Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years 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 :'-(

      → Reply
»
4 years 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

→ Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years 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

      → Reply
»
4 years 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 ?

→ Reply
  • »
    »
    4 years 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]);
    → Reply
    • »
      »
      »
      4 years 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?

      → Reply
      • »
        »
        »
        »
        4 years 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.

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

          Oh, didn't know that.

          → Reply
        • »
          »
          »
          »
          »
          4 years 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.)

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years 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...

            → Reply
  • »
    »
    4 years 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.

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

      So straightforwared that you can tell with understandable words?

      → Reply
      • »
        »
        »
        »
        4 years 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

        → Reply
        • »
          »
          »
          »
          »
          4 years 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.

          → Reply
»
4 years 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?

→ Reply
  • »
    »
    4 years 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.

    → Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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

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

Missing AnandOza and Geothermal's editorial.

→ Reply
»
4 years 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.

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

    k*d can be $$$10^{30}$$$ : overflow.

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

      Thanks a lot. My bad, I did not notice the constraints of k and d. :(

      → Reply
»
4 years 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++????

→ Reply
  • »
    »
    4 years 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.

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

So, How to solve F?

→ Reply
»
4 years 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 :'-(

→ Reply
»
4 years 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?

→ Reply
»
4 years 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

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

How to solve C?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it
    Fully Commented Code
    → Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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;
              }
    → Reply
    • »
      »
      »
      4 years 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).

      → Reply
»
4 years 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?

→ Reply
»
4 years 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 :(

→ Reply
»
4 years 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

→ Reply
»
4 years 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

→ Reply
»
4 years 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)

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

IF Anyone Need Detail explanation for D Here

→ Reply