Ashishgup's blog

By Ashishgup, history, 6 years ago, In English

I hope you guys enjoyed the contest — I hope to host another one soon :D

With that said, here are the tutorials:

Tutorial is loading...

Author's Code: 42591712

Tutorial is loading...

Author's Code: 42591830

Tutorial is loading...

Author's Code: 42591846

Tutorial is loading...

Author's Code: 42591882

Tutorial is loading...

Author's Code: 42592019

Tutorial is loading...

Author's Code: 42592026

Tester(cdkrot)'s Code: 42593206

For O(n3) or O(n2) solution, refer to this comment by pranjal.ssh

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

| Write comment?
»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

The proof to the greedy approach in Problem C is interesting!

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

    I didn't understand the +0.5 part, can someone explain please ?

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

      Me too

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

      For my understanding:

      Let A be the sum of a[1] / 2 + a[2] / 2 + a[3] / 2 + ... + a[n] / 2,

      and B be the sum of b[1] / 2 + b[2] / 2 + b[3] / 2 + ... + b[n] / 2.

      The list of the 1st player becomes a' = {a[1] / 2, a[2] / 2, ..., a[n] / 2}.

      The list of the 2nd player becomes b' = {b[1] / 2, b[2] / 2, ..., b[n] / 2}.

      Now, the problem tells us that the 1st player will play to maximize the amount A - B. For this player the process of choosing a number a[i] is equal to adding the halved-value element a'[i] to A, and choosing a number b[i] is equal to subtracting the halved-value element b'[i] from B, so the 1st player has two choices: either to increase A or to decrease B, and with any of them the amount A - B will increase, so he should choose the element that affects more, so he should choose the maximum element between a[i] and b[i] (where a[i] and b[i] are the maximum elements in a and b, respectively).

      For the second player, he want to maximize the amount B - A, and in a same discussion as above we can see that he should choose the maximum element.

      Hope this will help.

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

        @aboAdnan Thanks for your answer, unfortunately I still don't understand the /2 ? why don't you do the same reasoning without dividing by 2 on both sides ?

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          It's a way to show how choosing an element from the second list affects the answer of the first player.

          Because, without /2, when the turn is, for example, to the first player, adding an element from his list will increase A, so will increase the difference A - B, but removing an element from the 2nd player's list will not increase A neither decrease B, so the amount A - B will not change.

          But sometimes, we can see that removing elements from the other's list will help more than adding elements from my list. And to show this, the /2 was helpful.

          Anyway, I'm sorry that I couldn't help you, maybe someone else will help more.

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

            Can you tell me how I_love_Tanya_Romanova solve this problem. Here is the link 42562135

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

              My solution is the same as one described in editorial, and the reasoning that I used during the contest is similar to what described in editorial — thinking like "both taking X away from your opponent and picking X from your list has same impact on your final score".

              I'm just simulating the game and keeping track of scores.

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

              He stores the two lists in one vector, then sorts this vector (then reverses it, so sorts them in non-increasing order), and continues choosing the remaining biggest number.

              The editorial, instead, stores each list in an array, then sorts them both, and keeps one pointer on the remaining biggest number in the first list, and another pointer on the remaining biggest number in the second list, then it chooses the biggest between the two number that the two pointers points to.

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

     + 1

»
6 years ago, # |
  Vote: I like it +67 Vote: I do not like it

Excellently organized contest with short and precise problem statements.

Well done Ashishgup and Mahir83 !

»
6 years ago, # |
Rev. 4   Vote: I like it +26 Vote: I do not like it

Problem E. We can delete all loops because if we stay on vertex we can take all loops.O(n) solution we know that number of vertexes which has odd degree can be only 0, 2, 4. Because if 3 vertex has odd degree sum of all degree not divide on 2. It means if number of vertexes which has odd degree 0 or 2 graph has Euler path, it means we can take all edges. If number of vertex which has odd degree 4 we have two case. 1 case number of components equal 1 and number of components equal 2. If number of components 2. Each component has Euler path we take max. If number of components equal 1, we can take all edges except 1 edge. Sorry for my english.

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

    "It means if number of vertex which has odd degree 0 or 2 graph has Euler path, it means we can take all edges." No, if the graph has edges in different connected components, there is no Euler path in this graph.

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

      I mean each component has Euler path. It means we can take all edges in component.

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

        Okay. What about this?

        "If number of vertex which has odd degree 4 ... If number of components equal 1, we can take all edges except 1 edge." By deleting this edge, we can make this graph disconnected.

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

          No. Because obviously that at leas two vertexes should has degree grater than 1. It means if we delete edge number of components didn't change or we just delete one vertex.

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

            If the graph contains loops, this statement is untruth.

            Example: test #117.

            Input

            If you delete any edge from this graph, it will not have Eulerian path.

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

              I told we delete all loops in begin and in the end add to answer. We can delete loops because if stay in some vertex we can visit all loops in this vertex.

              • »
                »
                »
                »
                »
                »
                »
                »
                6 years ago, # ^ |
                  Vote: I like it -11 Vote: I do not like it

                So some deleted loop can become new connected component. Look at my example in previous message.

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

                  We delete loops in start. We calc degree of vertex without loops.

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

    My AC solution 42591906

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

      Submit again and see if it passes test #117 :P

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

      I require some assistance in understanding your solution.

      Firstly, the number of vertices with odd degree is 0, 2 or 4. It cannot be 1 or 3 because then the sum of degrees of each vertex would not be even.

      Case 1 — The number of odd-degree vertices is 0

      We can take the whole graph

      Case 2 — The number of odd-degree vertices is 2.

      You have written that we can take the whole graph, but I did not understand why. Please explain.

      Case 3 — The number of odd-degree vertices is 4.

      Case 3a — There is one component — Take the full graph

      Case 3b — There are two components — Take whichever component has a higher sum.

      I hope I summarised your solution correctly, but I didn't understand Case 2 and Case 3. Please help me understand your solution.

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

        This isn't quite right. For case 3a, we take the full graph except for a single edge.

        It's well known that a graph has an Euler circuit if and only if there are no vertices with odd degree, and a graph has an Euler path if and only if there are exactly 0 or 2 vertices with odd degree. This means in these cases we can take every edge.

        When we have 4 vertices of odd degree and a single connected component, we can remove an edge to get back to the earlier case. Therefore we should remove the minimum weight edge that connects two different nodes.

        If there's two components, we can obviously only take one of them. This is a graph with two nodes of odd degree, which has an Euler path. Take all the edges in this component.

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

          As you said before, "When we have 4 vertices of odd degree and a single connected component, we can remove an edge to get back to the earlier case. Therefore we should remove the minimum weight edge that connects two different nodes."

          I am doing this but this gives WA I think this is happening because if after deleting the "minimum weight edge" , the graph may divides into two divided components resulting in the different answer. Test case 117 is about this only. 6 1 10 1 1 2 2 2 10 3 2 20 3 3 1 4 4 10 4

          We should delete "3 1 4" but this will make graph disconnected and we will also have to remove the loop on 4 itself .

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

    This solution is not O(n). It is plain wrong if n > 4.

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

      Sorry O(M).

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

        You probably don't understand big-O notation. Solution works in O(f(n)) if there exist c > 0 and N such that for all n > N the number of operations is no more than c·f(n).

        But your solution can't work for n > 4.

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

          I think you might be talking about different things. In this problem, there are always at most four vertices, and n is the number of edges. The solution is correct (because the problem is only defined for small number of vertices) and O(n).

»
6 years ago, # |
  Vote: I like it +76 Vote: I do not like it

F can be solved in O(n3), by counting strings based on the KMP state after reading whole string. As string is cyclic we want the KMP state to start and end with same state and somewhere in between the KMP state should be |S|. See my code for details

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

    Interesting solution! I have added a link to your comment in the editorial :)

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

      It can also be reduced to O(n2) by doing forward and backward dp from the first position where KMP state becomes |S|. Code

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

        How does the O(n^2) taking more execution time in compare to O(n^3)? pranjal.ssh Can you please clarify your approach or explain your solution a little bit more?

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

    Can u explain more clearly ? Please.

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

In Problem D, Why in the solution code of the author he say that when all of numbers are positive or all of them are negative then answer is ans-2*minValue ?????

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

    Because he adds it to the variable ans in the loop.

    For example, a = {3, 4, 5, 6, 7}, the answer of this case is:

    4 + 5 + 6 + 7 - 3  =  19.

    But in the loop he adds all the element to ans, so ans have 3 in it, so he should remove the number 3 two times from ans in that case:

    ans = 3 + 4 + 5 + 6 + 7 = 25, so the correct answer is, ans - 3 - 3.

»
6 years ago, # |
Rev. 2   Vote: I like it +30 Vote: I do not like it

I think The easiest way to solve problem B was to take 'n' in one set and the rest 1 to n-1 in another set. why does this work? As the sum of 1 to n-1 is n * (n-1)/2, so, the gcd of n and n*(n-1)/2 is always greater than 1. My Submission : http://codeforces.net/contest/1038/submission/42567986

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

    How did u reach the conclusion that gcd of n and n*(n-1)/2 is always >1

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

      If n odd it means n — 1 is even hence n * (n — 1) / 2 is divisible by n. If n even let say n = 2 * k it mean n * (n — 1) / 2 = k * (2k — 1) is divisible by k and 2 * k is divisible by k.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      you can take n common from n*(n-1)/2 and n*1, as n is dividing both of the numbers.

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

        Definitely wrong!!!! check the above comment

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

        yes that seems like the obvious explanation. but it isn't true because if u take n common what is left in the first part is (n-1)/2 and it is not guaranteed that it is an integer as (n-1) could be odd or even.

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

I m not able to get AC even after referring to solution for problem C. Please help !!!

I have attached link to my solution 42593499

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

    I'm not exactly sure why did you use sum of arrays a and b. You don't need it. Refer to my solution if you want, I think it's same as editorial says. I made 2 functions, one for player A, one for B. I hope it helps :D

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

      Brankonymous: u have sequentially add the values selected by the players from their own to ans_a, ans_b respectively and i have subtracted the values from suma and sumb that have been removed by opponent.

      I didn't understand why there is comparison of a[f] and b[g] in your solution ? Frankly speaking I didn't even understand argument about "each player gets 0.5 of all numbers in his list" given in editorial which is used to explain O(nlogn) solution.

      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        Well I use f to have index array a, and g to have index of array b. Sort array and declare f ang to n-1 (because that index is biggest) And let's look at player A because he goes first. If he sees that b[g] is bigger than a[f] that means that optimal solution is to substract g by 1, so player B won't put b[g] in his list. Otherwise put a[f] in A's list. Because we used a[f] substract f by 1 so that we will se biggest number in a not used.

        Do the similar thing for player B.

        And do it until f and g is out of bounderies.

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

still, haven't understood the problem D... So, anybody can give the proof of correctness for D???? thanks in advance....

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

    Let pos be the number of positive numbers in the array,

    and neg be the number of negative numbers in the array.

    If pos > 0 and neg > 0, so you can let each negative number eat the positive numbers to the left and right of it, so the result of each process of eating will be a negative number also (because negative - positive = negative), and keep one positive number alive, so the array will become like following: {some negative elements, one positive element, some negative elements}, so this remaining positive element can eat any negative element with still being positive (because positive - negative = positive), so the answer of this case is the sum of all absolute values of the initial values.

    But when all the elements are positive (neg = 0), we should create a negative element to return to the previous case. And to create a negative element in this case we should let an element eat any other neighbor element which is greater than the element which eats, for example, a[i] - a[i + 1] = negative element, after that the answer will be the sum of the absolute values of the values remaining after this process of eating (as the previous case exactly). But we shouldn't forget that we remove an element (i.e. a[i]) to create the negative element, so we should choose a[i] to be as small as possible.

    And when all the elements are negative (pos = 0), we should create a positive element to return to the first case. And choosing the element that has to eat other element is discussed as the previous case.

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

      Thank you..

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

      Many thanks mate ! You told the intuition behind the editorial. It really helped a lot.

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

        Happy to hear this :D. Wish you all the best!

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

      Wow, what a amazing explain :3 tks u alot for help me understand :3 the world need more people like u :3

»
6 years ago, # |
  Vote: I like it +39 Vote: I do not like it

Thanks for allowing exponential solutions to pass for F! http://codeforces.net/contest/1038/submission/42588924

Let m=s.size().

If m>=20, we just fix s as the prefix of t and brute force the remaining 2^(n-m) possibilities and carefully count the number of rotations that will work. This part is O(2^(n/2)*n)

Else, we brute force the prefix of length (m-1) of t and there are 2^(m-1) possibilities. This is a standard trick to convert cyclic dp to array dp, which is easier to think of for stupid people like me.

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it -24 Vote: I do not like it

    That's a nice approach as well. We were wondering if there was an exponential approach to solving this problem, while setting it up, but failed to came up with one! Something new learnt :)

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

Alternative solution for E (harder to implement but was easier to come up with for me): While there are 3 or more edges between two colors, we can remove two most valuable edges and note that if any of these vertices is visited than we need to add the value of all corresponding removed edges. Now there are no more than 2 (edges per color-pair) * 6 (color-pairs) = 12 edges. The graph became small enough to bruteforce all possible edge-paths: After making 11 steps there will be only 1 edge left so we won't have a choice at that point. First 11 times there will be no more than 3 (number of other colors) edges to choose from. This gives an upper bound of 3^11 = 177147 node traversals. We will need to try starting at all four colors so the final number is 4 * 3^11 = 708588. In practise it works surprisingly fast: 31ms. If you for some reason would like to look at my solution: https://codeforces.net/contest/1038/submission/42595983

»
6 years ago, # |
Rev. 4   Vote: I like it +18 Vote: I do not like it

My alternative bruteforce Solution for E, without any nasty graph theory and bitmasks https://codeforces.net/contest/1038/submission/42586454

the Idea here of this solution is that we can divide the blocks into 6 type of block (block with color (1,2), (1,3), (1,4), (2,3), (2,4) (3,4) ) (since (1,2) is equal to (2,1))

for blocks that has the same color (1,1) (2,2) (3,3) (4,4). we could count it greedily since if we could choose one blocks of a type, we could choose all blocks of that type. Lastly we could brute force all of the possible quantity for block with type (1,2), (1,3) (1,4), (2,3), (2,4), (3,4) and check whether it possible to create a valid sequence of blocks. then, for each case find the maximum.

At the worst case, the blocks will be divided equally (16-17 blocks for each type) The overall time complexity is O(6 * (n/6)^6) ~= 128600823.04526755, which is fit the time limit

Correct me if i wrong and sorry for my bad england.

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

    Good to see that someone else went through the same hell-ish implementation :P

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

Can Anyone help me with the dp approach that author was tring to convey( about the 4*n states)..It shall be really helpful!

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

In problem D, Can anyone prove how "any combination of + and − is obtainable"?

And what train of thought leads to this conclusion?

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

In problem D I'm getting WA in test case 35.It's very big test case.So,Can anyone give small counter test case?

My submission

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

Can anyone give a proof of why the greedy solution is correct for Problem C. I read the editorial and comments but I'm still confused why it works. Thanks in advance!!

»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Please put this blog into Contest materials.

»
6 years ago, # |
Rev. 3   Vote: I like it +27 Vote: I do not like it

F can also be solved in O(n2) using inclusion-exclusion principle. Implementation: https://codeforces.net/contest/1038/submission/42615092

Explanation:

Let n be the length of target string and m the length of pattern. Let Ai be a set of cyclical strings containing pattern at position i. The answer to the problem is the size of . We can write it using inclusion-exclusion principle as:

Now consider dynamic programming f(k) as contribution (in the sum above) of subsets J of {0, ..., k} containing 0 and k, but forgetting about bits on positions  > k (so f(k) is contribution divided by 2irrelevant bits). Having values of f(k) computed we can get the answer in the following way:

(for each k we need to multiply f(k) by count of "non-wrapping shifts" of positions set (all of them contain 0 and k) and fill in the forgotten bits). How to compute f(k)? Let valid(i) be the set of positions j such that we can place pattern at position i and j simultaneously.

f(k) is non-zero only for since counted sets always contain 0 and k. For such k we consider all possible previous positions of pattern and fill not covered bits. Whole sum is negated since we increase power of -1 in inclusion-exclusion equation. Notice that valid(i) is just cyclical shift of positions in valid(0), it's introduced for notation. valid(0) can be computed naively in O(nm) or O(n + m) using KMP.

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

    Hello, did you make a mistake by accident? Your f(k) is either 0 or negative, so your answer must be a non-positive number.

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

      I forgot to mention that f(0) = 1 (base case), I'll edit the answer. Thanks for noticing.

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

Can someone tell me how this work to solve the problem E?

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

    That solution actually fails on test 117. However, to explain it, the main idea is that every graph has an even number of odd degree vertices.

    If a connected graph has at most 2 odd degree vertices, then there is an eulerian path (a path that visits all edges exactly once). Therefore, every connected component in the graph with at most 2 odd degree vertices has a path that visits all edges and the answer is just the sum of all edges' values. However, when there are 4 odd degree vertices (all of them), one (wrong) approach is to just remove the edge with minimum value. This fails because you may remove a loop, which won't change the parity of the vertices or you may remove a bridge which will make the graph disconnected (that's case 117).

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

In problem C: what's the induction proof to show DP == Greedy ?? Some hints plz

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

Can someone explain this solution to problem F? 42584804

»
6 years ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

UPD. I wrote something stupid and found editorial could do nearly the same thing.

Whatever, for problem C, follow the proving idea in editorial, we can have a shorter solution. my submission (This code is different from the proof in editorial, but I think they are similar if you wrote a version based on proving idea in editorial.)

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How does bool checker() in author's solution on problem E work ?

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

just wondering if there exists a solution for problem E that involves minimum cost flows, thanks and good round btw :)

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

Details for pF please

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

There is an interesting O(2n / 2n2) solution for the Problem F. In the case , enumerate the rest part and count different number of string; In the case , enumerate the first L-1 chars of the string and do a O(n2) dp. The total time complexity is O(2n / 2n2) and I got AC. My code : http://codeforces.net/contest/1038/submission/42792131

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

" The key observation to solving the problem is that any combination of + and − is obtainable, except where all signs are + or all are − " How to prove this ?

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Another solution for the Problem E. Just brute force and greedy.

For every node (1 2 3 4) , we fix its matching priority. For example, node 1, match 2 first, then match 4, and then 3.

Why? If we choose three edges in our answer, for example, 1-2 , 1-3 , 1-2 . This means we can at least go back to node 1 twice. So why not choose the matching nodes in a fixed order ? (1-3, 1-2, 1-2) This means we must select node 3 before select node 2 when we are at node 1. This can be done for every nodes. And brute force matching priority only cost O((3!)^4) , the specific complexity depends on your implementation.

check my code for more details. 42952879

Sorry for my extremely poor English.

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

1038B O(1) solution (it`s not about output data), but for n>2 answer is Yes, and you need to put (n+1)/2 to first set, and all other numbers to second set, and No otherwise

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For D problem The Slimes one for the test case 4

1 1 -1 -1,According to editorial the answer should be 4 but there is no sequence in which the slimes can eat to get the answer 4 or maybe I am missing something,According to me the answer for this test case should be 2

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

I didn't understand the dp solution for problem D.

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

    plus and minus signs has to be placed before each element of the array in such a way that there is atleast one +ve sign and atleast one -ve sign.

    So while assigning the signs, keep track of whether +ve sign has been assigned or not. It is possible to keep track of this information by introducing a state p to the dp, p = 0 means + has not yet been assigned and p = 1 means + has been assigned. Introducing another variable to the dp state can track whether -ve sign has been assigned or not in a similar fashion.

    So there can be 4n states. You're welcome to check my code

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

      Sorry but what is your dp state denoting

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

        dp[i][p][q] stores the answer if we were to consider only the slimes from i,i+1...n. Here, p=0 means that atleast one +ve sign has already been used before some slime 1,2...i-1. p=1 means that no +ve sign has been used over the segment 1,2...i-1. Same can be said for q which is used for -ve sign.

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

          Thanks I understood. I implemented an iterative solution here https://codeforces.net/contest/1038/submission/51602779

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

            Could you please explain your solution...

            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it
              Main idea to save that, have we used +1 * a[i] before i or not and same for -1 * a[i].
              
              According to my solution, 
              dp[i][p][q] => suppose we have 1st i silmes[0 ... i].
              then what will be the answer.
              here p and q are the flags,
                  (For j, 0 <= j <= i)
                  p: +1 * a[j] is included atleast one time or not 
                     (boolean value, 1 means included, same for q)
                  q: -1 * a[j] is included atleast one time or not
              
              Think about this and you can make dp transitions on your own. If you want any help, then i have added my solution below, you can see it !!
              
              My Solution
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution for problem C(Gambling)

https://pastebin.com/Z3FLxML1

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

My solution to problem C(Gambling) My Code

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So,for problem D I have the proving process, and the Solution ignore it,the code ID:66302024 Welcome to Hack~

»
5 years ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

`Most easy approach vll =vector

int main() { FAST; ll n; cin>>n; vll a(n); for(ll i=0;i<n;i++) cin>>a[i]; sort(a.rbegin(),a.rend()); vll vis(n,0); for(ll i=1;i<n-1;i++) { if(a[i]>0) { a[n-1]-=a[i]; vis[i]=1; } }

for(ll i=1;i<n;i++)
{
    if(vis[i]==0)
    a[0]-=a[i];
}
cout<<a[0];
return 0;
}
»
2 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Problem $$$E$$$ was quite nice!

I have a different solution than the editorial. In fact, it's better than the editorial and runs in $$$\mathcal{O}(N)$$$.

As the editorial suggests, this problem effectively reduces to finding the longest (i.e. highest weighted) path which does not repeat edges amongst a graph with only $$$4$$$ nodes and at most $$$100$$$ edges. Instead of trying to construct this path, we can try to construct some subset of edges which can form a path. So in a sense we reverse engineer the problem.

In order for the edges to form a path, we must have at most $$$2$$$ nodes with odd degree. In fact, we can't have an odd number of nodes of odd degree either for obvious reasons, so we basically have either $$$0$$$ or $$$2$$$ nodes with odd degree.

Additionally, and perhaps obviously, the edges, once connected, cannot have two nontrivial connected components. Basically, we cannot have the edge $$$[1, 2]$$$ and $$$[3,4]$$$, since we have no way of traveling between those edges.

With these observations, we have vastly reduced the number of requisite states. In fact, our state only needs to contain information about the mask of edges visited, the parity of the degrees of the nodes, and which prefix of nodes we've visited.

I will leave as exercise to reader how to transition between those states. It's quite straightforward if you understood the preceding part.

Code: 164193566

»
3 months ago, # |
  Vote: I like it +2 Vote: I do not like it

D: "The key observation to solving the problem is that any combination of + and − is obtainable, except where all signs are + or all are − (exception n=1, where the answer is the value of the slime itself)"

Give proof.