IgorI's blog

By IgorI, history, 4 years ago, In English

Thank you for participating in the contest! I hope you enjoyed the tasks. Here is an editorial with hints.

1474A - Puzzle From the Future

Hint 1
Hint 2
Editorial
Solution

1474B - Different Divisors

Hint 1
Hint 2
Hint 3
Editorial
Solution

1474C - Array Destruction

Hint 1
Hint 2
Hint 3
Hint 4
Editorial

1474D - Cleaning

Hint 1
Hint 2
Hint 3
Hint 4
Editorial
Solution

1474E - What Is It?

Hint 1
Hint 2
Hint 3
Hint 4
Editorial
Solution

1474F - 1 2 3 4 ...

Bonus
Editorial
Solution

Good luck in your future contests!

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

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

thanks for fast editorial

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

Hope I'll become Candidate master today without new year's magic ;)

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

Man!!! That was really quick! Nice hints and clear insight.

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

If negative numbers allowed in problem C, Is this problem still can be solved ?

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

    Sorry I underestimated the fact that, the X will become variable in case of negatives. Ex : 6 4 1 -2 Here we can make X = 5, {4, 1} -> {6, — 2}

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

Thanks!

»
4 years ago, # |
  Vote: I like it +40 Vote: I do not like it

Good contest, despite O(N^2LogN) not passing in java for C

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

I am not understanding why i am getting tle verdict in third problem. I think i am doing it in O(n2⋅logn) but i am wrong maybe . Here is a link to my submission https://codeforces.net/contest/1474/submission/104839937 I would be extremely glad if someone can point out the error.

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

    for me also the multiset solution was not passing then I did it using the count array as the numbers were restricted to 10**6. So, I modified it to O(N^2) solution.
    Upd: sorry did not knew that count operation in multiset takes linear time.

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

    I think the issue is in the part after you calculate as where you do s.erase(dusra). Instead you should do s.erase(it).

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

      Thanks it solved the provlem. I meant to write it only there i don't know what i was thinking then.

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

      I don't understand why 104806538 is getting TLE in problem C. I think it is n2*logn and should pass. It would be very helpful if someone can point out the issue.

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

There doesn't seem to be any hacking round, so When is the rating gonna be updated?

»
4 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Very well written tutorial. While solving C using multiset; one needs to remember that erasing an element by value will delete all elements having same value. And it costs you time to debug it and to read online documents.

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

Problem 1474D - Cleaning. I supposed that, if we don't use the ability, the answer is "yes" if and only if the sum of numbers on odd positions is equal to the sum of numbers on even positions, and every number is not greater than the sum of it's neighbors. But the solution fails: 104836378. Is my idea wrong, or is it because of some mistake in the implementation? I wasn't able to find any couterexample(and the test on which it fails is unvisible) nor any formal proof. Thanks in advance.

UPD: I have found the counterexample. Very weird my solution passed all those millions of tests.

1
8
2 2 4 3 1 2 1 1
  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I used the same idea and it worked. You can check my submission.

    UPD: the counterexample isn't complex but I just couldn't find one during the contest.

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

      Thank you, it turns out I used bool instead of int for the prefix sums array, that was the mistake.

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

        Do you have any formal proof of this solution(I also had the same intuition while trying to upsolve it but sadly i cannot prove it)?

        Thallium54 kkite_gk

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

          Sadly, no one can prove it because it is simply wrong. See my comment above.

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

        Can you please tell why my submission is not accepted like I am also doing using similar approach

        https://codeforces.net/contest/1474/submission/104876110 [My submission]

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

          Sorry, no idea. Try checking if all the indices are correct.

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

            Some people were lucky and their solution got accepted otherwise it is giving wrong answer on

            1

            13

            1 2 2 3 1 3 2 1 2 1 2 2 2

            answer should be no but your and mine approach gives Yes

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

      Can you please explain how to choose x for C problem ? i'm stuck at that.

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

        From the problem statement it can be observed that x will decrease with each operation. So it is necessary for us to take maximum element as one of the constituent of x.

        why

        So we must combine each of the element with the maximum to get a new potential value of x. and check if it is feasible to go with that value of x.

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

I was only able to solve A and couldn't finish debugging C. Just found out that the only bug in my C code was m.find(t)--. (It should be m[t]--)

-99 rating. YAY never been happier

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

I don't really understand the explanation for D. Can somebody explain/give an example for how p_i and s_i are calculated, and what the check mentioned in the last paragraph is? A link to a solution that implements this method would be just as good as well.

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

    I think you should first focus on improving your problem solving skills rather than wasting time in making youtube videos.

    p.s. NO intention of offending you but just an advice, rest on you .

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

My Java Solution for Problem C: 104839108
Isn't it O(n^2logn) ? I used to HashMap.

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

    Can you help me with my Java submission for C. Its giving TLE even though its O(n^2 logn) 104873241

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

      No, it's $$$O(n^3)$$$: for each starting $$$x$$$ ($$$2n$$$ variants) you $$$O(n)$$$ times call $$$contains()$$$ and $$$remove()$$$ from $$$ArrayList$$$ $$$l$$$, where at least one call of $$$remove()$$$ is removing the first element and works in $$$O(n)$$$.

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

in 1 sec per test: will our code of O(n^2) passes? if 1<=t<=1000 and 1<=n<=1000 because i read only 10^7 operations will pass... but here (n^2)*t will be around 10^9 right.. any clarification on this will be appreciated...

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

    It is guaranteed that the total sum of n over all test cases doesn't exceed 1000.
    This means: Whether how many test cases there are, n will never exceed 1000. You can remove 't' from your complexity here. Suppose t=1000. Then the value of n in each test case will be 1 only.

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

    "It is guaranteed that the total sum of n over all test cases doesn't exceed 1000."

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

This editorial is awesome as it totally focuses on concepts instead of spoon-feeding.

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

It's hard for me to understand why there is only one way to make all numbers equal to 0 in problem D. I don't get how proof works. Can someone explain ?

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

    Start from a[0], it necessarily takes a[0] operations. Apply those and now a[1] is fixed and a1~n-1 is a similar problem.

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

My soln of F is similar to the model soln mentioned in the editorial of 1295F - Good Contest.

Firstly in linear time, we can compute the length of LIS.
Let's fix a minimum element of LIS say X and length by L. Then we know that LIS is $$$X,X+1,..,X+L-1$$$. We will loop over all possible Xs.

dp[0][X-1]=1.
dp[i][j] is no of LIS starting at X and end at j using first $$$d_1,d_2,...,d_i$$$
This soln works in $$$O(n*(max(Pi)-min(Pi))$$$.
One can refer to this Bruteforce soln for more details about DP states.

Soln in one line — dp[i] is a piecewise polynomial function of degree atmax i in j.

Let's denote B be the set of all values in prefix sum of the given array in increasing order.
Important thing to note here is there exsists a polynomial P(x) of degree less than or equal to i such $$$P(B_l)=dp[i][B_l],P(B_l+1)=dp[i][B_l+1],...,P(B_{l+1}-1)=dp[i][B_{l+1}-1]$$$.
So instead of maintaining $$$O(B_{l+1}-Bl)$$$ states we can just maintain i+1 values and interpolate this polynomial whenever required.

Also, X belongs to B.
For each polynomial, we maintain O(n) values. Interpolation takes O(n). There are $$$O(n*n)$$$ polynomials for each $$$X$$$.
This soln works in $$$O(n^4)$$$.
AC Submission

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

I just added solutions in C++ to all problems.

There are some problems with spoilers now, so hints are published without any spoilers (actually it is the reason editorial wasn't pusblished just after the contest).

Anyway, thanks again for taking part in my contest and discussing its problems.

UPD: Now hints should be ok

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

    The Problems were beautiful.

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

    Great problems. The hints in the editorial are excellent as well. Thanks for a very interesting problem set.

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

Hey, can someone explain why am I getting time limit exceed for problem C : https://codeforces.net/contest/1474/submission/104834766

I used a O(n^2log(n)) solution, normally it should pass..

I used an unerdored map in the last seconds and got accepted in 982 ms.

Thanks in advance

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

Can someone tell me Time complexity of my code , I think it is O(N^2) approx. https://codeforces.net/contest/1474/submission/104834839

»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Here are my video solutions of this round for A-E, which I'm really glad I didn't do a screencast for

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

Can someone explain why we don't need to check the case where $$$a = p^3$$$ in problem B ?

In other words why can't a solution be of the form: $$$1$$$ $$$p$$$ $$$p^2$$$ $$$p^3$$$ ?

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

    $$$p_1.p_2 < p_1^3$$$ where $$$p_1 > d, p_2 \geq p_1 + d.$$$ Since, we're asked to find the minimum integer $$$x$$$. Maybe, It's also because prime numbers are dense at the start.

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

      what if $$$p_1^2 < p_2$$$ ? or that just never happens due to the limits of this problem ?

      $$$p_1^2$$$ being greater or equal than $$$p_1 + d$$$

      $$$p_2$$$ being next prime greater or equal than $$$p_1 + d$$$

      any formal or convincing proof that this never happens?

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

        Bertrand's postulate, proven in 1852, states that there is always a prime number between k and 2k, so in particular $$$p_{n+1} < 2p_n$$$.

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

        As pointed in above comments , we can prove using Bertrand Postulate .

        More formally suppose you say answer is $$$p^3$$$ and thus it's factors are $$$1,p,p^2,p^3$$$ . Difference between each of them should be greater than $$$d$$$. Thus $$$p_1≤p$$$ . Using Bertrand Postulate we can say that there must exist prime $$$p_2$$$ such that $$$p<p_2<p^2$$$ , since smallest prime is 2. Hence $$$p_1*p_2$$$ is better answer.

        You asked very good question , I never thought of it during the contest.

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

          No, I don't think $$$p_1^2 < p_2$$$ since $$$2p_1 < p_1^2, \forall p > 2$$$.

          We can further postulate that, there also exist a prime, $$$p_x$$$ that is less than $$$4p_n$$$ with Bertrand's Postulate since, $$$p_{n + 1}$$$ may not be greater than or equal to $$$p_n + d$$$.

          Thus, We can prove that $$$p_n . p_x < p_n^3$$$.

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

            I wrote $$$p < p_2$$$ .It's called proof by contradiction. So i assumed that $$$p^3$$$ is the best answer but then we arrived at contradiction that a better answer would exist in that case.

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

              Using Bertrand Postulate we can say that there must exist prime $$$p_2$$$ such that $$$p^2<p_2<p^3$$$.

              I don't know if this is called proof by contradiction. It'd be correct if you change the order as $$$p_2 < p^2 < p^3$$$ according to Bertrand Postulate.

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

                In Bertrand Postulate , take $$$n=p$$$ , also $$$p≥2$$$ , thus there must exist prime $$$p_2$$$ such that $$$n<p_2<2n≤p^2$$$. So how my argument wrong ?

                Thus we have better answer $$$p_1*p_2$$$ but that's contradiction since best answer was $$$p^3$$$ . Hence our assumption that $$$p^3$$$ will be best answer was wrong . Thus answer must be of form $$$p_1*p_2$$$.

                proof by contradiction . In this to disprove something we first assume it's correct and then arrive at some contradiction . Here i assumed $$$p^3$$$ is correct and then we arrived at contradiction .

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

                  In Bertrand Postulate , take $$$n=p^2$$$ , also $$$p\geq2$$$ , thus there must exist prime $$$p_2$$$ such that $$$n<p_2<2n≤p^3$$$.

                  I get what you're saying. But $$$p^2$$$ has to be a prime number in order to use Bertrand's postulate.

                  proof by contradiction. In this to disprove something we first assume it's correct and then arrive at some contradiction . Here i assumed $$$p^3$$$ is correct and then we arrived at contradiction.

                  Thank You, I didn't read about this before.

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

                  It can be any integer .

                  I get what you're saying. But $$$p^2$$$ has to be a prime number in order to use Bertrand's postulate

                  read here :

                  A less restrictive formulation is: for every $$$n>1$$$ there is always at least one prime p such that $$$n<p<2*n$$$
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          Rev. 7   Vote: I like it +3 Vote: I do not like it

          When you said p ^ 2 < p2 < p ^ 3, didnt you actually prove p1 * p2 is a worse answer? Because suppose p1 = p so then p1 * p2 > p * p ^ 2, because p2 > p ^ 2. So optimal would be p ^ 3.

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

            Thanks for pointing it out , I have corrected it now. Actually i needed to write $$$p<p_2<p^2$$$ and thus $$$p_1*p_2$$$ is smaller.

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

This "Hint by Hint" format is nice. Keep it up.

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

I would be very thankful if someone can find the bug in my code https://codeforces.net/contest/1474/submission/104847038 I'm unable to figure it out

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it
    Testcase:
    
    2
    
    8  2  4  5
    
    Correct Answer:NO
    
    Your OUTPUT:
    
    YES
    
    13
    
    5 8
    
    4 4
    
    2 2
    
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Problem B can be solved with help of regexes, as N is not big. Try it yourself.

Spoiler 1
Spoiler 2
Spoiler 3

Solution 104855574

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

The time constraints for C are absolutely atrocious, I tried 3 different n^2 log n implementation and I wasn't able to make any of them pass

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

If anyone is stuck at C https://youtu.be/Y_53vVG7RMw

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

I still have a question about prob D, why we just talk about the swap between 'a[i]' & 'a[i+1]' ?

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

    Before the start of cleaning, you can select two neighboring piles and swap them.

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

      Oppps, what an idot i am... :(

      by the way, what if there's no this "neighboring" limit?

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

        I think there is n^2 solution then

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

My solution is getting WA on test 2 and I don't understand why. Can someone please give me a test case where this fails?

https://codeforces.net/contest/1474/submission/104864709

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

I got a few doubts in n* +max(a) solution of c

if (cnt[a[j]] < 0 || cnt[x - a[j]] < 0)
            {
                cnt[a[j]] = 0;
                cnt[x - a[j]] = 0;
                break;
            }

when the cnt of a[j] will be less than zero ? as for in while loop we check that cnt[a[j]]>0 also if i comment it out, then why it gives wrong answer since in reset(a) after ops, we are anyway setting cnt[a[i]] to zero ?

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

brilliant idea for problem D

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

Is +460 in first codeforces contest good? What is the metric for good and bad for codeforces contests?

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

This format of multiple hints and then answering them is great

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

Problem D, Now we have 0 stones in the 1-st pile and a2−a1 stones in the 2-nd pile. I understood this.

We can apply the idea above and get that we should have a2−a1 stones in the 3-rd pile. How do we get a2-a1 for 3-rd pile?

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

Why I'm getting RE in Case 6 in problem C, Help me (O_O) :

104870245

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

    upper limit for a[i] is 10^6 but you have made the size of array f as 10^5 so f[a[i]]++ will end up with run time error(as 10^6>10^5 so its array size issue).

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

      Tnx Man :). Got Ac . Verdict Time : 998 :( 104875146

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

        For each test case, you create a new array $$$f$$$ of size $$$10^6$$$. Don't know why you are sad — you are lucky to get AC on Java with it.

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

What's wrong with my D? I'm confused. 104868453

I'm not good at English..Emm...

If I don't use the superability,it will be ``` b[1]=a[1] b[2]=a[2]-a[1] b[3]=a[3]-a[2]+a[1] ... b[n]=a[n]-a[n-1]+a[n-2]-...

For odd numbers : b[n]=a[n]-a[n-1]+a[n-2]-...-a[2]+a[1] For even numbers : b[n]=a[n]-a[n-1]+a[n-2]-...+a[2]-a[1]

if we swap(a[pos],a[pos]+1]) b[pos] will -a[pos]+a[pos+1]

for i>=pos+1 i%2=(pos+1)%2: b[i] will -2*a[pos+1]+2*a[pos] i%2=(pos+2)%2: b[i] will +2*a[pos+1]-2*a[pos]

I want b[n]->0 and all i in [1,n] b[i]>=0 I calculate suffix(suf) and prefix(pre) ``` Oh,I can't make it any clearer,I'm poor in English...

upd: Accepted

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    If I don't use the superability,it will be
    b[1]=a[1]
    b[2]=a[2]-a[1]
    b[3]=a[3]-a[2]+a[1]
    ...
    b[n]=a[n]-a[n-1]+a[n-2]-...
     
    
    For odd numbers  : b[n]=a[n]-a[n-1]+a[n-2]-...-a[2]+a[1]
    For even numbers : b[n]=a[n]-a[n-1]+a[n-2]-...+a[2]-a[1]
     
    if we swap(a[pos],a[pos]+1])
    b[pos] will -a[pos]+a[pos+1]
    
    for i>=pos+1
    i%2=(pos+1)%2: b[i] will -2*a[pos+1]+2*a[pos]
    i%2=(pos+2)%2: b[i] will +2*a[pos+1]-2*a[pos]
     
    I want b[n]->0 and all i in [1,n] b[i]>=0 
    I calculate suffix(suf) and prefix(pre)
    
    Oh,I can't make it any clearer,I'm poor in English...
    
»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

C was just awesome.

I solved it using the idea that at each operation we have to select two numbers among which one is always the maximum number among the remaining non selected numbers and the other number can be any number among non selected numbers such that sum of both numbers is equal to x(and then update x and repeat the process) If we can not do it for any selected x then answer will be No. And initial x can be (maximum of all numbers+ any other number from array).

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

Hello , Thanks for this awesome contest and awesome solution for Problem D.

However I tried to solve D using segment trees and I am able to get AC on it. What I am doing is creating two array for odd and even position and trying every swap by making appropriate updates and then rolling back to original states. I could'nt see anything wrong in my solution. Can someone help me figure it out ?

My code

Update: Figured out my bug, I skipped the fact that I had to update previous element also. xd

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

104885466 why i am getting tle

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

    Because if your use find(ms.begin(), ms.end(), val) it is linear in time, instead you should use ms.find(val), which is O(log n). I submitted your code 104886371 with it and got AC.

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

for some reason i feel tired of constructive problem.i dont hate them but while doing them i just feel so weird and solution often suprised very hard (like an unexpectd slap)

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

I advise everyone to watch this video, hope would be helpful!

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

Can we solve problem D if we are allowed to swap any two piles once? It could be a variation for this problem.

Suggesions are much appreciated.

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

If someone pls could help ! their solution for C without set ..isn't it O(n³) ? if not then why coz the three loops in worst case are gonna iterate and complete to their limit ?

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

Can anyone tell what is wrong in my D? WA on test 2: 105030694

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

Still stuck in problem D, can anyone help me? :| thanks. 105049987

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

    my latest WA submission #105067344

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

    Oh, I find out why. in case 0 if (Smark==n+1 && s[n]==0) in case 2 (a[i]-s[i-1]>=0 && a[i+1]-p[i+2]>=0 && a[i]-s[i-1]==a[i+1]-p[i+2] && s[i-1]>=0 && p[i+2]>=0)

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

somebody please explain why this is giving TLE for problem 1. https://codeforces.net/contest/1474/submission/104916660 again for problem 1, the following code prints all digits as 1, i cant see why it is happening https://codeforces.net/problemset/submission/1474/105175403

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

    hey combinatorialist, well I don't know the reason , but in your code this is because of you are using strings and append in strings like a=a+'1'; and b=b+digit; my suggestion is if you use the char array like this

    char a[(int)1e5+5],b[(int)1e5+5];
    int ai,bi;
    int main(){
        int t;
        cin>>t;
        vector<string>sol;
        while(t--){
            memset(a,0,sizeof(a));
            memset(b,0,sizeof(b));
            ai=0,bi=0;
            int prevsum=0;
            char digit;
            int n;
            cin>>n;
            for (int i=0; i<n; ++i){
                 cin>>digit;
                b[bi++]=digit;
                if(b[i]+1!=prevsum){
                    a[ai++]='1';
                    prevsum=b[i]+1;
                    continue;
                }
                if(b[i]!=prevsum){
                    a[ai++]='0';
                    prevsum=b[i];
                }
    
            }
            sol.push_back(a);
    
        }
        for(auto x:sol){
            cout<<x<<endl;
        }
    
    }
    
    

    hope this helps...

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

      ok.....can you also look at my second submission, it is printing every digit as 1, i cant understand why. https://codeforces.net/problemset/submission/1474/105175403

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

        bro your code is correct! You just make 1 to '1' and 2 to '2' in if(sum-b[i]==2) and else if(sum-b[i]==1) as it is character so it's sum is 97 ans you are comparing it with 2;

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

          ok, it worked...but i am still confused. when i write int sum=a[i]+b[i], this means that int sum='1'+'1' which should mean int sum="11", and then the string "11" will be converted to int? basically i am getting confused in adding two chars and then converting into int, can you explain or give me a resource from where i can read this?

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

            here co is cout<<

            char a='1',b='2';
            co a+b<<nl;///99
            co (char)(a+b)<<nl;///c
            co a-'0'+b-'0'<<nl;///3
            

            when you add two char it automatically becomes int until you convert it into char.

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

Hints for problems is such a great idea! I believe that hints+editorial is way better because some people may need just a bit of help to upsolve. Setters, please, make hints+editorial.

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

My $$$O(N^2)$$$ java sol for problem C is getting TLE. But such similar solution of others getting passed. Can anyone tell why it's getting TLE. I thought a lot but unable to figure it out. Anyone please.

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

For problem D,in case of no superability, why should we start from 0 ? why not from position n-1 ?