Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

chokudai's blog

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

We will hold AtCoder Beginner Contest 145.

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

We are looking forward to your participation!

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

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

How To Solve 'E'?

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

    It's a standard knapsack problem, the only difference being that the order you want to eat the food in is increasing by A (you want the longest food you'll eat to be at the end)

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

      I still didn't get , why sorting with respect to time gives AC. Can you please,explain?

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

        Because you want to eat a couple, and then the last one you eat can go over. Since it can go over and is not bounded by T, then the BEST one to go over is the largest one from the subset you selected.

        Formally if you have a subset of times A1, A2, A3 ... Ak, you can eat them iff, you have a subset of k-1 that is <= (T-1). Now you see that you want to remove the maximum one from the subset. Sorting it and doing a knapsack will guarantee that the last one is the added is the maximum one in the subset

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

    Let $$$dp[i][j]$$$ be maximal happiness you can achieve taking some of first i dishes during j minutes. Let $$$backdp[i][j]$$$ be maximal happiness you can achieve taking some of last dishes (with indices from i to n) during j minutes. Now let's go through the dish that we will eat last ($$$i$$$) and time we spent on eating first $$$i - 1$$$ dishes ($$$t'$$$). Try to update answer as $$$min(answer, dp[i - 1][t'] + backdp[i + 1][(t - 1) - t'] + b[i]$$$. It's easy to calc $$$dp$$$ : $$$dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - a[i]] + b[i]$$$ (if such exist)$$$)$$$. Same with $$$backdp$$$.

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

How to Solve D ?

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

    If you print the matrix you notice that every third diagonal is part of pascals triangle (so just implement combinations and get the right row and column in the triangle)

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

      Can you please detail more the idea and solution ?? Thanks

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

        To get to x, y from 0, 0 we have to do some (i + 1, j + 2) and some (i + 2, j + 1) moves. So, let's iterate how many times we will do (i + 1, j + 2) moves and check whether if moves left can be done with some number of (i + 2, j + 1). If the total number of moves is N, and we did K (i + 1, j + 2) type moves, number of ways to do it will be $$$C_{N}^{K}$$$

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

      But how to implement combinations.I think it can't work when using mod.This worries me so much.

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

        You can calculate factorials modulo n, store them in fact[x]; And then inverse of factorials modulo N. (since MOD is prime, invFact[n] = POW(fact[n], MOD-2))

        And since comb(a,b) = fact[a] / (fact[b] * fact[a-b]) modulo this means

        fact[a] * invfact[a] * invfact[a-b].

        Edit: Tutorial that explains https://www.geeksforgeeks.org/compute-ncr-p-set-3-using-fermat-little-theorem/

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

          Thanx

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

          You also can use Extended Euclidean to find modular inverse. I prefer it more than fermat.
          link: You only need to read equations, so don't worry about language.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      Matrix
»
8 months ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

DPcoder rip rating

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

How to Solve D ? plz explain

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

what's the dp at F? plase

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

    best[i][j][k] -> best cost if you only consider the first i columns, the i-th column has value j and you've done k changes already. (j is really big, but you notice that there's no use in changing in something that's not already in the input, or 0). (Note, since you only look 1 in the past with i, you can only store 0/1 for it)

    The big observation to make this fit in time is that if the previous one has height X, then if you change the current one, you don't want to make it shorter, since that won't decrease the cost, but might increase it in the future.

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

Hello, I need guidance please for E. For problem E I have an approach that gave me wrong answer and I don't understand why. I just do a normal knapsack problem and I stop at time T-1 means knapsack(weight=T-1,n) then by backtracing the elements of my solution knapsack[t-1][n], I delete them from the val set and choose the maximum left and add it to my result. it gave me 5 wrong answers. Can somebody help me ?? My solution

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

    Think about the problem as tubes(denoting times) . So , long tube for longer time and short tube for shorter time.

    case 1: If for optimum time T-1, longest valued tube is there in solution i.e its tube is in naive knapsack sol. and it may be replacing shorter tubes that represents a smaller sum than the highest valued. There you can replace most valued tube and take it at the last T.

    case 2: if second highest values tube whose tube length is greater than T , wont come into naive knapsack picture and if highest valued tube is in the picture then its optimal to take the second highest at last T.

    Similar way there are many cases we have deal with . I think this time atcoder's official editorial is better. It does brute force dp , for all i after excluding it

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

What is the after contest test case added for problem E All you can eat? My solution fails for it and passes the rest.