sugim48's blog

By sugim48, 2 weeks ago, In English,

The contest was postponed to 2019-01-06(Sun) 11:00-16:00 UTC.

Hello, Codeforces!

We will hold Educational DP Contest at AtCoder on Saturday.

About the Contest

This is an unofficial contest to practice DP (Dynamic Programming). We selected 26 DPs, mostly basic ones, and prepared a problem to learn each of them. Test your skills during the real contest, and brush them up after it ends.

Details

Rules

The rules for ABC, ARC and AGC apply. The important points are:

  • This is an individual match; no teams allowed.
  • Revealing the solutions to others during the contest is prohibited.
  • The penalty for an incorrect submission is 5 minutes.

Notices

  • The problems may NOT be arranged in ascending order of difficulty.
  • There are many famous problems.
  • The contest is not intended for experts such as reds (anyone can compete, though).
  • It is recommended to use languages that are not too slow (such as C++ and Java).

Staff

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

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

Nice idea

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

the problems with u all setters are that for u even div1 e problems are easy ..

so cant guess what easy means here

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

    Don't worry, red coders are able to set up contests with easy problems.

    flashback of my rounds

    Okay, some red coders.

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

So which level are the problems in? Will the problem set be interesting for orange coders? and purple?

Since you say they are basic ones, it sounds like it should be somehow like div2 contests?

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

    The difficulty levels of the problems range from Div2 A to Div2 E. However, it may be challenging even for Div1 coders to solve all the problems in five hours.

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

Neat idea! Are there any plans to do this with other topics as well (e.g. Educational Combinatorics contest, educational geometry contest, etc.)? I think that could be really beneficial for a lot of people, especially if this contest goes well.

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

Very nice initiative

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

Now this is some serious effort by Atcoder this year to help us strengthen up our DP. Hope they continue to come up with such good ideas.

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

I wanted something like this

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

Will an english editorial be posted when the contest ends ?

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

    If this can be done then it will be really helpful.

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

Why is the contest postponed?

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

    As mentioned in the sugim's tweet on twitter it is due to the codeforces round clashing with the atcoders' round.

    "1/5 (土) 20:00 — 25:00 に開催予定の DP まとめコンテスト (https://atcoder.jp/contests/dp ) ですが、1/5 (土) 25:30 — に Codeforces のコンテストが生えたので、1/6 (日) 20:00 — 25:00 への移動を検討しています。ぜひアンケートにご協力ください。"

»
13 days ago, # |
  Vote: I like it +17 Vote: I do not like it

Nice idea to test how good you are in dp :DDD

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Reminder: The contest starts in an hour.

»
12 days ago, # |
  Vote: I like it +14 Vote: I do not like it

Are questions sorted by difficulty?

and thanks for this ^^

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

    Read the blog.

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

    No the questions won't be sorted by difficulty

  • »
    »
    6 days ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Difficulty according to solve count during contest: A B C D H F E I G K L M N P S O Q R J U Z Y X T V W

»
12 days ago, # |
Rev. 3   Vote: I like it +14 Vote: I do not like it

How to solve Permutations in less than n3 ?

  • »
    »
    12 days ago, # ^ |
    Rev. 4   Vote: I like it +53 Vote: I do not like it

    dp[i][j] — The number of ways to make a permutation of length i + 1 that respects the first i signs and the last element is j (j ≤ i + 1).

    If s[i] is  >  then

    Otherwise

    To do this in O(n2) use prefix sums

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      I don't really get it. Why would it be permutation? Won't we count the ways where j is used on some earlier step?

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it +12 Vote: I do not like it

        Hint: See that Rudy358 used >= instead of > in his first equation.

        • »
          »
          »
          »
          »
          12 days ago, # ^ |
            Vote: I like it +18 Vote: I do not like it

          Ah, so we kinda insert j to the previous step permutation by increasing all the values greater or equal to j by 1 and it doesn't break anything. Yeah, that makes sense, nice.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    dp[i][j] denotes the number of permutations of 0, 1, ..., i - 1 such that the last element is j and all the first i - 1 inequalities are fulfilled. You can easily update this dp in O(1) with prefix sums, giving O(n2) complexity.

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

    I solved it with inclusion-exclusion principle, dividing the sequence into monotonously increasing parts. After writing down each terms, calculate dp[i] := sum of terms ending at i. That can be done in O(n^2) time. (I couldn't come up with simpler dp...)

»
12 days ago, # |
  Vote: I like it +33 Vote: I do not like it

Thanks very much for contest ! When editorial will be available ?

»
12 days ago, # |
  Vote: I like it +14 Vote: I do not like it

How to solve 0-1 Knapsack with weights <= 1e9?

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    In the given problem the values were  ≤ 1e3, so .

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    You need to make a dp[N][V] — what is the minimum weight you need to use to get the value V in the first N items. Then just iterate over the dp table to find the maximum value that requires less than W space.

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

      Can anybody explain the solution of E for the below test case?

      6 15
      6 5
      5 6
      6 4
      6 6
      3 5
      7 2
      

      Problem link

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Btw, there is also dp[val] solution (val<=1e5, maximum possible value) where for each i<=n check if there is j>val[i] such that adding wgh[i] to dp[j-val[i]] will minimize dp[j]. (1<=j<=val). But in order to not overlap with updates (if you go from 1 to val), either iterate from val to 1, or store all changes in vector and update it after iteration.

»
12 days ago, # |
  Vote: I like it +14 Vote: I do not like it

The contest was very nice, i didn't manage to solve quite a few problems(i got 18), which is a good thing since i will be able to solve them now and learn new things :).

»
12 days ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve Sushi?

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

    I even don't understand it, do you?

  • »
    »
    12 days ago, # ^ |
    Rev. 2   Vote: I like it +41 Vote: I do not like it

    If you have k empty piles out of n, the expected value of the number of steps to go to different state increases by . The rest is just dp[cnt1][cnt2][cnt3] with 3 transitions.

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

      Hey! I am really weak at expected value problems. Can you also explain the recursive relations?

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

        You basically have three options to pick from some state (cnt1, cnt2, cnt3). These are: eating from a pile with 3 with probability , from a pile with 2 with probability and from a pile with 1 with probability . So that gives you

        + +

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
          Rev. 2   Vote: I like it +10 Vote: I do not like it

          Still can't understand the recursion? :(

          Can someone(PikMike) please explain it?

          • »
            »
            »
            »
            »
            »
            10 days ago, # ^ |
            Rev. 2   Vote: I like it +16 Vote: I do not like it

            The state is: how many piles of size 1, size 2, and size 3 there are, and E[][][] is the expected number of remaining turns. At the current step, we know each of the probabilities of picking a stone from a pile of size 1, 2, 3, or empty pile. The empty pile leads to the same state, while the others lead to states whose E[][][] value are already computed. Eventually, you will be able to solve an equation E[c1][c2][c3] = 1 + prob(empty) * E[c1][c2][c3] + (stuff in terms of previous dp values) which gives you the same formula as PikMike posted.

            • »
              »
              »
              »
              »
              »
              »
              10 days ago, # ^ |
              Rev. 2   Vote: I like it +10 Vote: I do not like it

              Yeah I understood. Thanks ksun48!

              gritukan's code helped me a lot. Very well written and self explainable.

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

              Why extra "1" is added??

              • »
                »
                »
                »
                »
                »
                »
                »
                6 days ago, # ^ |
                  Vote: I like it +16 Vote: I do not like it

                Current step always uses a turn no matter what happens, the rest of the sum is the expected number of additional turns after this one.

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

          Thanks a lot, PikMike and ksun48!

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

      PikMike How do you find the formula , Did you use something easier than actually evaluating arthmetic-geometric progression, ( )

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

        I just calculated this progression for like 100 iterations and guessed the formula. No idea about the proof.

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

          A more intuitive way (for me) is to just write the dp as

          and move to the left hand side.

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

            Why extra "1" is added??

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

        It is well-known from statistics that for the geometric distribution (counting number of trials before a success, where each independent trial is probability p) the expected value is . In this case, to hit a non-empty pile, so the expected value of steps to hit a non-empty pile is as desired.

        There are several ways to prove it here. Indeed, arithmetic-geometric progression is one.

»
12 days ago, # |
  Vote: I like it +10 Vote: I do not like it

What is testcase 1_03 for E?

»
12 days ago, # |
  Vote: I like it +9 Vote: I do not like it

In Matching I had O(n2 * 2n ) solution, how to optimize it? I feel really stupid

»
12 days ago, # |
  Vote: I like it +20 Vote: I do not like it

I hope this is the first of many Educational Rounds to come from AtCoder. Looking forward to more such good content.

Here are my solutions to the problems of this contest, in case anybody wants to refer.

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

    You did coins but not the problems before it? Or are you still uploading problems.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solved Coins in the same way as you did but got WA. My solution What mistake did I make?

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

      Try setting the precision to a higher number plus try putting (double) in front of every multiplication.

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

        They mentioned absolute error actually, sad

        • »
          »
          »
          »
          »
          11 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          They were checking upto 9 digits instead of the usual 6. :)

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

    I like your idea, so i have uploaded the codes for the problems i solved. I will be adding more problems as i solve them and maybe even the explanations to some problems if i'm not too lazy.

»
12 days ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Is CHT of Z really easier than rerooting of V or inclusion-exclusion thingy of Y?) Or is there any solution without CHT?

Btw, how does one generate tests for CHT dp? Like what stops me from maintaining MAGIC best by some parameter positions and trying to update from them all (like in O(n·MAGIC))?

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Haven't even read Frog 3, the problem is actually easy with LiChao or something similar.

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, I've heard that CHT is easy enough with LiChao but I've never put myself to learn it (or any other implementation of CHT). I've always thought that CHT is really advanced topic. Especially compared to problems V or Y.

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

        LiChao is quite easy actually. I did Z with LiChao in like 10 mins while Y took me 30-40 minutes. I found Z to be easier but it may be because i practiced dp optimizations not too long ago. Didn't get to solving V during the competition.

        • »
          »
          »
          »
          »
          12 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I coded in 5 minutes but have been debugging for almost 10 minutes. Here is my code I used dynamic LiChao because I had implementation already but why it doesn't work?

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

            Can't really tell what is wrong with your code. Here is my implementation of LiChao(The set function is nicer than in your implementation). I got it from this site. It explains quite nicely how it works and has a pretty easy to memorize implementation.

            • »
              »
              »
              »
              »
              »
              »
              12 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              This is where I learned it from too but in my implementation, I break it to all possible cases of intersections because It is easier for me to get it right

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

    If you have a template, (I used https://github.com/kth-competitive-programming/kactl/blob/master/content/data-structures/LineContainer.h), it's one of the easier problems.

    V and Y are simpler concepts IMO but reequire more not-template code.

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well, yeah, probs. It seems I just somehow expected everyone to code all problems from scratch. :D

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

    I really like tests for Z! (I can't come up with a MAGIC solution which passes even half of them :D) sugim48, can you please show me some generators for it?

    UPD: Why did I comment that instead of writing a PM? :D

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is there an easy way to do the rerooting in V? I had to make a segment tree for every node to store the already calculated values for its neighbours to make my solution not TLE. I understand why it TLEs without the segtree but cant figure out something simpler to fix it.

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

      You store partial products for neighbours (both prefix and suffix) and combine them to recalc the value.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is the limit of n so big in problem U? I spent 20 minutes trying to optimize it without realizing that O(2^32) will fit TL. Is there a faster solution?

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the editorial of problem N,slimes?

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

    dp[l][r] — minimum cost to merge from l to r Notice that in the last operation we will merge two consecutive blocks, and their total sum will be the sum of all slimes. So dp[l][r] = min(dp[l][k] + dp[k][r]) + a[l] + a[l + 1] + ... + a[r]. Which is O(n3)

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

      Are you sure? The problem seems to me similar to Matrix Chain multiplication, which is O(n3) in time.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How about the problem STONES

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve R-Walks?

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The TLE is caused by visiting a state over and over.

    Remember a node can have many parents.

    I suggest you count the answer for each node on a topdown manner , and when visiting it again just return its value.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain why/how Convex Hull Trick is used for Z?

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

    We have dp[i] = min(dp[j] + (h[i] — h[j])^2) + C , (h[i] — h[j])^2 = h[i]^2 + h[j]^2 — 2*h[i]*h[j], dp[i] = min(-2*h[i]*h[j] + h[j]^2 + dp[j]) + h[i]^2 + C, the line is (-2*h[j] , h[j]^2 + dp[j]).

»
12 days ago, # |
  Vote: I like it +24 Vote: I do not like it

W is almost https://csacademy.com/contest/archive/task/popcorn without alien's trick (this problem is W but with positive weights and every position has an equal negative weight). I'll use this opportunity to ask: how to solve it faster than O(n * logn) with a lazy seg tree? Since O(N * log^2) is TLE for POPCORN.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hint on Problem R(Walks) if the constraints on N would have been higher ?
With given constraints on N, it could be easily solved using Matrix Exponentiation but what if constraints on N were higher.

»
11 days ago, # |
  Vote: I like it +13 Vote: I do not like it

Can someone tell me the solution for problem X-tower and W-Intervals? I can't figure out the solution for these problems during the contest.

  • »
    »
    11 days ago, # ^ |
    Rev. 2   Vote: I like it +14 Vote: I do not like it

    Problem X: Sort all blocks according to w + s decreasing. Now DP(i, j) is the maximum value of stack containing blocks for the first i blocks and current stack can contain more j unit weight.

    Transition is very similar to Knapsack problem:

    • If we don't choose block i, then dp(i, j) -> dp(i + 1, j)

    • If we choose block i, then it must satisfy j >= weight[i], dp(i, j) + value[i] -> dp(i + 1, min(j — weight[i], solid[i]))

    • »
      »
      »
      11 days ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      Can you prove that sort all blocks according to w + s decreasing is the right order?

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

        Think about how you would order the blocks if there were only 2 of them, lets say the first has w1 ans s1 and the second has w2, s2. Lets consider both orderings:

        If you put the first on the bottom, the strength of the tower will be s1-w2.

        If you put the second on the bottom, the strength of the tower will be s2-w1.

        So we want to take the first as the bottom one if s1-w2 > s2-w1.

        Which is equal to saying s1+w1 > s2+w2. There you go, we want to put the ones with greater s+w on the bottom.

        For more problems like this one check out these videos by Errichto: part1 part2

        • »
          »
          »
          »
          »
          11 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Why would the strength of the tower be matter?

          • »
            »
            »
            »
            »
            »
            11 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            If you want to put more blocks above the first 2, you want to make it so you can put more weight on top.

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

              Understood, the more weight you can put on top, the change of getting optimal answer increase.

  • »
    »
    11 days ago, # ^ |
    Rev. 2   Vote: I like it +25 Vote: I do not like it

    Problem W:
    l[v] — left of v-th query
    r[v] — right
    a[v] — score for v-th query
    dp[i] — answer for prefix with length i if s[i] == '1'
    in naive solution dp[i] = max(dp[j] + summ(a[v])) for all j < i , for all v if l[v] <= i <= r[v] && !(l[v] <= j <= r[v]))
    it works in O(n^2)
    to improve it you need to use segment tree witch can give you max on prefix, for dp[i] = get(0, i — 1)
    so you need to keep tree valid at each iteration
    if you encountered left edge of some query make += a[v] on segment (0, l[v] — 1)
    if you encountered right edge of some query make -= a[v] on segment (0, l[v] — 1)
    when dp[i] is calculated += dp[i] on segment (i, i)

    UPD: "r[v] — 1" to "l[v] — 1"

»
11 days ago, # |
  Vote: I like it +35 Vote: I do not like it

will There be any Editorial??

»
11 days ago, # |
  Vote: I like it +97 Vote: I do not like it

I would like to request AtCoder to hold more such contests on various topics, such as one on range queries and updates, one on geometry, one on number theory and combinatorics, one on graphs, etc., similar to the dp one (where known methods are used in various ways to solve the problems).

I think this would be a great idea, helping many of us gaining the basics of topics quickly. Holding them at a every 10 days or so time interval would allow enough time to prepare the contest as well as give contestants time to upsolve the last one. I hope this is seriously considered!

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

    Totally agree, that would be awesome :D

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

How can i see testcases which my solution failed in this contest.

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

Thanks a lot to all the authors, the problems are really exciting.

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

Can anybody please explain the solution for problem Y — Grid 2 as well? I'm kinda stuck. :) Basically, on how to calculate the value of so many 's when both n and r can be upto 1e5?

»
9 days ago, # |
  Vote: I like it +14 Vote: I do not like it

How to solve V (Subtree)?

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

    Let's calculate two values for every node after rooting the tree:

    • down[node] = number of ways to paint the descendants of node when node is black

    • up[node] = number of ways to paint vertices not in the subtree of node when node is black

    The answer for any node is the product of these values, down[node] × up[node]

    down[node] is easier to calculate, it is (we let the subtree rooted at son all white or we have down[son] ways). The base case is when the node is a leaf, we have 1 way to color it black.

    up[node] is almost the same, (the 1 summing in the beginning comes from letting the parent white).

    The trick part with up is that the modulus will not always be co-prime with the values we got (so we won't be able to calculate the inverse modular by, let's say, maintaining the product of all sons and dividing by the current son down value to get the up[node] fast). The solution is to keep a prefix and suffix product of the down values for the sons of a node, this way we don't have to divide or use modular inverses.

»
9 days ago, # |
  Vote: I like it +12 Vote: I do not like it

Hello, everyone. Someone could explain to me how to make the problem Z — Frog 3 into something better than O (n ^ 2). Greetings and thanks in advance.

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

    To solve it in O(n2) we have the following recurrence,

    .

    Now, hi2 + c is constant for fixed i, and we have to minimise the second term.

    Now observe that the second term is of form y = mx + c, with (m, c) = ( - 2hj, hj2 + dp[j]) which we are evaluating at x = hi, which means we can use Convex Hull Trick to compute answer in O(nlogn).

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

      Just to add so there is no confusion, it is actually dp[i] = what you wrote + dp[j]

»
9 days ago, # |
  Vote: I like it +10 Vote: I do not like it

Is there a clean way to implement the solution for U? My solution used approx. operations, which is about 4e8 when n = 16 and ran in 1.9s (https://atcoder.jp/contests/dp/submissions/3969569), but I was curious if you could kick out that k factor from the sum and just get operations, which is like 4e7 on n = 16 and is much nicer.

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

    Yeah, check my submission: https://atcoder.jp/contests/dp/submissions/3948412. Precompute the sum for each mask to kick out the k factor.

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

      I actually did precompute the sums for each mask; that would create a k2 factor, I believe. My k factor was coming from creating all the subset-bitmasks for a given bitmask. Your line for (int ss = mask; ss > 0; ss = (ss - 1) & mask) is a clever way to generate them, that's pretty much exactly what I was looking for. Thanks.

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

    How to solve U?

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

      You must solve the problem for each subset of the input. Since n=16, we can use bitmasks to keep a dp array of the answer for each subset. On a given subset, try each sub-subset as a potential group and recurse.

»
9 days ago, # |
  Vote: I like it +10 Vote: I do not like it

So i just watched the new episode of Algorithms live where he and his guest talked about an O(n) solution to the problem L-Deque from the dp contest. I found this very interesting and implemented it. In fact, i found it so interesting that im writing this comment to let you all know about it :)

»
7 days ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

In Matching, I failed only at one test. I could not find bug in my code. Can anyone have a look? Thanks. My submission.

Edit: I fixed it. My above code fails for the test "1 1".

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

does there exists better solution for O-Matching than O(2n * n2), or it was intended to pass recursive solutions, while failing iterative?

  • »
    »
    6 days ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    We can solve in O(2n * n) iteratively as well. We don't need the second dimension. Let k be the number of 'on' bits in the mask. dp[mask] represents number of ways in which first k men can pair with any k women subject to their preferences being matched. We can derive answer for current mask by turning off singular bits from the mask and checking compatibility of the k'th man being placed at this position.

»
6 days ago, # |
  Vote: I like it +10 Vote: I do not like it

Can someone explain the states and transitions of dp in problem T-Permutation. It got me thinking for a while now, and still don't get it. thanks in advance

»
6 days ago, # |
  Vote: I like it +10 Vote: I do not like it

Nice problems. Anyway how to solve C (vacation)?

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

    dp[i][j] = i'm now considering the i'th day and I did the task j (A or B or C) at previous day((i-1)'th day). So I can't do the task j in this i'th day.

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

Can anyone explain any other approach to solving S-Digit Sum, apart from digit dp, well I'm getting a MLE by the digit-dp approach!

Or can you provide an optimization to solve my error!

My submission

Thanks in advance!

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

    you got RE(Runtime Error) not MLE(Memory Limit Exceeded)

    Try again fixing these:

    1. the maximum value of your num.length() can be 10001, not 1005
    2. now if you think, you'll get your state sum is not good enough to be a DP state here as it can be big(<=9*10000) As we just only need to check "The sum of the digits in base ten is a multiple of D", instead of exact sum we can consider a state sum modulo D.
    3. in line 100 you are going to start working with index 0, how you are considering start as 1? Think again.
    • »
      »
      »
      5 days ago, # ^ |
        Vote: I like it +10 Vote: I do not like it
      1. I know, 1005 was made atleast to make my code run...1e5+1 will not run the code, you'll get a compilation error :(

      2. OK, this is naice!

      3. start is a state which specifies whether I'm in the most significant digit of a number or not.

      As far as point 1 is considered check this out

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

How to solve M — Candies?

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

    dp[pos][j] =  number of ways of distributing j candies among [1, pos]. You can use prefix sums for transition between the states. Solution.

»
4 days ago, # |
  Vote: I like it +10 Vote: I do not like it

Can anyone explain how to do O-Matching problem?

Elaborate The dp states plzz!!

  • »
    »
    4 days ago, # ^ |
    Rev. 5   Vote: I like it +11 Vote: I do not like it

    F(mask) = number of ways to match all girls with 1-bit in mask with first P boys (P = number of 1-bit in mask)

    Answer is: F(1111) — full mask

    Transition:

    F(mask) = SUM( F(submask) )

    Where submask all subsets of mask without only one 1-bit (if it is possible to marrige P-th boy with this girsl)

    For example:
    F(1011) =

    if it is possible to marrige 3-d boy with 1-st girl
    F(1010) +

    if it is possible to marrige 3-d boy with 2-nd girl
    F(1001) +

    if it is possible to marrige 3-d boy with 4-th girl
    F(0011)

    We try to match P-th boy to every available girl (1-bit is a free girl)

»
67 minutes ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Why this O(MAX_DIGIT_LENGTH * D) solution timed-out for S-Digit Sum given that MAX_DIGIT_LENGTH<=10000 and D<=100 .

UPD: Got it. :) Passing string to the function caused TLE.

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

    Because of this: int solve( string s ,int idx,bool smaller,int rem),
    add "&" here: solve( string & s ,int idx,bool smaller,int rem)

    • »
      »
      »
      30 minutes ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah I realized that. Thanks for reply though.