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

Автор BledDest, история, 4 месяца назад, перевод, По-русски,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Разбор задач Educational Codeforces Round 21
 
 
 
 
  • Проголосовать: нравится  
  • +78
  • Проголосовать: не нравится  

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

Автокомментарий: текст был обновлен пользователем BledDest (предыдущая версия, новая версия, сравнить).

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

If we are able to solve problem E by iterating over all possible values of 3-weighted objects + dp on triple (cost, cnt1, cnt2), can we just solve it with dp on quadruple (cost, cnt1, cnt2, cnt3)? Better, can we solve any knapsack problem with N distinct weights with dp on (N + 1)-uple (cost, cnt1, cnt2, ..., cntN)?

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

    Well, it seems that it doesn't work. Can someone explain why it works for two values and not for three?

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

      I have the same doubt with you! I also what to know how to use ternary search sloving this problem.

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

        Have you solve this? If not, you can read my code, I use ternary search to solve this problem.

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

          I am sorry for that I saw your reply too late.But does your code is use ternary search? I consider ternary search is trie but your code is use binary search. Anyhow, thanks your new idea.

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

      Consider the case n=4, m=7 with items A=(1,3), B1=(2,4), B2=(2,4) and C=(3,6).

      Then the (only) optimal solution for dp[4]=A+C, for dp[5]=A+B1+B2, dp[6]=A+Bx+C and dp[7]=B1+B2+C, but there is no way to create the solution for dp[7] by adding items to any of the three solutions before.

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

        It apparently doesn't work for weights 1, 2 and 3. but can you give a proof that it works for weights 1 and 2 only? I can't figure it out.

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

          When you have only two weights, you can solve the problem greedily: first take the minimal number of necessary items so there is a multiple of the lcm remaining (in this case this means taking a single item of weight 1 when the wanted sum is odd) and after that greedily take the best groups of a single item of total weight equal to the lcm until you have the wanted sum (in this case this means either taking a single item of weigth 2 or two items of weight 1).

          It is then relatively easy to prove that the dp solution gives the same results as the greedy solution above (for example by induction).

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

            Why can't we make the same argument for three numbers 1, 2, 3 with lcm 6?

            At a given state there could be 6x + a number of 1's, 3y + b number of 2's and 2z + c number of 3's. So if we consider all values of a, b and c for dp transitions, it should work right?

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

        thanks your sample, it very useful for me because my poor dp skill.

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

        Many thanks! Your example was extremely useful. I've managed to solve it with quadruple dp. The point was in trying to change dp[m-1] or dp[m-2]. If they have 1-element, it can be replaced with more expensive 2-element or 3-element respectively.

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

      I tried this method, and got several WA, but finally received an AC. If you take 1&2&3-element in consideration at the same time, then there are four possible way to renew dp[i]:first:dp[i-1]+ 1-element; second: dp[i-2]+ 2-element; third: dp[i-3]+ 3-element; ※fourth: dp[i-2]- 1-element+ 3-element.What's more, it can be proved that all other way is equal to the four ways above. This is my AC code: http://paste.ubuntu.com/24652108/

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

any suggestions how this solutions for D was hacked? http://codeforces.com/contest/808/submission/27138172

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

what does unexpected verdict during hacking mean?

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

My solution of E is a kind of greedy and Dp solution. In this problem we have a knapsack problem. The knapsack has a size much bigger than the size of its components. So we can make a greedy approach until the size of knapsack is X, then make a knapsack DP on the rest of components on a knapsack of size X. I fix X = 300 (3*100 ) arbitrarily. A doubt: How we can find the minimum X that we guarantee a optimal solution in this case? :p My solution:http://codeforces.com/contest/808/submission/27144481

Edit: It is Wrong! Sorry!

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

    It is wrong because if you have, for example, one souvenir with cost 5 and weight 3 and then two hundred souvenirs with cost 3 and weight 2 and you are able to carry 400 weight, you would greedily choose the 3-cost souvenir right at the start, which is not optimal.

    Now, what if you make sure you leave enough unpicked items of each weight before the end of the greedy phase? That is, you refuse to pick the item with the best cost-to-weight ratio if it makes your list with that specific weight too short. Then, the dynamic programming should have enough of each weight to optmize the remainders of the knapsack.

    My intuition says this approach should work, but I can't come up with a proof or even the right limits for when to start the DP and for how many items of each weight we should keep.

    EDIT: Nevermind, it's just wrong. Unless there are specific and artifical limits on the costs of the items, one greedy choice in enough to make the algorithm incorrect.

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

Ignore

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

    Flow network must be oriented, that isn't said in the editorial. Hope that this will help someone

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

I am not able to understand letter E, can someone explain me more clearly please ?

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

Can anybody explain why we just need to optimize the 'cost' in problem E solution without regarding to the 'cnt1' and 'cnt2' ?

Much appreciated!

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    if(dp[i - 1].cnt1 < t1 && dp[i - 2].cnt2 < t2) 
        if(dp[i - 1].cost + c1[dp[i - 1].cnt1] > dp[i - 2].cost + c2[dp[i - 2].cnt2]) {
        *****//renew dp[i] //********
        }
    

    my code is a implementation of E in editorial, cnt1 and cnt2 can be used to determine how to renew dp[i](like above). Here it is 27157016

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

      I mean, why we ONLY need to optimize(maximize) the COST.

      The cnt1 and cnt2 definitely means something. But why we can ignore it.

      I want a proof or something like that.

      my code here 27149084

      and another code using quadruple get WA which I cannot figure out why. 27163738

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

        Hey, can this be cleared out. If coldwater got it or anybody, please tell why there is WA with 1, 2, 3 and cost together but not with 1, 2 and cost?

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

Can someone explain the ternary search solution to problem E?

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

    keep the best m elements of weight 1

    keep the best m/2 elements of weight 2

    keep the best m/3 elements of weight 3

    sort all of them in non-increasing order

    sum[i][j] is the sum of the first j elements of weight i

    /* from the editorial above

    We can iterate on the number of 3-elements we will take (in this editorial k-element is a souvenir with weight k). When fixing the number of 3-elements (let it be A), we want to know the best possible answer for the weight m - 3A, while taking into account only 1-elements and 2-elements.

    */

    let y be m — 3A , we need to take B 2-elemensts and C 1-elements with total weight equal to y

    y = B*2 + C*1

    we will take the first B elements of weight 2 and the first C elements of weight 1

    the ternary search is on B with this function F(i) = sum[2][i] + sum[1][y-2*i]

    it is correct because F(0) <= F(1) <= .... <= F(B) >= F(B+1) ...>= F(m/2)

    and we are searching for the best B

    the answer will be : sum[3][A] + sum[2][B] + sum[1][C]

    take a look at my code if you need : code

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

      Can you give me your evidence to prove prove that F(0) <= F(1) <= .... <= F(B) >= F(B+1) ...>= F(m/2)

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

        I also dont get this. What if last 1-element ( that has least price) has bigger cost than first 2-element (has highest cost of all 2-elements) ? then F(0) >= F(1)

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

        B isn't literally bigger than 0 and less than m/2

        it might be 0 or m/2

        the idea is that the graph of the function F is increasing then at some point is decreasing

        it's correct because we sorted the 3 types of elements in decreasing order

        when we take 1 more 2-element with sum greater than the last 2 1-elements we took before the answer is increasing

        but at some point , taking 1 more 2-element with sum less than the last 2 1-elements we took before the answer will start to decrease

        you need to try an example to understand it well

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

      Why do u take first m/2 elements of weight 2 and m/3 elements of weight 3? Maybe in optimal solution we will take worst element of weight 3? Please explain. Also, any good reference on ternary search? Edit: wow, cant believe I asked this..thanks for reply

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

        Cos it maximal number for 3-w elements could be only m/3 and for 2-w m/2.

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

      Does ternary search still work if we iterate on the number of 1-elements?

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

      I thought ternary search is only possible when the function is strictly increasing then decreasing (or vice versa). How come this still works if you have the <= instead of < in this case?

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

        It works because in this case F(0) < F(1) < .... < F(B1) = F(B1+1) = ... = F(B2) > F(B2+1) ...> F(m/2). If there also are equal elements in other places, you are right and ternary search is not guaranteed to work.

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

I don't understand D?

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

    Here's one approach.

    Maintain two multisets, one for prefix elements and one for suffix elements. Traverse through the array in the given order and keep prefix and suffix sums as you traverse. Also maintain the two multisets, adding the current element in prefix multiset and erasing it from suffix multiset.

    If prefix sum is greater than suffix sum, search in the prefix multiset for their difference halved. If such element exists, output YES.

    If suffix sum is greater than prefix sum, search in suffix multiset. If you can't find such element, output NO.

    Corner Cases: When n=1, answer is always NO.

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

      I traversed the array both ways keeping the sum of all elements encountered. Then when ever the sum is exceeding the half of the total sum I'm checking whether the difference has been encountered. This means I'll be able to spot an element which i have to remove from the prefix and add to the suffix in order to get the answer. 27175419

      Please let me know if I have miss understood the question.

      EDIT: This is the working solution 27176375...

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

    Here is how I solved it:

    Remember the partial sums (let the sum of the first i terms be s[i]). If s[n] is odd (total sum) then you can't divide it in 2 of the same sum. In the case s[n] is even:

    Iterate i from 1 to n. For every i check if s[i] == s[n]/2 (you can remove a number and place it in the same spot). If yes output and you are done. Otherwise, do binary search over the first i elements of s (the terms are positive so s is increasing). Search for s[n]/2-a[i] (so if you move i to a position j, j < i, you can just look at the first j and the rest).

    Then do another binary search on i+1, n and search for s[n]/2+a[i]. (you would move i at position j, i < j, and the sum of the first j-1 is s[j-1] — a[i], which you need to be equal to s[n]/2. so you need s[j-1] = s[n]/2 + a[i])

    Hope this helped!

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

Problem F is something good to learn about mincut , thanks

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

I think problem F is solvable with binary search + edmond blossom with a complexity O(N^3logN), not sure if it would pass.

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

Can anyone explain binary(not ternary!) search solution for problem E (if there is one)? I tried to solve it this way with binary search but it fails on test case 9: separate elements in 3 arrays, every weight goes in one of them. Sort arrays Lets fix number of 3-elements we will use. then I do 2 steps: 1. step — first binary search for number of 2-elements, and while doing that, binary search for number of 1-elements (so binary search in binary search :D ) 2. step — same but oppposite: first binary search for 1-elements, then binary search for 2-elements inside. Why we do bs in bs twice? Because maybe optimal solution is to take 0 2-elements and 100 1-elements, so if we just binary search for 2-elements first, then we may skip this solution.

code: http://codeforces.com/contest/808/submission/27160206

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

Does problem D mean that we get to swap the elements? For instance, example #3 shows that we need to swap the elements 3 and 4 to make the sums equal. (2 2 3 4 5) -> (2 2 4 3 5). I'm asking this because it did not work, obviously :(.

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

    Not swap elements, just PUT one element in different position. In example above, you took number 3 and put it right from number 4. Number 4 didnt move anywhere, but it seemed as it did because you moved 3 from its position.

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

    In general, no, you cannot swap two arbitrary elements, you are only allowed to remove one element and place it somewhere else. Notice, hoewever, that if you take the 3 of (2, 2, 3, 4, 5) and place it one position to the left, the final result is equivalent to that of swapping it with the 4.

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

      So, from what I understand from your kind answers, there are two cases

      1. Removing an element from prefix(or suffix) and add it to suffix(or prefix), which means <sumPrefix — element, sumSuffix + element>
      2. Moving an element at the boundary of prefix / suffix in which case, the swap happens <sumprefix — prefixElem + suffixElem, sumsuffix — sufixElem + prefixElem>

      Please correct me if I'm wrong

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

        If I understand what you are saying, you are correct, but there is no need to divide the problem into two cases, the second one is just a particular occurence of the first.

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

    is it allowed to swap more than 1 element? isnt this np ?

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

Another approach for E: Sort all souvenirs in decreasing order by cost / weight (if equal it's better to choose souvenir with least weight).

Now pick greedily up to m - X weight (we'll choose X later). After that we have res + X weight to fill (1 <  = res <  = 3 — residue after greedy stage of algorithm).

Now we'll use naive approach (either standard knapsack dp or even iterate on all possible counts of 1-souvenir, 2-souvenir, 3-souvenir). It turns out as far as we have really small weights, we can choose X to be relatively small (intuitively we can choose X to be 3 * 3 + 2 * 3 + 1 * 3 = 6 * 3 = 18).

My submission http://codeforces.com/contest/808/submission/27144235 so feel free to hack it;)

P.S. For ones who might want to understand crappy code above. In submission I have 3 vectors (for 1-souvenirs, 2-souvenirs, 3-souvenirs respectively) and 3 pointers to handle greedy picking souvenirs and loops at the end.

Edited:

Thanks @lewin for the hack. Yeah, interesting. I was pretty sure this approach works:) Gotta find out if it's a bug or incorrect approach

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

    This comment proposed a similar solution, and you can see my counterexample as an answer.

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

      In fact I still believe this approach works with the following tune: After greedy step we have to remove worst 3 1-souvenirs, worst 3 2-souvenirs, worst 3 3-souvenirs and perform naive approach (looping and knapsack dp).

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

What if we have several pairs of cnt1, cnt2 for optimal cost dp[w]?

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

What is the time complexity of D using sets of search.

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

Here is another approach to problem E. Suppose we have only two kinds of weight, 2 and 3. Then we can easily solve the problem with sorting and (two pointers or binary search).

The main idea is that we can reduce the main problem to this easy one. Solve the problem twice: choosing odd number of items of weight 1, or even. If we decide to choose even, we can pair the weight-1 items and convert them to weight-2 items. And if we decide to choose odd, first pick the biggest item of weight 1. The remaining part is same as the even version.

27164728

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

    Such a beautiful solution. While trying to solve problem, I also came on idea to pair weight-1 items to get weight-2 or even to take triples of weight 1 items. But I thought that it wont be correct because it may be optimal to choose only one weight-1 item. Now I see — either you pick greatest weight-1 item and pair others, or you pair all of them... Thank you.

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

    Why can this subtask be solved using greedy approach unlike thr initial?

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

      Initial problem can also be solved with greedy approach(selecting the most valuable items from each group). But the time complexity will be O(N^2) as we have to deal with 3 groups. After reducing the number of groups from 3 to 2, the problem can be solved in O(N log N).

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

http://codeforces.com/contest/808/submission/27164939 About the problem E ? I don't think is wrong. Who can help me?

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

In G you don't need to consider all 26 characters. From position j you either move forward by tj or you start from position P(j), where P is prefix function. My solution for reference: 27165597

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

I thought I understand DP solution for E, but then I realised that I dont. Here is my problem; lets say that dp[i].cost = x. then you say we update dp[i+1], dp[i+2],dp[i+3] with this value. But what if there is way to get weight i, with cost y, such that y < x, but in that case we used less elements of weight 1 lets say. So, maybe dp[i+1] will be better if updated with cost y + cost of next weight 1. Am I right?

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

    I don't think there is a difference due to the fact we use best k-elements available. For instance, to get x you use 1-elements e1[1] + ... + e1[m] (in sorted order) and to get y e1[1] + ... + e1[m -1]. You claim that y < x and y + e[m] > x + e[m + 1] (if e[m + 1] exists) which is obviously wrong, in worst case (if e[m + 1] doesn't exist) y + e[m] = x, so y can't be strictly bigger than x, I suppose.

    Edit: y + e[m] can be bigger than x in worst case, of course, if we take into account 2 and 3-elements , so the question remains unanswered.

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

      Yeah, I wanted to say you that you didnt count 2 elements and 3 elements, and then saw that you updated comment. So, anyone with answer?

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

    You can not update [i+3] state choosing only from 1s and 2s. And we don't care about free souvenirs, we will use the most expensive of them anyway. Example: 1-w: [2 3] 2-w: [2 5] m = 2. dp[0] = {0, 0, 0}, dp[1] = {3, 1, 0}. dp[2] choosing from (0 + 5) and (3 + 2). They are equal, so two variants of new tuple: {5, 0, 1} and {5, 2, 0}. But we are interested only in the first value, and it must be the biggest. if (cost of 1-w + 1-w) == (cost of 2-w) we could use any of them (weights are equal) and use another later if have extra weight reserve.

    Sorry if I didn't unserstand you question and wrote something strange :D

    My realization if needed: http://codeforces.com/contest/808/submission/27421196

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

There is some bug with my solution: http://codeforces.com/contest/808/submission/27133213 Does anybody know how to fix it?

UPD. Bug disappeared. It's ok now.

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

why F we can't use more than one card of magic number is 1?

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

Could someone please help me understand as to why greedy approach of G not correct. As i am replacing the given string in the specified string from back and then count the total number of the given string .Any explaination of this would be really helpful .

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

    Dude, u better change your dp before asking any question.

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

    Consider s1 = "a????bcab", s2 = "abca????b" and t = abcab.

    For s1 optimal answer is "aabcabcab" and for s2 it is "abcabcabb", and t occurs 2 times in both of these.

    If you do greedy from front, you'd get "abcabbcab" as answer for s1, which has 1 occurrence of t.

    If you do greedy from back, you'd get "abcaabcab" as answer for s2, which has 1 occurrence of t.

    Hope this helps!

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

      Thanks Dude but could you help me understanding the dp approach ?

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

        Do you know the KMP algorithm and understand it well?

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

          i know KMP algo but dont have a deep understanding of it just basics !

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

            My solution is here.

            There are two main functions pre and go.

            In pre, first I create the table b where b[i+1] stores length of longest proper suffix (which is also its prefix) of the string p[0:i+1] (substring of p starting at 0 and of length i+1). Then I calculate n[i][j] which is same as the next array defined in the editorial.

            My go function now uses the above two arrays to calculate the dp and cnt values. dp[i,j] tells if there exists a placing of characters such that last j characters of s[0:i+1] are same as first j characters of p.

            Use this information and try to understand the code, and why it is correct.

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

I got TLE in this code for problem B can someone please point out the error??

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

What is the time-complexity for D?

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

    O(n log(n)) if you use something like std::set to maintain the elements on the prefix.

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

      I thought of the same complexity, but i thought it was wrong. Thank you :)

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

How do we do ternary search (or its reduction to the binary search version) for E if it isn't necessarily true that the function is strictly increasing/decreasing?

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

    See my comment: http://codeforces.com/blog/entry/52010?#comment-360483 Here I explained my TRY of binary search inside binary search. It passed 9 test cases and I didnt really try much to debug it. But from my solution you can see that you can do bs. If you separate items (weight i in group i — so 3 gruops totally) and then sort, you have increasing function.

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

      Isn't it only nondecreasing, not increasing?

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

        Well for binary search non decreasing is ok. And I cant help you with ternary cause I also have problems with that solution.somewhere here in comments there is ternary search solution written but I dont understand why function is first increasing and then decreasing (user didnt prove it, he just said it).

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

How did this randomized solution 27148367 pass 808F - Card Game ?
Are the test data too weak or the probability of success is really high?

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

In Problem F, I get WA test 11.

Can someone help me please? My solution ==> 27199504

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

In problem G: what are other ways to represent the states? thanks

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

My code http://codeforces.com/contest/808/submission/27212742 for Problem A is running wrong in test case 2, for input 201, when checked in submission it shows output 96, whereas in my compiler and other online compilers it is showing output 99, don't know what to do.. help if possible...

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

    Rounding inside pow() differs slightly among implementations (details here), so surrounding pow() with another round() fixes the issue. It's usually preferred to use exponentiation by squaring when exponents are integers, though.

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

I am getting WA on test 21 for problem D ,although I checked it with lot of hack cases. Any help would be appreciated. http://codeforces.com/contest/808/submission/27217259

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

problem:G... first I am finding in string s, all the possible positions where the string t can end and storing in boolean array, eg for (win???dwin,win) f=[0,0,1,0,0,1,0,0,0,1] . And then I am finding the LPS for string s. And then using this DP state :(lt=len of string t,ls =len of string s)
for(i=lt;i<ls;i++) { if(flag[i]) dp[i]=dp[ i-lt+lps[lt-1] ] + 1 ; else dp[i]=dp[i-1]; } I am getting right answer for most of the test cases...except test cases 56,60,64. Can anyone pl explain why am I getting WA for these test cases.

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

there is another solution for problem E. we can sort the array and select front item greedily, then do some fix to generate right answer. 27342219

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

Why cant E be solved by simple 0-1 knapsack problem like this?

http://ideone.com/EiWMGd

What is wrong in this approach?

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

    It's O(n*W) which is too slow for this task.

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

    Yes exatly. First thing which came to my mind after reading problem statement was knapsack. But then I read editorials but doesn't makes much sense to me. Will someone care to explain why this isn't plain knapsack problem?

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

Here's (another?) solution for E.

My greedy algorithm calculates answer for state with weight not more than w + 1 using the value of only state w. For this there are three types of transitions add one 1 - element to w state, add one 2 - element and remove one 1 - element from w state; or add one 2 - element to w state.

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

Can somebody explain why my solution fails on test case 21. Here is my submission