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

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

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!

  • Проголосовать: нравится
  • +72
  • Проголосовать: не нравится

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

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

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

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

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

How to solve F?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится
    Solution for F
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится

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

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

      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!

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

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

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

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

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +9 Проголосовать: не нравится

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

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

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

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится

            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.

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

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

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

              How to solve it in O(n logn)

              • »
                »
                »
                »
                »
                »
                »
                »
                4 года назад, # ^ |
                  Проголосовать: нравится +16 Проголосовать: не нравится
                O(n log n) solution for D
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 года назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  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.

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

                  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?

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

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

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

                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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +10 Проголосовать: не нравится

          Same happened with me

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

Should have rushed for E before D.

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

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

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

    submission i am also getting WA on same test cases .

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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.

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

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

Submission

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +45 Проголосовать: не нравится

    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

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

    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.

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

      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 :'-(

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

Crap

Same 4/44 WA in D as people above

And failed to fit E into timelimits with python

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

    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.

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

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

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

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

      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?

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

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

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

          Oh, didn't know that.

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

          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.)

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

            Right.

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

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

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      So straightforwared that you can tell with understandable words?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +7 Проголосовать: не нравится

        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

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

          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.

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

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?

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

    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.

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

    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.

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

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

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

Missing AnandOza and Geothermal's editorial.

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

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.

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

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

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

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

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

So, How to solve F?

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

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 :'-(

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

For D :

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

Can someone explain better way to do this?

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

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

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

How to solve C?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится
    Fully Commented Code
»
4 года назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

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

      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).

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

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

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

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 :(

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

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

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

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

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

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

IF Anyone Need Detail explanation for D Here