vovuh's blog

By vovuh, history, 3 weeks ago, In English

1426A - Floor Number

Idea: fcspartakm

Tutorial
Solution

1426B - Symmetric Matrix

Idea: BledDest

Tutorial
Solution

1426C - Increase and Copy

Idea: vovuh

Tutorial
Solution
Solution 2

1426D - Non-zero Segments

Idea: BledDest

Tutorial
Solution

1426E - Rock, Paper, Scissors

Idea: fcspartakm

Tutorial
Solution

1426F - Number of Subsequences

Idea: fcspartakm

Tutorial
Solution
 
 
 
 
  • Vote: I like it
  • +102
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Wow that was faster than flash!!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Fast Tutorial. WOW!

»
3 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

Wow that was fast.

»
3 weeks ago, # |
  Vote: I like it +79 Vote: I do not like it

I SUCCESSFULLY GAVE MY FIRST CONTEST. I WAS ABLE TO SOLVE ONE QUESTION.THANK YOU FOR THE EDITORIAL AND I HOPE TO PARTICIPATE IN MORE CONTESTS LIKE THIS AND LEARN NEW THINGS .

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Superb round!

»
3 weeks ago, # |
  Vote: I like it +38 Vote: I do not like it

I wonder how many people did prove the correctness of their solution to problem E.

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

    Max flow :)

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

      Can you tell in problem E editorial what is the use of ord vector??

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

        I am guessing that you are asking as to what is vector in cpp.

        It is another data type very similar to arrays with being more dynamic in memory allocation. You can read about them at https://www.geeksforgeeks.org/vector-in-cpp-stl/.

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

          I know what is vector I k saying what is use of that in the code logic I want

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

        Basically testing each order(permutations) of the given operations that needs to done before selecting moves which makes Alice wins.

        So we try to make Alice lose / tie and deplete the rounds as much as possible, before allowing her to win. For this, there are many orders with which we can perform the given moves (before winning rounds), and order vector helps us to generate that permutations.

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

      nishant403, please explain how problem E is related to max flows. I tried a lot to think in this direction but could not figure it out.

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

        consider rock paper scissor as 3 nodes.

        player1's three nodes : a1,a2,a3

        player2's three nodes : b1,b2,b3

        we link a1 with b1,b2, link a2 with b2,b3, link a3 with b3,b1 (for example a1 is rock,b1 is rock ,b2 is paper ,a1->b1 draw,a1->b2 lose)

        root is the source with infinite flow,the you should maximize b1+b2+b3

        the n — b1 — b2 — b3 is minimum win. so maxflow can tell your the answer(make b1 + b2 + b3 flow as much as possible from a1,a2,a3)

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

          Thanks for the insight :)

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

          Is maxflow minflow some algo?? Related to graph??

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

            yes

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

              What are the prerequisite to learn it??

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

                BFS/DFS is enough imo. Then you can look at Ford Fulkerson algo which computes the max flow and min cut.

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

                  In which question max flow and min cut are usefull??

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

    Some guys from the testers (and authors) who do not bother about proofs just wrote mincost maxflow solutions :D

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

      Could you please explain the logic behind E? As in, how do we prove that the optimization problem has that solution?

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

    Proof by AC

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

      What a nice proof! I think max flows should be in the tutorial.XD

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

    See my proof for E E simple proof

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

    Can you provide some resource to understand how maxflow works in such problems or at least topic names?

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

    I wrote the following during the contest, and it got accepted. I see a lot of confusion in the comments about the problem. Can you please check and tell me if this is a correct approach? I am doubtful (after reading so many comments about 'flow') if I got lucky that it passed all test cases.

    #include <bits/stdc++.h>
    using namespace std;
    
    int main() {
        int n;
        cin >> n;
        int a[3];
        int b[3];
        for (int i = 0; i < 3; ++i) cin >> a[i];
        for (int i = 0; i < 3; ++i) cin >> b[i];
        int ans1 = max(a[0] - (b[2] + b[0]), 0) + max(a[1] - (b[1] + b[0]), 0) + max(a[2] - (b[2] + b[1]), 0);
        int ans2 = min(a[0], b[1]) + min(a[1], b[2]) + min(a[2], b[0]);
        cout << ans1 << " " << ans2;
    }
    
»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

i wonder if those russian high school students are also checking out the solutions in coddeforces or not ?

Nice problemset btw .

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

    Nah, the first few stages of this competition are hosted on our local site with some really dumb restrictions I don't want talk about. But, iirc, the third (semifinals) stage is hosted on some local domain of codeforces.

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

To all the 'wow that was fast' comments, that's what she said...!!

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

In problem E, for finding the min wins many people have directly used max(0, a1 — b1 — b3) + max(0, a2 — b1 — b2) + max(0, a3 — b2 — b3) . Can someone prove how this is correct ?

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

    We need to use max(0, a1 — b1 — b3) a1 for b2, It's similar for other two cases. The only problem is that we use some (b1 + b3) for a1 and some (b1 + b2) for a2, will it be enough? We can see that (b1 + b2 + b3) is greater or equal to (a1 + a2), so it's ok.

    I think this greedy solution works correctly. However, I'm sorry that I can't give a formal prove.

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

    Is it actually correct??? maybe just the pretests???

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

    I did $$$max(0, b1 - a1 - a2, b2 - a2 - a3, b3 - a3 - a1)$$$ and it passed. I have some intuition that it would work but not sure at all. Someone prove this please.

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

      We have a draw if Bob use the same thing as Alice and losing if Bob counters some specific item.

      Wins for Alice are situations where Bob have some extra $$$b'_i$$$, which cannot be matched with $$$a_i$$$ or $$$a_{(i+1)\%{3}}$$$. If there are no such extra $$$b'_i$$$ then Bob can create outplaying strategy.

      So, if we have some $$$b_i$$$, such that

      $$$b_i > a_i + a_{(i+1)\%{3}}$$$

      then

      $$$b'_i = b_i - a_i - a_{(i+1)\%3}$$$

      Our goal is to find all these $$$b'_i$$$.

      We can prove that: there is only one such $$$b_i$$$ , if it exists.

      Proof:

      Let we have 2 of them, $$$i \neq j$$$

      $$$b_i > a_i + a_{(i+1)\%{3}}$$$

      $$$b_j > a_j + a_{(j+1)\%{3}}$$$

      then

      $$$b_i + b_j > a_i + a_j + a_{(i+1)\%{3}} + a_{(j+1)\%{3}}$$$

      For every $$$i, j$$$ the same situation will appear:

      $$$b_i + b_j > a_k + a_m + 2a_{3-k-m}$$$

      $$$(k \neq m)$$$

      Also we have this statement

      $$$b_i + b_j + b_{3-i-j} = a_k + a_m + a_{3-k-m} = n$$$

      And so, next statement is going to be true

      $$$a_{3-k-m} + b_{3-i-j} < 0$$$

      Or simply

      $$$a_p + b_q < 0$$$

      For some $$$p$$$ and $$$q$$$, but every $$$a_p$$$ and $$$b_q$$$ are >= 0, so we have a contradiction.

      So, there is only one group of items with extra items in it or there is no such group. Quantity of these extra items is the answer, otherwise the answer is 0.

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

        I think instead of a(i+1)%3 and a(j+1)%3 there should be a(i+2)%3 and a(j+2)%3,correct me if I am wrong. Anyway great explanation!

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

    Obviously, this is a lower bound, but can we reach it? Just to prove it (1) (a1-b1-b3)+(a2-b1-b2)+(a3-b2-b3) = -n (2) B1=a1-b1-b3 >= -n (3) B2=a2-b1-b2 >= -n (4) B3=a3-b2-b3 >= -n If two of them are greater than 0, then the other is less than -n, but this is impossible, all three are either less than or equal to 0, or only one is greater than 0. I.If B1<=0,B2<=0 and B3<=0,this is correct. II.Only one is greater than 0.For example, a1-b1-b3>0, and after removing the game that Alice won, a1=b1+b3, so that b1 and b3 consume a1. At this time, b1=0, b3=0, a1=0, obviously a2 , a3 can't win b2

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Was the pretest for E weak or my solution is correct?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Was this tutorial posted even before the contest finish? xD

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

You came early

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Lol I solved E exactly same as written in editorial , I initially thought that it was an overkill but now I realized it was intended.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone please show me the steps for n = 42?

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

    For the first 5 steps, add 1 to get [6] as the array

    For the next 6 steps, append 6 in the array to get [6 6 6 6 6 6 6]

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

      thanks

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

      How the author arives at the part that not more than O(sqrt(n)) is required if anyone can help me proving this.

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

        You to make the sum at least n. so best way is to go till sqrt(n) and then just append it. Check the sample cases.

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

        Assume that we are fixing x as the value taken by all elements of the array, and y as the number of elements. We need to check for all (x, y) such that x * y >= n.

        For a particular x, y can simply be calculated as y = ceil(n / x). Thus, the number of moves required = (x — 1) + (y — 1) = x + y — 2

        If you take x beyond sqrt(n), you start getting same values for y for continuous range of x, which implies unnecessarily wasting moves by increasing the value of our array element to a higher x, and appending it the same number of times, y.

        Consider the case of n = 12

        x = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

        y = [12, 6, 4, 3, 3, 2, 2, 2, 2, 2, 2, 1]

        As you can see, after x = sqrt(n), y takes the same value for a range of x out of which we only need the distinct one's.

        The distinct values of y (after x = sqrt(n)) are y = [3, 2, 1] and corresponding x = [4, 6, 12] which gives the same (x, y) pairs as traversing x till sqrt(n) did, just the values are swapped!

        P.S. : not a very formal proof, but I hope this helps you understand why checking beyond sqrt(n) is not required.

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

          int ans=INT_MAX; for(int i=1;i*i<=n;i++){ int x=ceil((n)/(float)i); ans=min(ans,i-1+x-1); } cout<<ans<<endl;

          Why is this not correct?

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

            Not sure if float causes an overflow, try changing it to double ?

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

          Thanks a lot for the help. cuber_coder

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

          soln Actually, it reduces to this, can you please expain the correctness of the above o(1) solution?

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

        lets say the number of times we do +1 operation be x,then number of steps will be (x-1)+(n-1)/x,minimimum occurs when x-1=(n-1)/x (using A.M.,G.M. property),hence x=sqrt(n).

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

    Increase the single element from 1 to 7(6 moves) then eppend that 7 to array 5 times (5 moves) ...total 11 moves...arr=7,7,7,7,7,7

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

    Increment upto 6 steps and then append 5 times. Incrementing 6 times will give 7 and then appending 5 times means multiplying 7 six times which is 42. Hope this helps!

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

    a[1]-> a[2]-> a[3]-> a[4]-> a[5]-> a[6]-> a[7]-> a[7,7]-> a[7,7,7]-> a[7,7,7,7]-> a[7,7,7,7,7]-> a[7,7,7,7,7,7]

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For C: Answer = sqrt(4*N — 1) — 1

Is this correct ?

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

    let the increment be X, then the answer must be Ans= ceil((n-x)/x) + x-1 So using the arithmetic mean concept answer is greatest when both terms are equal, so ceil((n-x)/x) = x-1 or you can say that x must be in between sqrt(n)-10 to sqrt(n)+10

    My submission : 94074745

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

      Hi ,

      can you please explain , the reasoning behind considering both terms equal .afaik , Ans >= 2 * (ceil(n-x)/x)*(x-1) acc to AM>=GM . what am i missing ?

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

        We know that AM >= GM But we want answer to be minimum possible, That mean AM=GM (least possible) That mean (x+y)/2= sqrt(xy) this is only possible when x=y. => (ceil(n-x)/x) = (x-1) => ((n-x)+(x-1))/x = (x-1) =>. (n-1)/x = x-1 Or we can say that x = sqrt(n) ± 10.. If you are still confused ask me I would be happy to solve them ans pls like this comment :)

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

          I am very new to coding, Can you please explain me in problem C, we were trying to make an array but you are using arithmetic mean and geometric mean. How did you reach to that conclusion? I understood solution1 in editorial but cannot reach to AM and GM.

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

            In these type of Questions first try to find the function of answer which is dependent on x. Then try to figure out how you would maximize it. Solve as many problems as you can.. this will help alot.. :)

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

              Could you please tell me where can I find such problems ?

              I want to practise this types of problems more

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

                I dont know any specific topic, I would suggest keep reading editorial and comments for such tricks :)

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

                  Finally I understood AM and GM. Thanks for your help

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain the approach in F?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How is this possible Editorial was out before the contest xD! The questions were easy but conceptual...Thanks vovuh!

»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

The editorial came in O(1) time.

»
3 weeks ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

I think the problem E should have been B/C question type because, for minimum moves, we had to just generate all permutations in a brute force. Not much logic involved over there!

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

    this is actually how i do it XD

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

      E is not even a problem to 1800, just dont get why testers put a such easy problem to that position

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

I thought it would be too stupid to generate all combinations on E and I gave up...

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

Problem C can be done without even using a loop, basic math.

long long i = ceil(sqrt(n));
long long ans = i + (n+i-1)/i - 2;
//Print ans
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can u explain?

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

      Try to plot the graph of the formula given in the editorial: x + ceil(x/n) - 2 If you remove the ceiling from the expression, the resulting expression x + x/n - 2 is a lower bound for the initial expression (because always ceil(x) >= x). So, if we find the smallest integer value of that expression for x >= 0, we'll be done. Using some calculus, you can find that this expression is minimized for x = sqrt(n), so ceiling it and plugging it into the original equation will give us the smallest integer value of the expression. (I hope I could explain it correctly...)

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

    I was thinking the same! Thanks for your solution :)

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

    how can you be sure that i = ceil(sqrt(n)) , UPD : got it

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain for problem C, how adding 1 till we reach a number x and then copying it is the most optimal way?

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

    As suggested in the editorial, we can prove this by swapping the order of the two operations and checking which results in a better solution.

    Let's say you have $$$x$$$ in the beginning, if you do increment and add, you'll have $$$(x+1)+(x+1) = 2x+2$$$. Instead, if you decide to add and then increment, you'll have $$$x + x + 1 = 2x+1$$$.

    Thus we can see that if we ever do increment after adding to set, we'll always be worse off. That is, we should always increment the value first and then add it.

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

      I am using ternary search to find the minimum of the function given in the tutorial but I am getting WA on test case 2. Could you tell me what is the problem? Submission: https://codeforces.com/contest/1426/submission/94132053

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

        The function $$$F(x) = x + n/(x+1)$$$ is ternary on real numbers when $$$x, n >= 0$$$.

        But for integers $$$F(x) = x + ceil(n/(x+1))$$$ doesn't seem to be ternary.

        Both functions seem to have their minimum point pretty close tho (I don't have a proof for this. I hope somebody could provide one or even some insight or intuition).

        You can plug in arbitrary values of n and draw both functions here to visualize it: https://www.desmos.com/calculator.

        You can avoid this problem in this problem by searching using doubles and try the integers around the minimum point (which may or may not be fractional). I did something similar in this submission: https://codeforces.com/contest/1426/submission/94170281

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

          What a nice trick!

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

            Please note that this is not a general trick. It relies on both functions having their minimas pretty close.

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

              I know, but I guess that the ceil function is what make F(x)=x+ceil(n/(x+1)) not unimodal, so removing the round part give us a better candidate function for ternary search...

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

              Thanks for the clarification btw

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

                You're welcome. Thanks for the insights.

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

          Thanks Bekh. I understood the approach :)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me figure out why didn't my solution to C work even though it iterates from 1 to 2*sqrt(n) ? Here's my submission and thank you :)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain me in C why does x-1 gets added to n-x in sol even though steps for obtaining x have been added initially?

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

    I was having the same problem instead of explaining I will say take n=5 then u will understand it

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Simple Solution for F using combinatorics. 94117068

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

    Kindly explain your solution.

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

      Fix the $$$b$$$ in a position and count the number of possible $$$a$$$ in the prefix and possible $$$c$$$ in the suffix.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

E felt like easier than A lol

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem A: Can someone explain how did the formula floor(n-3 / x ) + 2 come from? Thanks in advance

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

    We have, $$$2 + x + x + x + ... + x \geq N \Rightarrow 2 + (Step-1) \times x \geq N$$$

    This results in $$$Step \geq \frac{N-2}{x} + 1 \Rightarrow Step = \lceil\frac{N+x-2}{x}\rceil$$$

    Now, either you can just use this in your program, or else there is a neat way to do this and that is $$$\lceil\frac{a}{b}\rceil = \lfloor\frac{a+b-1}{b}\rfloor$$$. If you use this result, then the above expression converts to $$$Step = \lfloor\frac{N+2x-3}{x}\rfloor = \lfloor\frac{N-3}{x}\rfloor + 2$$$.

    You can try to verify that the ceil to floor conversion works for yourself.

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

      I understand the ceil to floor conversion, but would you please elaborate the inequality to equality conversion of Step ≥ N−2x+1 ⇒ Step=⌈ (N+x−2)/ x⌉ ?

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

        Basically, we want the smallest integer which is either equal to or greater than this fraction, which is the definition of the ceiling function.

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

          Oh, I understood you just transformed the 1 into x / x so you can use the ceiling to flooring conversion. Thank you

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

            Actually, you don't even need to do that, you can leave the 1 as is an only change the fraction. It'll come out to be the same.

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

              what is step-1

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

                Step is the level you are at. So $$$2$$$ for the first level and for the remaining $$$Step-1$$$ levels you have $$$x$$$ rooms, which gives you, $$$2 + (Step-1)\times x$$$ total rooms.

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

      can you tell me the corresponding mathematical topic of this approach.like how to find the formula

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

        I am not sure how to answer this. I'm tempted to say this comes under linear equations!? After getting the equation, I don't think you need to get the exact formula as stated in the editorial, just solve it as you would on paper.

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

      Epic explanation...

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why in Problem A, if we remove the first floor, then we subtract 3. And why, after division, we add 2

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the use of ((n-x)+x-1) instead of why not we simply write (n-1) in problem C. Can someone please help me?

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

    That is for the sake of understanding that we need ceiling of {(n-x)/x} , and a popular way to implement it is to write ((n-x) + (x-1) / x). And for the same reason, if you want ceiling of (n/5) you would write (n+4)/5 !

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

Another solution for finding minimum wins for ALICE in E . a1 b1 c1 ---> set with alice

a2 b2 c2 ---> set with bob.

to minimize wins a1 must be played against a2 and c2 thus a1 depends on a2 , c2 b1 depends on b2 a2 c1 depends on c2 b2.

also I claim that a2 handles a1 and b1 . b2 handles b1 , c1 , c2 handles c1 and a1 that is cyclic order. lets supppose any one of the following situation is true.

a2>=(a1+b1) --->(1)

b2>=(b1+c1) ---->(2)

c2>=(c1+a1) ---->(3)

in any of this case we can make 2 values of a1,b1,c1=0; example in case of situation 1 a1 b1 can become 0. c1 can be minimised by remaining b2 c2. by subtracting minimum accordingly. thus remaining value of c1 is answer. similarly we can check for other cases.

In case any of these situation is not true

then simply the minimum value is 0. proved below

Proof.

Since a2<(a1+b1); b2<(c1+b1)==>(4); c2<(c1+a1) -->(5) since every 3 inequality holds so at first we can reduce any one of a1 and b1 by amount a2 and make a2 completely 0. then from inequality 4 we can make b1 0 and b2 0 or still if we have b2 left we can reduce c1 . now reduces some a1+c1==c2 as we reduced a1 +b1+c1 by amount a2+b2 and since a1+b1+c1==n thus reduced value is n-(a2+b2)==c1. thus remaining sum from first set equals last remaining value. Hence we can make alice lose every match in this scenario.

Submission!

94112692

»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Can someone explain a solution using flows in problem E? I know only the basics on this topic and I'm really curious how it can be applied in this problem.

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

    You can link the source to Alice's options (1-rock, 2-scissors, 3-paper) with their respectives capacities (a1, a2, a3) and the sink to Bob's ones (4-rock, 5-scissors, 6-paper) with capacities (b1, b2, b3). Then link the options that make Alice not win (draw or lose) mentioned in the editorial with infinite capacity and just calculate the max flow in that network. The edges will be:

    (source, 1)
    (source, 2)
    (source, 3)
    (1, 4)
    (1, 6)
    (2, 4)
    (2, 5)
    (3, 5)
    (3, 6)
    (4, sink)
    (5, sink)
    (6, sink)
    

    Note that (4, 5, 6) are Bob's options (rock, scissors, paper) but with other numbers to not repeat nodes. So the minimun number of rounds Alice can win will be (n — max flow) Code: link

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we do the third problem using DP?

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

    no because of time limits. otherwise we can make a recursive solution easily.

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

      How? can you tell the recurrence?

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

        ok so we have to make n from least steps. and our recurrence depends on two things. first -> value we want , second- > max value we have. n = value we want, maxi = max value we have. solve(n, maxi) = 1 + min((solve(n-1, maxi+ 1), solve(n-maxi, maxi)); here base case is if n <= then return 0;

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

          great!! I couldn't come up with it but got the thought process.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1426/submission/94126035

Can anyone tell me the error in this sol for D?

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

    Line 39 — variable cur overflows the range of int

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

      i also tried with long and long long but still same error

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

    You should be using set instead of set because even though you change you cur variable to long long, set value will overflow

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

Please look at these two submissions to problem C.

Sub1 : https://codeforces.com/contest/1426/submission/94126382

Sub2 : https://codeforces.com/contest/1426/submission/94126537

Sub1 uses ceil function and Sub2 uses the technique in author's solution 1.

Sub2 is accepted while Sub2 gaves TLE. Can you please explain why ceil function lead to TLE? ;_;

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

    Maybe some problem with double or something. People usually avoid using ceil for these reasons.

    P.S. I don't know if you know this or not, but C++ has a build-in swap function.

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

Its just me or someone also felt that nowadays problem A,B,C in codeforces Div-2 and Div-3 rounds are of almost same levels?

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

another nice solution for F with math.

we can make substring abc by taking a charecter b and one a in left(left of b) and one c in right side(right of b)

hence for a string s (which doesn't contain '?') we can calculate the number of abc subsequence as the following method :

$$$a_i = $$$number of a before the positon i

$$$c_i = $$$number of c after the positon i

$$$ans = \sum_{\text{s[i]=='b'}}{a_i\times c_i}$$$

If we allow '?' in our string then what will happen? :

$$$p_i = $$$number of ? before the positon i

$$$q_i = $$$number of ? after the positon i

Then for $$$i^{th}$$$ position if it is 'b' then in left there might be $$$a_i + k$$$ numbers of a , where $$$0\le k \le p_i$$$

how many string are there that have exactly $$$a_i + k$$$ numbers of a before the $$$i^{th}$$$ position ?

the answer is $$$\binom{p_i}{k}\times 2^{p_i-k}$$$

(we can do , pretty much the same things for right side)

summing up the idea we got our total answer:

$$$\text{answer = }\sum_{\text{s[i]=='b' or s[i]=='?'}}{(\sum_{k=0}^{p_i}{(a_i+k)\times\binom{p_i}{k}\times 2^{p_i-k}}) \times (\sum_{k=0}^{q_i}{(c_i+k)\times\binom{q_i}{k}\times 2^{q_i-k}})}$$$

we can write $$$(\sum_{k=0}^{p_i}{(a_i+k)\times\binom{p_i}{k}\times 2^{p_i-k}})$$$ this part as this $$$(3^{p_i-1}(3a_i+p_i))$$$

this things reduce our solution in :

$$$\text{answer = }\sum_{\text{s[i]=='b' or s[i]=='?'}}{(3^{p_i-1}(3a_i+p_i)) \times (3^{q_i-1}(3c_i+q_i))}$$$

we can easily calculate this in O(n)

you can see my solution here

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

    steinum we can write (∑pik=0(ai+k)×(pik)×2pi−k) this part as this (3pi−1(3ai+1)). Is there any formula for this line you wrote??

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 3   Vote: I like it +12 Vote: I do not like it

      well , I dont know if there is any well known formula for it or not.

      $$$\sum{(a_i+k)\times \binom{p_i}{k} \times 2^{p_i-k}}$$$

      $$$\Longrightarrow a \sum{\binom{p_i}{k} \times 2^{p_i-k}} + \sum{k \times \binom{p_i}{k} \times 2^{p_i-k}}$$$

      $$$\Longrightarrow 3^{p_i}a+3^{p_i-1}p_i$$$

      for the first part we can define a problem : you have to choose 'k' ball from p ball and color them white, for the rest of the ball you can color them with eigther black or blue

      this problem can relate $$$\sum{\binom{p_i}{k} \times 2^{p_i-k}}=3^{p_i}$$$

      and, for the second part we can define another problem : you have to choose 'k' ball from p ball and color them white, for the rest of the ball you can color them with eigther black or blue. And from the white balls you can pick one ball

      this problem can relate $$$\sum{k \times \binom{p_i}{k} \times 2^{p_i-k}}=3^{p_i-1}p_i$$$

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

      Use binomial expansion like-:

      First Part-

      (1+x)^N = (Nc0) + (Nc1)x + (Nc2)x^2 + (Nc3)x^3 ................(NcN)x^N. ---eq(1)

      Put x = 2 both side and use relation n choose r is equal to n choose (n-r) Left side = 3^N ,Right side = Req sum

      Second Part — Differentiate eq1 both side wrt to x : L.H.S- N*[(1+x)^(N-1)]

      R.H.S becomes the second part after some modifications .

      Put x = 2 like first part L.H.S= N*(3^(N-1))

      Hope it helps.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can C be solved using Binary search ? it worked on sample test cases but i guess i was not able to converge the search space?

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

    You can solve it using the ternary search. The answer will first decrease and then increase. But if you have the intuition that the answer won't be too big, you can just iterate until your new answer is better than the previous one.

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

      https://codeforces.com/contest/1426/submission/94078419 Can't it be done only using binary search?

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

      Ternary search may not work. The answer is not strictly increasing or decreasing.

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

        Yes, you're right, Thanks!

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

          I have done it using ternary search. The only thing you need to take care is that when the (value at mid) == (value at (mid + 1)) then recursively search for the best answer in both (low, mid -1) and (mid + 1, high) ranges.

          My submission : 94125048

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

        Actually ternary search can work here..you can have a look at the graph :

        Screenshot-49

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

          Screenshot-from-2020-09-29-11-57-00

          Note x can only take integer values.

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

            Oh yes I missed putting floor...but still the graph does decrease then increase/

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

              But not "strictly", for ternary search the graph must be strictly decreasing then strictly increasing.

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

                But then how to account for those sparsely distributed values on the left side of minima ?

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

    yeah,I solved C by using binary search:https://codeforces.com/contest/1426/submission/94096870

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In D, Why do we need to clear the set? Can't we keep the prefixes from the left side and move on?

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

    Then you will count extra. Ex- 1 -2 1 -2 3. In this case you will add a positive no in bw -2 and 1. but you will add extra since you will consider tha array -2 1 -2 3 also as sum=0.. But we have already inserted a no so sum is not 0. Hence we don't want to save arr[0] and arr[1] contribution in set.

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

    As far as I understand, when we are inserting the large element to change the sub segement which just now became 0, we can consider the list, 1 2 -2 1 -1 Here, we have prefixes, 1 (1st element) 1 + 2 = 3 (1st 2 elements) 1 + 2 — 2 = 1 (1st 3 elements) Here as we are getting same prefix sum repeatedly we can say the subsegment between the sum 1 and 1 is 0. so, 2 -2 is 0. Now according to the statement we can insert a large element to change this 0 sub segment. We insert into the middle of two elements. We insert here, 1 2 X -2 1 -1 (X = large element) So, we are sure that 1 2 X, if we take this prefix we will never get a 0 sum as X is huge. But later down the road we may end up getting 0 subsegments. So we ignore the whole prefix with the large element X and consider the latter portion, -2 1 -1.

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

    No, because the prefixes "restart" after you insert a big number.

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

    Turns out we don't need to clear the previous set if we keep changing the big number. Link to my Solution

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

Please explain what this line means in E :

"It can be shown that if we started using some combination we are better to end it before using the other one. " .

Does it means that we need to minimise both of them by minimum of them ?

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

    It means suppose we are currently Choosing paper for Alice and Scissor for Bob , then we must continue until its not possible to use this combination (because either paper finished or scissor finished or both).

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

      Fine. But then editorial also says that order of these steps does not matter.

      So i perform for first test case as follows:

      Take a1 and b1. Nothing changes.

      Take a2 and b2. Both reduces to 0.

      Take a3 and b3. Nothing changes.

      Only value remains are b1 and a3.

      So minimum value should be 1 using these steps . Where i went wrong ?

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

        You should take first b3 with a2, then b2 with a1.

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

    So these are the 6 types of combinations in which Alice loses. So it can be shown that if you are going to use some combination more then once, for example — a2 and b1, it is never efficient to use a2 — b1, then use another combination and again a2 — b1. So now you have six different segments of combinations which you got to reorder in the best way. You try all 6! variations and choose the best one.

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

      I get it that we can try all orders of combinations.

      But why editorial says "It is also possible that the order of these combinations does not matter, but we didn't prove that fact " ?

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

        Aah, it means that there might be a constant solution where you don't have to try all variations but they haven't proved it.

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

Why are we inserting 0 into the set in problem D? I can see in submissions that people inserted 0 initially and then every time the set was cleared 0 was inserted again.

UPD: I guess when the whole prefix becomes 0 we need to reset which is why we are using the initial 0 in set.

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

    Say the prefix sum came out to be 0. You can either check it yourself or just let the set operation check it for you.

    You can Explicitly check if it was 0, or you can let "the Set" do it for you

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

For problem E how we will get minimum win as 119 for following example?

319
10 53 256
182 103 34

129 is lowest I can think of.

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

    First use all your Papers against their Paper and Scissors. In this way, you'll have 119 Papers remaining.

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

      Got it. Thank you!

      I want to know how this max flow works in such problems. I think 94072786 uses max flow.

      If you can provide me with some resource that would be great. Thank you again.

»
3 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

This contest was one of the greatest programming contest..I have ever seen in my life..(problem statements pleased me!)

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

    yeah..that was super..the problem statements are so cool..and I like easy small codes..and wanted more contests from..BledDest,fcspartakm and vovuh..thank you guys for this contest..

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

C was a case work ^^'

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think max flow is easier than other approaches for E xD. Maybe it should be written in the tutorial, at least it's interesting.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem F is a thing of beauty.

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it
So,I think I have a more clear solution for D.For every [l,r] which is 0 ,we want to insert as few as possible numbers to break them,we have an idea that find all the [l,r] which equals 0 and select as few as possible points to "touch" all the intervals(which I means that makes every interval has at least one point) and we find it is O(n^2) but the greedy model is classical,we sort the intervals and select as right  point as possible and we find that for [l1,r] [l2,r](l2>l1) if we can touch [l2,r] we can touch [l1,r] so,we just store the [l2,r]=0 which the l2 is the biggest.

Sorry for my poor English,and it may sound silly...But I hope it will be helpful for you bros

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody tell why the best solution will be near sqrt(n) in Problem C

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

    We should get n (or nearest) by multiplying two numbers and the sum of two numbers should be minimum (greedy) hence, the rule!

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

      Which numbers do we multiply? We can only do +1 or copy (sum). Where is the multiplication?

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

        You increment some times ok, this takes you to $$$X$$$. This will take approx $$$X$$$ steps. Now you'll add it $$$Y$$$ times to make the sum $$$N$$$. This will take $$$Y$$$ steps. You want $$$X+Y$$$ to be minimum, given $$$XY=N$$$. Which gives you the desired condition of approx $$$\sqrt{N}$$$

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

          Finally got it, thanks. Also used the example with 42 above. Summarizing:

          We +1 until we reach x

          Then we copy: add x times x (multiply x*x)

          e.g. for 42:

          First five moves: [1] -> [2] -> [3] -> [4] -> [5] -> [6]

          Next six moves: -> [6,6] -> [6,6,6] -> [6,6,6,6] -> [6,6,6,6,6] -> [6,6,6,6,6,6] -> [6,6,6,6,6,6,6]

          Total: eleven moves(noted as ->)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For C, How did you come up with the intuition that we only need to go till sqrt(n) instead of n/2?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How come this submission was accepted? He didnot go through all the permutations.

void solve()
{
    int n,a1,a2,a3,b1,b2,b3;
    cin>>n>>a1>>a2>>a3>>b1>>b2>>b3;
    int ans2=min(a1,b2)+min(a2,b3)+min(a3,b1);
    int d1=min(a1,b1),d2=min(a2,b2),d3=min(a3,b3);
    a1 -= d1;
    a2 -= d2;
    a3 -= d3;
    n -= (d1+d2+d3);
    int ans1=min(b1,a2)+min(b2,a3)+min(b3,a1);
    cout<<n-ans1<<" "<<ans2<<endl;
    
}
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me on what test case my solution for B fails? It is hacked. Here is my submission.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I misunderstood problem C and wrote a completely different solution but it still seems to pass the tests. Can someone hack my solution or tell me why it is correct. This 94146956 is my submission. Also I wonder if anyone else wrote a similar solution?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It was my first contest on codeforces . I don't know about the rating system. Did the rating got updated for u guys? I solved 1 question successfully but it is showing 0 ratings for me,

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain problem c

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

i think proplem E must D and D must be E any one see that E is so easy

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

for Problem C why the array could not consists of copies of different numbers?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

for problem 1 instead of the formula mentioned above i used (ceil((n-2)/x)+1), this too passed all the test cases, could someone explain me whether this is equal to the formula mentioned above or is there any test case where this fails

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

    It's same, you can use $$$\lceil \frac{a}{b}\rceil = \lfloor\frac{a+b-1}{b}\rfloor$$$

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is p(r) and p(l-1) has to be same in problem D??? Can someone please explain it to me

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

    If p(r) = p(l-1) we can say there ia no change is prefix sum or sum of the interval (l,r) is 0.

    Arr[l] + arr[l+1]....arr[r] = 0

    P(r) — p(l-1) = 0

    So, P(r) = p(l-1)

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

It is also possible that the order of these combinations does not matter, but we didn't prove that fact.

What does this statement mean? I tried running the brute against this:

47

14 21 12

30 9 8

But for more than 500 different orders the minimum calculated was different from the actual one.

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

    He might be taking of some special cases

    Like, a= {3,3,3} and b= {5,5,5}

    Here the order of permutation doesn't really matter.

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

      Okay, I thought that the order doesn't matter in general because mentioning that it won't matter for some special cases is unnecessary.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can any one help me with problem F .... how to handel the case of question mark in DP solution.... thanks for the help

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem C why this code is giving TLE can anyone tell plz https://codeforces.com/contest/1426/submission/94158754 Thanks in advance

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone explain me 1426D — Non-zero Segments problem's logic please. I am not able to understand the provided solution.

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

    Let us define $$$presum_{k}$$$ as the prefix sum, $$$a_k$$$ as the array.

    $$$ presum_{k} = \sum_{i=1}^{k} a_i $$$

    Let's define $$$i,j$$$ as indexs($$$i < j$$$):

    • if $$$presum_{i} == presum_{j}$$$, we can know that
    $$$ presum_{j} - presum_{i} == 0 \rightarrow sum\{a_{i+1}, \cdots, a_{j}\} == 0 $$$

    In order to avoid this situation, we insert a $$$+\infty$$$ behind the $$$a_j$$$. Like this: $$$a_{i+1}, \cdots, a_{j-1}, \stackrel{\infty}{\downarrow},a_{j}$$$.Then reconsider from $$$a_j$$$

    Part of the core code:

    void solve(){
        int n = read();
        unordered_map<LL, int> mp; // 0 --> not in, 1 --> in
        mp.clear();
        LL sum(0), ans(0);
        for (int i = 0; i < n; ++ i){
            int f = read();
            sum += f;
            if (sum == 0 || mp.count(sum)) { 
                ++ ans; 
                mp.clear();  // Simulate inserting an infinite number
                sum = f; 
                mp[sum] = 1;
            }
            else mp[sum] = 1;
        }
        cout << ans << '\n';
    }
    
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks

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

      hi first of all nice explanation thank you for that.

      but i have certain doubts

      why we have clear the prefix sum left of the new element added, why we dont consider it anymore and can you tell how the complexity of the program in the editorial is nlogn?

      thanks

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

        hi, — Under normal circumstances, we need to add an infinite number to the prefix sum before the insertion position

        Obviously, after inserting an infinite number, we can guarantee that this situation does not exist:

        $$$ presum_i == presum_j $$$

        So we don’t need to consider the prefix sum before the insertion position.If we do not clear it, it will affect subsequent operations.Like this:

        $$$ \overset{+\infty}{\overbrace{1}}, \overset{+\infty}{\overbrace{5}}, insert, 1, 5 $$$

        If you do not clean up, it will appear $$$mp.count(5)$$$. Actually that is $$$5 + \infty$$$. So cleaning is to simulate the process of adding infinity.

        i do not konw the extacly complexity of the program in the editorial, because i konw little about py, if the operation in and add are $$$\mathcal{O}(1)$$$, the algorithm is $$$\mathcal{O}(n)$$$, if the operations are $$$\mathcal{O}(\log n)$$$, the algorithm is $$$\mathcal{O}(n \log n)$$$

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

      I have a little bit confusion about test case 3 (-1 1 -1 1 -1 1 1 -1 -1) .

      Here prefix sum is-1 0 -1 0 -1 0 1 0 -1 . I have to insert a number before every 0 according to describe above. Then there is only 4 options. So ,How the result is 6?. Please clarify my fault.

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

        yeah i had this same doubt

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

        OK, I have also had this problem, which is also the key to solving this problem. You insert a number before the first 0 like this

        $$$ -1, \stackrel{\infty}{\downarrow}, 1, -1, \cdots $$$

        then, the prefix sum will be [Reconsider the next element from infinity]:

        $$$ 1, 0, 1, \cdots $$$

        To make it clearer:

        $$$ \begin{array}{ccccccc} &befor\; insert& -1& 0& -1& 0& \cdots \\ &after\; insert& NULL& \underset{new\,\,start}{\underbrace{1}}& 0& 1& \cdots \\ \end{array} $$$

        You can find that after inserting a number, a new 0 may be generated while eliminating a 0.

        Your idea is offline, but this is actually an online problem. Need dynamic processing. in my opinion

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution to F, it maintain 6 cnt for a, ?, ab, a?, ?b, ?? and get the result.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I couldn't get the logic of copy and increase problem can anyone help me .

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please tell me how to solve C via Binary Search??

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

    If you plot the graph of f(x) = (n/x) + x — 2 you will see it looks like graph of quadratic function with (a>0). So we can apply ternary search here to find optimal x at which f(x) is minimized. However no need for that, because we can differentiate the above function to see that x = sqrt(n) ! We can confirm that it is minima by double D or by just looking at graph. Since the actual answer is ceil(n/x) + x — 2 we vary x from sqrt(n)-5 to sqrt(n)+5 to get the minimum as mentioned in tutorial.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi guys, In problem C: why do we need to add the bolded term? ans = min(ans, x — 1 + ((n — x) + x — 1) / x); and in the tutorial he didn't mentioned this term thanks.

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

    It's actually a trick for ceiling
    Instead of doing ceil(a / b) you just do (a + b — 1) / b

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve C if instead of having sum greater than or equal to n it were to be exactly equal to n?

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

    The cost for reaching sum exactly n, and for reaching sum at least n is the same. Suppose you are duplicating number i. If n % i = 0 then you reach sum exactly n. Otherwise, while increasing 1 to i with operation one, when you reach n % i duplicate it, this way you save the need to duplicate i one more time, because the n % i will reach the sum to n. As you can see, the cost is the same. Funny thing, same code gets AC in both problems.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

in c why the solution doesnt go beyon root n?

thanks

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

    If you increment your number to $$$sqrt(n)$$$, you won't need more than $$$sqrt(n)$$$ copies of it since $$$sqrt(n) * sqrt(n) == n$$$

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

As noted, Problem F can have different solutions with varying implementation complexity. Here is a simpler one, imo.

At each index, find count of subsequences 'a', 'ab' and 'abc' ( conveniently named as such in the code below ) appearing in all combinations so far. One thing to note is, when appending 'a', the new 'a' appears in how many? count of number of strings so far (call it 'm' below). Leaving out mods in the (pseudo) code for easier reading.

a = 0, ab = 0, abc = 0, m = 1;
for (char c : s) 
  if (c == 'a') 
     a = a + m;
  else if (c == 'b') 
     ab = ab + a;
  else if (c == 'c')
     abc = abc + ab;
  else { // '?'
     abc = 3 * abc + ab;
     ab = 3 * ab + a;
     a = 3 * a + m;
     m = 3 * m
  }
return abc;

My submission: 94171796

ps: I see this is very similar to DP, except no explicit dp table. It's similar to how you can calculate fibonacci(n) using a=0, b=1, c=1; for(3..n) b = c = a + (a = b); print c; Bad idea to do it in one statement, but meh! you get the idea :)

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

    i also thought about same solution. but i couldn't think about m. why m= m*3 and a += 2*a + m what i was doing was a = 3*a + 1. can you explain why you used m and how it work a little more.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      • m is total number of different strings so far. For each '?' we have 3 choices ( a, b, c ) so x 3 for each '?'.
      • I updated code to a = 3 * a + m; which is the same. When you see '?', you replace it with one of 'a' or 'b' or 'c'. In each of these cases, you carry over previous counts of a, ab, abc (those not including this index). Additionally, if you include this index, each of them increase by the same factor as in their corresponding cases above.
      • I would suggest you to work out a small case on paper. Some times trying out a case gives you ideas. Eg: Try this "a??b?", Result should be 25.
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Amazing solution

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

my rating still hasnt updated...

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

Can someone please explain to me the C part in a less mathematical way or just in a more understandable method for beginners, please. I just can't relate between the logic that's mentioned above and the question. Thanks.

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

    Let draw some pattern by incrementing and by appending 1.[1],[1,1],[1,1,1],[1,1,1,1].... 2.[1],[2],[2,2],[2,2,2],[2,2,2,2]...... 3.[1],[2],[3],[3,3],[3,3,3],[3,3,3,3].... 4.[1],[2],[3],[4],[4,4],[4,4,4],[4,4,4,4]..... 5.[1],[2],[3],[4],[5],[5,5],[5,5,5],[5,5,5,5].... You can observe that for a given N if you come through a path which including its sqrt then it is taking minimum steps to reach N let say you want to reach N=4 then if you choose 2nd path it will cost minimum steps let say you want to reach N=21 then if you can choose 4th or 5th path it will cost minimum steps so by this, you can conclude that to reach N, first reach to its sqrt then after that start appending it and hence it will need minimum steps. Hope you got it.

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

      Oh, now I get it, thanks a lot. Just one last, while solving this question you are supposed to observe this pattern?

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

        In this question, if you try for some values of N by rough work you will notice this. Here you can also see Y(N which we need to reach) increasing fast wrt to X(minimum steps which we want) like a parabola.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

binary search solution for problem C ???

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Please help me with what's wrong here. https://codeforces.com/contest/1426/submission/94178071

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

when will the rating get updated?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1426/submission/94110938 Can anyone help me why this code is giving wrong answer on test case 10? Problem:D

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In question 3 how do we know that we get our solution by iterating upto sqrt(n). Is there a mathematical statement? I don't know why but ,I was trying binary search and was getting close answers.

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

    If you plot the graph of f(x) = (n/x) + x — 2 you will see it looks like graph of quadratic function with (a>0).

    It is actually hyperbolic. So we can apply ternary search here to find optimal x at which f(x) is minimized.

    However no need for that, because we can differentiate the above function to get that x = sqrt(n).

    We can confirm that it is minima by double differentiation or by just looking at graph.

    Since the actual answer is ceil(n/x) + x — 2 we vary x from sqrt(n)-eps to sqrt(n)+eps to get the minimum as mentioned in tutorial.

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

Can anyone help why this solution not working. I'm not going till sqrt(n) but going to 63944 which should also pass the testcase. I got tle and I'm confused that is time given for every testcase is different. https://codeforces.com/contest/1426/submission/94093082

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Have a look at my code (accepted) for 1426C - Increase and Copy

int n ;
cin >> n ;

int a = sqrt(n);
int b = n / a ;
if(n % a) b++;

cout << a + b — 2 << endl ;

I hope , you will find it more easy (no loops or iterations) than many other approaches :)

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

    Please explain your logic !

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

      You have to find two integers a and b such that a*b >= n and a+b is minimum possible.
      These values will be sqrt(n) and ceil(n / sqrt(n)).

      Approach :
      You have to increment the 1 (present in array) to a . This will take (a-1) moves.
      Then append this number a to the array (b-1) times.
      Ultimately, element a is present b times in array which gives a*b >= n

      Total moves will be : (a-1) increments + (b-1) appends
      So answer will be (a + b — 2).

      Hope it helps :)

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

The ratings are not updated yet. Is there any problem with the contest or something else? When can we expect rating change? UPD: the ratings are changed now.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the contest be rated?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The name of problem C gives a hint to solve it.

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

For problem E, the answer for the minimum can directly be given as $$$max({0, b_1 - a_2 - a_3, b_2 - a_3 - a_1, b_3 - a_1 - a_2})$$$.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I understand that number of moves will be x-1+((n-x)/x) but why ((n-x)+x-1)/x ?? I cant understand the "X-1" at the second part

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

    say you wish to get the sum 9 using 4s. you have to use 3 4s (4+4+4=12) but a simple n/x gives answer 2 in this case. suppose there is a case where we need to get sum 9*k using k's. you need 9 k's. for all n where 9*k < n <= 10*k, the answer has to be 10. (n+k-1)/k ensures this.

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

      I didn't get it. sorry

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

        take x=4. now, - n/x=0 for n=0,1,2,3. - n/x=1 for n=4,5,6,7. and so on. But we need this: - f(n)=0 for n=0. - f(n)=1 for n=1,2,3,4. - f(n)=2 for n=5,6,7,8. we can get this if f(n)=(n+x-1)/x. (we are shifting those x-1 numbers into the next group by adding x-1 to n.)

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

    To avoid floating point operations we write it as Ceil(A/B) = Floor(A + B - 1 / B); For example Ceil(7/3) = Floor(7 + 2 / 3) = 3 Or Ceil(7/2) = Floor(7 + 1/ 2) = 4 We convert Ceil to floor because in most programming languages floor(A / B) = A / B. Note : This only works for positive values. For negative values we have to make some changes.

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

can someone explain F?. It is hard to understand from the tutorial.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In E, how to proof the maximum number? The editorial doesn't have an detail.
Example:
22
5 8 9
11 7 4
The maximum number is min(5,7) + min(8,4) + min(9,11) = 18
And the thing left is
0 4 0
2 2 0
So The answer is 18-2 = 16 ?
Alice has 4 scissors and Bob has 2 scissors and 2 rocks, so Alice has to lose 2 more rounds?
But the correct answer is 18, so I'm confused. Can anyone explain please ?

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

    Alice won 18 rounds and lost 2 rounds , there is no points thing here so doing 18-2 is not needed. the maximum number of wins will just be 18

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stack>
#include <queue>
#include <set>
#include <utility>
#include <map>
#include <stdlib.h>
using namespace std;
typedef long long int ll;
const int mod = int(1e9 + 7);
// problem c
///////////why this code give wrong on 1337 please help.\/////////////




// it is optimal to increase and then copy the element 
// my approch to binary search->
//my search range is l=0 to h=n; here h=n b/c [ maximum moves we can obtain by increasing only]
//for example --
//n=42
//l=0 and h=42 
//mid=12 moves
// 2 2 3 3 4 4 5 5 6 6 7 7 
// let x=(mid/2)+1 -->(6+1=7)
//so sum=2*((x*(x+1))/2)-2     -->                       ( -2 for 1 1)
//if(sum>=n)then search in the left
// if(sum<n)then search in the right ;







ll check(ll m,ll n)
{
    
    if((m%2)==0)
    {
        int x=m/2;
        x=x+1;
       ll sum=x*1ll*(x+1);
       sum=sum-2;
       if(sum>=n)return 1;
       else
       return 0;
    }
    else// when mid is odd
    {
        int x=m/2;
        x=x+1;
       ll sum=(x+1)*1ll*(x+1);
       sum=sum-2;
       if(sum>=n)return 1;
       else
       return 0;
    }
    
    
}
ll solve(ll n)
{
   if (n==1)return 0;
    ll l=0,h=n-1;
    ll mid=l+((h-l)/2);
    ll ans=INT32_MAX;
    while(l<=h)
    {
        mid=l+((h-l)/2);
        if(check(mid,n))
        {
            h=mid-1;
            ans=min(ans,mid);
        }
        else
        {
            l=mid+1;
        }
    
    }
    return ans;
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
 ll t;
 cin>>t;
while(t--)
{
     ll n;
     cin>>n;
     cout<<solve(n)<<endl;
}
  return 0;
}
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can any one explain when m is odd in problem B the answer be NO !!

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

    How does that happen ?

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

    Since m*m is not divisible by 2*2 for odd m so you can never tile this m*m square in the first place.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

F to very nice problem hai!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

soln can someone tell why this solution works for problem c?

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

easy solution for C

formula

is the answer https://codeforces.com/contest/1426/submission/94245532

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

in rock paper scissors i got the max win part but i am not able to i understand the min win part

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
int main() {
	int o=1,a=0,ab=0,abc=0,n;
	scanf("%d",&n);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++) {
		if(s[i]=='a')a=(a+o)%mod;
		if(s[i]=='b')ab=(ab+a)%mod;
		if(s[i]=='c')abc=(abc+ab)%mod;
		if(s[i]=='?') {
			abc=(3ll*abc+ab)%mod;
			ab=(3ll*ab+a)%mod;
			a=(3ll*a+o)%mod;
			o=o*3ll%mod;
		}
	}
	printf("%d\n",abc);
	return 0;
}

Can anyone tell why we are changing abc,ab,a,and o values in reverse order in s[i] = '?' section and what is the significance of using variable 'o' here

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

    "o" is the total number of possible strings so far (it's equal to 3^(number of ?s))

    The assignments are done "backwards" because to calculate abc you need the original ab, not the updated one (same for ab and a, and a and o).

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody help me to approach problem D? I am not able to understand the editorial also.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I need a little help in Problem E :- I thought of solving it like counting number of subsequence of "abc" the transition is trivial to counting number of sub-sequence . i.e if the current characters match then dp[i][j] = dp[i-1][j-1] + dp[i-1][j] and when it doesn't match and current is not equal to '?' then dp[i][j] = dp[i-1][j]. For the question mark part dp[i][j] = dp[i-1][j-1] + 3*dp[i-1][j] actually out of 3 possible character one of it is going to be equal and rest 2 not so this case is just sum of previous 2 cases.

Everything is fine but for consecutive '?' it is wrong for eg for the last sample test-case it gives 44 instead of 46. Can anyone provide feedback am i missing some case??

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

    You are missing one thing. Let's say $$$dp(i,\text{'a'})$$$ is the amount of times $$$\text{'a'}$$$ appears in all sequences on prefix $$$[1\dots i]$$$. Let's also say that $$$k_i$$$ is the amount of question marks on prefix $$$[1\dots i]$$$

    Then,

    $$$dp(i,\text{'a'}) = dp(i-1, \text{'a'}) + [s_i = \text{'a' or } s_i = \text{'?'}] \cdot 3^{k_{i-1}}$$$
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

cannot understand the condition ? please someone elaborate the condition :

x-1+((n-x)+x-1)/x

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why do we add a 0 to the set after clearing it?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell what is wrong in my code please

https://codeforces.com/contest/1426/submission/94357901

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain problem D

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it
#include<iostream>
#include<string>
using namespace std;
int main(){
    long long MOD=1000000007;
    int n;
    cin>>n;
    string s;
    cin>>s;
    long long a=0,b=0,c=0,mul=1;
    for (int i=0;i<s.length();i++){
        if (s[i]=='a'){
            a += mul;
            a %=MOD;
        }
        if (s[i]=='b'){
            b += a;
            b %= MOD;
        }
        if (s[i]=='c'){
            c += b;
            c %= MOD;
        }
        if (s[i]=='?'){
            c = (c*3 + b) % MOD;
            b = (b*3 + a) % MOD;
            a = (a*3 + mul) % MOD;
            mul = (mul * 3) % MOD;
        }
    }
    cout<<c;
    return 0;
}
I have a better solution.
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain how he find min numbers of win in E problem I didn't understand what he was telling in tutorial.

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

    try all the combinations.6C2=720 ways to permute all possible options to find the best way. Use next_permutation from C++ for trying all possible combinations.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi everyone,I am struggling with Div3 E problem(Stone Paper Scissors).Actually i don't understand how to find the minimum wins even after looking the editorial as well as other coders's code? What is the concept of max-flow as well as min-flow in that question ? Can anyone explain it to me ? Thanks in advance

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E the order matters. Random order will give WA.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain me why this logic was not working for question 1 --->

~~~~~ float n,x; cin>>n>>x; cout<<ceil((n-2)/x)+1<<endl; ~~~~~

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In the E problem , can't we take the case of maximum wins for the other player and the remaining wins belongs to the first player.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain me, why in problem c solution, ans = min(ans, x — 1 + ((n — x) + x — 1) / x) is written, and not ans = min(ans, x — 1 + n/x). I mean it will take x-1 increments to make 1 equal to x and then the number of moves to make the sum greater than equal to n will be n/x. Please point out where I'm making mistake.

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

C can be done easily....and I am talking about the o(1) one...☺

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

How does sqrt(n) solution pass in problem C? There are 1000 test cases and 1000*sqrt(1e9) = 31622776. isn't 30 million operations too much for one second? I think around 2 million operations are maximum for 1 second. vovuh please let me know. Thanks.

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

Can anybody tell me why my code is giving TLE? I have tried everything but can't figure it out. 95270474

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

95411296 can anyone tell me what is the problem with this submission for D

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

problem C: we should copy the number k the square root of the least perfect square that not less than n then the answer is k — 1 + (n — 1) / k

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

I solved E with simple recursion. My submission if anyone interested.

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

HI can some one please explain E , for MAX case

what i thought was for alice to be max ans = min(a1,b3) + min(a2,b1) + min(a3,b2).

1)can someone tell me why it is not. 2)and why will min(a1,b2)+min(a2,b3)+min(a3,b1) give Alice max.

I am not at all good, Please explain me as a 5 year old child, please.