oolimry's blog

By oolimry, history, 7 months ago, In English

1428A - Box is Pull

Setter: bensonlzl
Prepared by: errorgorn

Hint 1
Hint 2
Solution
Code (C++)
Code (Python)

1428B - Belted Rooms

Setter: oolimry
Prepared by: oolimry

Hint 1
Hint 2
Solution
Other comments
Code (C++)
Code (Python)

1428C - ABBB

Setter: errorgorn and shenxy13
Prepared by: errorgorn and oolimry

Hint 1
Hint 2
Solution
Other comments
Code (C++)
Code (Python)

1428D - Bouncing Boomerangs

Setter: bensonlzl
Prepared by: bensonlzl

Hint 1
Hint 2
Solution
Code (C++)
Code (Python)

1428E - Carrots for Rabbits

Setter: errorgorn
Prepared by: errorgorn
Orz proof by: oolimry

Hint 1
Hint 2
Solution
Other comments
Code (C++)
Code (Python)

1428F - Fruit Sequences

Setter: bensonlzl
Prepared by: dvdg6566

Hint 1
Hint 2
Solution
Other comments
Code (C++)
Code (Python)

1428G1 - Lucky Numbers (Easy Version), 1428G2 - Lucky Numbers (Hard Version)

Setter: oolimry
Prepared by: oolimry

Hint 1
Hint 2
Hint 3
Hint 4
Solution
Code (easy version)
Code (hard version)

1428H - Rotary Laser Lock

Setter: bensonlzl and oolimry
Prepared by: bensonlzl

Hint 1
Hint 2
Solution
Code
 
 
 
 
  • Vote: I like it
  • +271
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Auto comment: topic has been updated by oolimry (previous revision, new revision, compare).

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this posted before 5 hours, or is there a way to post only for private?

»
7 months ago, # |
Rev. 2   Vote: I like it -40 Vote: I do not like it

Fast editorial.

»
7 months ago, # |
  Vote: I like it +126 Vote: I do not like it

I love the approach of adding hints in editorial.It really helps a lot by solving problem without seeing exact solution. Nice editorial!

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

    Giving some hints before showing the exact solution is very helpful(as it helps to think better). How nice it would be if everyone wrote the editorials like this!

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

      It would be very helpful if this style of adding hints is made mandatory.

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

    C : video sol. although editorial is also good and quick.

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

the editorial went out very quickly .. thanks

»
7 months ago, # |
  Vote: I like it +14 Vote: I do not like it

fast editorial

»
7 months ago, # |
  Vote: I like it +14 Vote: I do not like it

So Fast!!!

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

Loved the problem statements!!!

»
7 months ago, # |
  Vote: I like it +39 Vote: I do not like it

having lots of templates in the editorial codes makes the code harder to undrastand. if the codes were with less template(or the template which almost every one have like ll) it would be better.

»
7 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Any ideas for solving E for k<=1e18?

  • »
    »
    7 months ago, # ^ |
    Rev. 3   Vote: I like it +14 Vote: I do not like it
    spoiler
    • »
      »
      »
      7 months ago, # ^ |
      Rev. 3   Vote: I like it +9 Vote: I do not like it

      It seems it's too slow unless you can get rid of second bsearch: link. (Not to mention overflow for higher values)

      Edit: Using cuom1999's optimization below, I also ended up getting AC: link.

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

        I was able to get AC with some very similar code (95816754), but one second does seem to be a somewhat tight time limit, at least for these approaches.

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

          May i ask a question? why i submit your AC code, but it show TLE on Test6

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

          oh, i change the lang to G++17(64), it ac now, do you konw the reason?

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 2   Vote: I like it +19 Vote: I do not like it

      We can estimate the second binary search like this.

      Let's denote $$$cost(a, b)$$$ cost of dividing $$$a$$$ carrots to $$$b$$$ rabbits. We want to find $$$b$$$ such that $$$cost(a, b) + C * b$$$ is minimized, where $$$C$$$ is the parameter in Alien Trick.

      We can estimate $$$cost(a, b)=b*(\dfrac{a}{b})^2=a^2/b$$$. So $$$cost(a, b) + C * b = \dfrac{a^2}{b} + Cb$$$.

      This is minimized when $$$b$$$ is around $$$\dfrac{a}{\sqrt{C}}$$$. We can binary search only $$$50-100$$$ values around this number. Link 95819034

      P/S: This analysis gives us the hint that $$$C$$$ should be around $$$O(max(a_i)^2)$$$ in the worst case, which means we should binary search $$$C$$$ from $$$0$$$ to $$$~10^{12}$$$. I got WA due to ignoring this :(.

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

    Maybe WQS

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

      that's called "Alien trick" in other countries (WQS binary search in China)

      the word Alien is referring to IOI2016 D2T3

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

        I think that it's more often called "parametric search" or "lambda optimization".

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

          More often called Lagrange multipliers.

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

            Hey, where can I learn this trick/search technique? Is there a particular resource that helped you? I have tried out a few resources (hard to follow sometimes because of language differences), the intuition is clear but the proofs of convexity are generally missing. Any links that have a rigorous explanation of this trick?

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

    Suppose $$$n < k$$$ and consider the priority queue solution described in the editorial. The last cut added will have some value $$$V$$$. The idea is that there will be at least $$$k - n$$$ cuts possible to make with value at least $$$V$$$, but fewer than $$$k - n$$$ cuts possible to make with value greater than $$$V$$$, and this number of cuts can be calculated in $$$O(n \log(\max a_i))$$$, also using binary search. After finding $$$V$$$ the answer is easy enough to calculate: Make every possible cut with value at least $$$V$$$. Calculate the total eating time for this many cuts, then account for any extra cuts made by adding $$$V \cdot ((\text{cuts actually made}) - (k - n))$$$, since every extra cut has value exactly $$$V$$$.

    The overall time complexity of this is $$$O(n (\log (\max a_i))^2)$$$.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How come everybody suddenly started hacking 'B'?

»
7 months ago, # |
  Vote: I like it +6 Vote: I do not like it

I solved A, B, C and then I tried D and then I tried D and then I tried D.. and then contest was over. ;-;

»
7 months ago, # |
  Vote: I like it +54 Vote: I do not like it

I forgot about linking-3-with-3 case in problem D

big F

»
7 months ago, # |
  Vote: I like it +45 Vote: I do not like it

I hate problem D.

»
7 months ago, # |
  Vote: I like it +22 Vote: I do not like it

I really like these hints in editorials. Sometimes I feel its better to see hints and work through them instead of seeing full editorial. Thank you so much.

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

.

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

    The answer will not be worse if there is at most one number whose digits is not entirely 0, 3, 6, 9. ans = [ 96, 94 ]

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

      yup got it few second after I commented

      Thanks ^^

»
7 months ago, # |
  Vote: I like it +13 Vote: I do not like it

G: 0/K knapsack can be solved in same time complexity with 0/1 knaspack using deque, improving time complexity of the knapsack part to $$$O(nd)$$$.

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

    I actually did not know that, thanks for sharing! I was confused at first by the large number of solutions which used deque.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is wrong with normal Priority queue implementation in E?

Spoiler
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Awesome way of posting editorial !! (using hints)

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Fast Editorial and the Editorial is really nice. Thanks to the setters and testers.

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Am i the only one that overkilled B with SCC?

»
7 months ago, # |
  Vote: I like it +91 Vote: I do not like it

Almost everyone in rank $$$1 \sim 20$$$: HACK PROBLEM B!!!

Me: see that? GO HACK PROBLEM B!!!

checked every code in my room...

my room:

NO FST

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

    This time I am unluck either :( When can I arrive LGM again QwQ

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

    Can anyone please tell me what is that why that green red color appears when I open any solution in my room? One more question- If I open a solution and don't hack it, will I get any penalty for that?

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

As a new comer, i really enjoyed this contest and found the contest interesting .Thanks a lot !!

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

Why is there a preference of choice for matching 3 in D??? Update: Got it!!!

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

    I think this is to save maximum 1's for the columns having 2's in the left. Because 2's can only be matched to the unmatched 1's in the right.

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

Thanks for adding hints, fast editorial and nice problems.D was beautiful

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks for the hints

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I really appreciate the hints in this editorial, they give a different perspective to problem upsolving. I hope to go up in rating after a long time!

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

    your contribution is a positive .... for now ....

»
7 months ago, # |
Rev. 4   Vote: I like it -11 Vote: I do not like it

[Deleted]

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    1 3
    10
    

    For this case, you would split the carrot into 2, 3, 5 but the optimal solution is 3, 3, 4.

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

    [Deleted]

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      9 100000
      898512 885257 979202 697216 70837 914905 415207 599338 11710
      

      The answer should be 299468056, but your solution outputs 305594044.

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

For problem C:

Bonus: what is the length of the longest string that Zookeeper can make such that there are no moves left?

Would running the same algorithm on the reversed string be a correct approach?

»
7 months ago, # |
  Vote: I like it +26 Vote: I do not like it

An alternative solution for F: This problem can be solved by using Segment Tree Beats, specifically one of type 2. If we consider a sweep from left to right, storing the maximum segment from 1 to i in a subarray, we can clearly see that the maximum in the current run increases by one, otherwise you can take the maximum of the previous value and the current run. Complexity O(n log^2 n), which actually ACs with a lot of time to spare. I don't really know why. Code: 95789626.

P.S. The main advantage of this solution is that it uses zero brainpower and that you can copy STB templates online.

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

    yes. i actually solved F in about 5 minutes because of this. we tried to kill segment tree beats but other setters wanted nlogn segment tree to pass comfortably. i think that some segment tree beats solutions got killed by our anti segment tree beats testcases tho.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For E, why is it not possible to consider all the carrots in 1 large carrot? Thank you https://codeforces.com/contest/1428/submission/95799505

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

    You cannot glue carrot pieces together, so for example if you had a length 10 and a length 2 the optimal cut is 5, 5, 2.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Idk why some people hating D, but I found it pretty nice. Here is my solution:

Let's process columns from left to right, consider column $$$i$$$ with value $$$2$$$, as explained in editorial we need to connect it with some column $$$j$$$ on the right of it with value $$$1$$$. In order to do that we can just put target to cells $$$(i, i)$$$ and $$$(i, j)$$$. Also, we should skip column $$$j$$$ in later iterations.

For columns with value $$$3$$$ we can connect them with any column with non-zero value and in the same way we add targets to cells $$$(i, i)$$$ and $$$(i, j)$$$. (Note that 3rd part of chain will be added automatically to the cell $$$(j, j)$$$ when we process column $$$j$$$).

And finally for columns with value $$$1$$$, we can just put target to cell $$$(i,i)$$$. It's always safe because there are enough rows for each column

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

    lol as a setter, D gives me trauma from super trees (IOI)

»
7 months ago, # |
  Vote: I like it +13 Vote: I do not like it

F can also be solved with divide and conquer in O(nlogn).

Let g(l,r) be the answer for a segment. Obviously g(l,r) = g(l,m) + g(m+1,r) + "the rest". If you guarantee s[m]!=s[m+1], then "the rest" can be calculated easily with some prefix/suffix max dp and two pointers.

»
7 months ago, # |
  Vote: I like it +47 Vote: I do not like it

Here's a solution video (for A-F) that ends up being more about anxiously waiting to see if I got IGM

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

the way this editorial is formatted and things have been explained ! Kudos for it , I loved the proof in Problem E part

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

Why has the picture in the 1428B - Belted Rooms changed?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the hints. It really makes reading editorial more fun and useful :)

»
7 months ago, # |
Rev. 4   Vote: I like it -15 Vote: I do not like it

.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution for D fails in 11th case. The initial part of the case seems to contain 3 3 3 3 ...

I had tested my code for 3 3 3 ... 1 and 3 3 3 ... 2 1 I think 3 3 3 ... 3 3 should return -1 and so is my code returning.

Where am I going wrong? Thanks. My soln.: https://codeforces.com/contest/1428/submission/95817367

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

    You don't see the whole test, there might be some random numbers, or maybe some 3's at the beginning, then 2's, then 1's. I'll try to find the mistake, but not sure if I can.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Still can't get why greedy solution works for E

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve problem D if a[i] >= 4 ?

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

    We will iterate the array from right to left and will maintain two vectors:
    One storing the co-ordinates(x,y) with only one target in the xth row
    and another storing the co-ordinates(x,y) with two targets in the xth row.
    Lets name the vector of first type as "ones" and of second type as "twos" .
    We will also keep track of the rows which are empty (will be explained later ) .

    For a[i] == 0 :
    For a[i] == 1 :
    For a[i] == 2 :
    For a[i] == 3 :
    How to keep track of empty rows ?

    This concludes it for a[i]<=3.

    For a[i] <= 4 :
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I solved it for a[i]<=4.bensonlzl does the solution seem right to you ?

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

        If I'm understanding your solution correctly, your idea is to match a 4 with a 2-1 pair by storing the column of the 1 that the 2 was matched to. This brings up 3 problems (which I also encountered while solving).

        The first problem is that it is not obvious what the order of processing should be, because the 2-column can lie between the 4-column and the 1-column or it can be to the left of both the 4-column and the 1-column Consider the 2 testcases :

        3
        4 2 1
        
        3
        2 4 1
        

        The second problem is that it is not necessary for the 4 to always match to a 2-1. Consider the following test case:

        3
        1 4 1
        

        This is solvable using the following configuration (_ for blank and X for target)

        _XX
        X_X
        X__
        

        This means that if we process from right to left, we can actually create incomplete 4-1 pairs that are matched to the upper target of columns to their left which do not affect the lower target.

        In fact, while working on the $$$a[i] \leq 4$$$ case, I stumbled upon a way to chain 4-columns:

        _____XX
        ___X__X
        ___XX__
        _X__X__
        _XX____
        X_X____
        X______
        

        The above configuration gives the sequence $$$1,4,1,4,1,4,1$$$. What I discovered was that chaining $$$4$$$-columns can be very messy because a 4 matched to a 1 at column $$$i$$$ can chain to any other 4 to the left of column $$$i$$$, and thus the 4 chains can end up all over the place.

        The third problem is that row configurations come into play here. In the $$$a[i] \leq 3$$$ case, it was relatively easy to deal with the up and down movement of the boomerang. But it gets harder for $$$a[i] \leq 4$$$. An example is the following test case:

        3
        3 4 1
        

        This has no solution, because the 4-column needs a 4th target from the 3-column, but that would make it impossible for the boomerang in the 3-column to go down and find any other target.

        The point is, if someone can find a solution to $$$a[i] \leq 4$$$, I would be very happy. However, $$$a[i] \leq 4$$$ is when row configurations start to matter and where chains and matchings become very messy, so I gave up on solving this and use $$$a[i] \leq 3$$$.

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

Solution to problem 1428D:

1) The order of preference doesn't have to be $$$3,2,1$$$ — it works but isn't the most general. It is choose either $$$3$$$ or $$$2$$$ before considering $$$1$$$.

2) The row number can be assigned while "chaining" the columns. Just start with the first target (which has to belong to a $$$1$$$) in the bottom right corner. While traversing to the left, if it is a $$$1$$$ or $$$3$$$ increase the column number if it is a $$$2$$$ don't.

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

Problem E with k <= 10^18 i think bynary search value MIN and after i check how many value such as f(ai,p) — f(ai,p + 1) >= MIN for each Ai. If the number of value >= MIN no more than K then save it and increase MIN. O(Nlog(Ai)logK)

»
7 months ago, # |
  Vote: I like it -17 Vote: I do not like it

Is Bouncing Boomerangs' code solution in C++ correct? Because after running it I discovered a different answer. Following is the output that I encountered after executing it: 5 1 1 1 6 2 3 2 5 3 5 And the output expected is as follows: 5 2 1 2 5 3 3 3 6 5 6 Correct me if I am wrong.

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

    Both outputs produce the array 2 0 3 0 1 1. They are both correct outputs and will both be accepted by the checker.

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

In 1428D, why is it preferred to chain-up the first 3 from the right, with a 2 and not 1? I mean, suppose 3 is paired with a 1, then why can't that 1 be used with some 2? Please explain.

UPD: I got it!

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

    Your solution will pass even if you chain it with the nearest of 1 or 2 which is unchained , I did the same in my AC solution.

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

E is a nice problem, if you made $$$n, k \le 5000$$$, then $$$O(nk)$$$ trivial dp would pass. Thus, with $$$n, k \le 10^5$$$ it is actually a much nicer problem in my opinion.

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

    can describe your O(nk) dp? I actually dont know how O(nk) dp would work here

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

      I might be wrong but this is my thought process during the contest: there are $$$k - n$$$ "chances" to cut the carrots. Let $$$dp[i][j]$$$ be the best solution to use exactly $$$j$$$ chances on the first $$$i$$$ carrots. I think you should be able to find some recurrences over there. The final answer is going to be $$$dp[n][k - n].$$$

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

        That ia trivial. But im not able to find O(1) transition.

        O(logN) transition has many ways to do but not simple. One way is dnc. Another way is notice that sorting carrots in descending order, number of cuts is non decreasing, which gives us a (n)*(k-n)*(1/1+1/2+1/3+1/4+...) transition bound.

        If you can figure out O(1) transition i would be happy to hear it :)

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

          Oh my bad, I just realized my solution was actually $$$O(nk^2)$$$ lol.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

There should also be a dp tag to problem B. For every node, one could precalculate how much right and how much left one could go from there in O(n) and check for the appropriate conditions.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This hint thing is so helpful. I wonder which round it started? Global round 11 I guess.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution for F requires little thinking. (and little coding time since I wrote a similar code before and copied it...)

Just move $$$r$$$ from $$$1$$$ to $$$n$$$. Let $$$f_i$$$ be the answer for segment $$$[i,r]$$$.

If $$$a_r=0$$$, we don't do anything. (just add the sum of all $$$f$$$ to $$$ans$$$) Otherwise, let $$$lst$$$ be the minimum number that $$$a_{lst}\sim a_r$$$ are all $$$1$$$. Add $$$f_lst \sim f_r$$$ by $$$1$$$, and make $$$f_{1} \sim f_{lst-1}$$$ be the maximum one of themselves and $$$r-lst+1$$$.

Use a segment tree with lazy tags to handle range add and range chkmax. There's a well-known trick on maintaining the sum: maintain the number of minimums in the segment, the minimum in the segment and the second minimum in the segment. If the segment's minimum is greater than $$$k$$$ ($$$k$$$ is $$$r-lst+1$$$) then quit. If the minimum $$$x$$$ and the second minimum $$$y$$$ satisfy $$$x<k\le y$$$ then change the minimum and the count. Else brute force into its left and right sons. The upper bound of complexity is proved to be $$$O(n\log^2 n)$$$. (I don't know the exact complexity though)

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

Sorry for asking, but how does a O(TC*N) solution pass B as max test cases are 1000 and N is 300,000? Wouldn't that be 3*10^8 when 10^8 runs in 1 second?

Same goes for C.

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

    Look at the bottom of Input section. Problem setter declared that It is guaranteed that the sum of n among all test cases does not exceed 300000. This means TC*N will be at most 300000.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How could we solve D with a[i] >= 4?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For 1428E, my approach was 1. Insert all elements into a max heap 2. Select the max element every time, and pop this out. Split this to two halves and insert back these halves into the heap. 3. Continue this till the size of the heap becomes k. But this approach turns out to be wrong. Can anyone tell me what is the issue ? Thanks in advance !!

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

    The problem is if you are splitting an element into some parts it should be as even as possible. Suppose initially your heap contains 10 and k = 3. So you will split 10 into 5,5 and then to 2,3,5 whereas splitting into 3,3,4 will give you a better answer.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For 1428E — Carrots for Rabbits I understand it is obvious that "Clearly, w=floor(l/p) and p2=lmodp." Since we would try to divide equally, but I want to know how it follows from - To calculate f(l,p), we need to find p1,p2 such that p1(w)+p2(w+1)=l and p1+p2=p, minimizing p1(w)^2+p2(w+1)^2." I think an additional constraint is that p1,p2,w are whole numbers.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C++ Implementation of D is clever

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice contest, i have learned a lot of things =)

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

People come to see tutorial if they couldn't managed to get the idea or solve the problem for any other reason. You guys should write the solution code as clean as possible. Using #define is useful for the contestants to minimize the code and time but not suitable for you as it makes the code much difficult to understand. Hope we will see #define less tutorial in the future:)

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

    you can open other people's code. Setters focus on making sure the explanation in the editorial is clear.

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

Can anyone elaborate Firstly, we notice that the contents of the stack do not actually matter. We actually only need to maintain the length of this stack. Decrementing the size of the stack whenever possible is optimal as it is the best we can do. And in the case where we must push B to the stack, this is optimal as the parity of the length of the stack must be the same as the parity of the processed string, so obtaining a stack of length 0 is impossble. for probem C?

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

    The (also acceptable) solution I did was maintain a stack of characters of 'A's and 'B's. Then I push each character and check the top two if it can be removed. Finally, I output the length of the stack.

    The reason that the contents of the stack are unimportant is that if it is an 'A', you will always push it to the stack and if it's a 'B' you will always pop an element (as you can pop "AB and "BB") unless there are no elements on the stack.

»
7 months ago, # |
  Vote: I like it -10 Vote: I do not like it

I think the problems D is too difficult for me to solute. But after all, it is a quite nice experience to attend such interesting game.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can't a 2 be matched with a 3 which is ahead of it ? in problem D

»
7 months ago, # |
  Vote: I like it -10 Vote: I do not like it

PROBLEM E CARROTS FOR RABBITS COMMENTED CODE https://ide.geeksforgeeks.org/zsZx6svH3N

»
7 months ago, # |
Rev. 4   Vote: I like it -13 Vote: I do not like it

SOLVED small error in (x-extra) line, should be (p-extra) thanks :)

Why my code doesnt work for E. its exact same as editorial>????? Help please :(

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define IOS ios_base::sync_with_stdio(0);
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define rep(x,j,n)for(int x=j;x<n;x++)
typedef vector<pair<ll,ll>> vpi;
typedef vector<ll> vi;
typedef vector<vi> vvi;

#define ii pair<ll,ll>
#define iii pair<ll,ii>
ll sq(ll x)
{
    return x*x;
}
ll decrease(ll x, ll p)
{
    ll unit = x/p;
    ll extra = x-unit*p;
    return  ( (x-extra)*sq(unit) + extra*sq(unit+1));
}


    priority_queue< iii> pq;
int main()
{
    IOS
    ll n,k;
    cin>>n>>k;

    ll cost = 0;
    rep(i,0,n)
    {
        ll t;
        cin>>t;
        cost+=sq(t);
        pq.push(iii(decrease(t,1)- decrease(t,2), ii(t, 2)) );

    }

    rep(i,0,k-n)
    {
        cost -= pq.top().fi;
        ll aa = pq.top().se.fi;
        ll bb = pq.top().se.se;

        pq.pop();
        pq.push(iii(decrease(aa,bb) - decrease(aa,bb+1),ii( aa, bb+1)));
    }
    cout<<cost<<'\n';

    return 0;
}

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

For problem F, can someone please explain the line that updates the cur in inner loop? "cur += (l-1+x) — hist[x]" What is it exactly doing & how is it correctly updating the tot?

for (int x = 1; x <= (r-l+1); ++x){
	cur += (l-1+x) - hist[x];
	tot += cur;
	hist[x] = r-x+1;
}

Can you please explain bensonlzl dvdg6566?

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

    The variable $$$cur$$$ stores the current area under the histogram and needs to be added to $$$tot$$$, which is the total sum of areas (aka the answer at the end).

    Here we are considering the segment of 1s from $$$l$$$ to $$$r$$$ inclusive. Now we consider the $$$x$$$-th one in this segment of 1s. The total area this 1 adds is the distance from itself to the last index $$$i$$$ where the height of the histogram is $$$x$$$. You can look at the diagrams in the tutorial to convince yourself that this is true.

    Thus, we need to add $$$l-1+x - hist[x]$$$ to the current area.

    Now if we look what the histogram looks like after we added the entire segment of ones, the $$$x$$$-th 1 from the back is at index $$$r-x+1$$$, which means that the height of the histogram at this index $$$(r-x+1)$$$ after we have updated the entire segment of 1s is $$$x$$$, so we update $$$hist[x]$$$ accordingly.

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I laughed out when I saw the code with language C++ for "1428E — Carrots for Rabbits". The Chinese characters in the beginning reminded me how popular the Chinese song was in the world some time ago.

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

Another(probably incorrect) solution for G.

Let $$$dp[mask][sum]$$$ be the answer for the problem when we are allowed to use only positions from $$$mask$$$ (e.g., if $$$mask = 100101_2$$$, our numbers can contain non-zero digits on positions $$$1, 100, 100000$$$).

Transition for this $$$dp$$$: $$$dp[mask][sum] ← dp[{mask} \oplus {2^{pos}}][sum - l \cdot 10^{pos}]$$$, where $$$l$$$ is the sum of digits, we put at position $$$pos$$$. $$$l_{max} = min ( 9k, \lfloor {{sum} \over {10^{pos}}}\rfloor)$$$ is the maximum possible value of $$$l$$$. Let's iterate $$$l$$$ from $$$l_{max} - MAGIC$$$ to $$$l_{max}$$$.

This $$$dp$$$ takes $$$O(2^6 \cdot 6 \cdot n \cdot MAGIC)$$$ to calculate, so let's do meet-in-the-middle: calculate $$$dp_1$$$ for the lowest $$$3$$$ positions and $$$dp_2$$$ for the highest $$$3$$$ positions. Now it takes $$$O(2^3 \cdot 3 \cdot n \cdot MAGIC)$$$ to calculate.

Answer for $$$n$$$ is maximum of $$$dp_2[allPositions][i] + dp_1[allPositions][n - 10^3 \cdot i]$$$.

Total complexity is $$$O(2^3 \cdot 3 \cdot n \cdot MAGIC + q \cdot 10^3)$$$.

For some reason it passes for $$$MAGIC = 30$$$.

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

Someone please explain why simple binary search doesnt work for E? I ran Binary Search on the biggest size of carrot, and for each carrot, computed how many carrots it needs to be split so that largest piece cannot be larger than mid, and then split this carrot as evenly as possible. But this is not working.

The code is below:

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

    Got it, its just wrong. We may also consider example case $$$n = 2, k = 5$$$, $$$a = [20, 60]$$$ then there is no way to get all sizes less than a value x and number of pieces exactly 5.

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

Can anybody help me pls in problem E, I made a priority queue(max heap), and pop off the top element, and used binary search to divide that number such that it is just greater than the next lesser element. Now pushed all such divisions of this number and again used the max value and continued the process, till I get k numbers code -Submission to E problem

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

In 1428E, one of your test solution is probably wrong (in the 4th case my outcome is around 2*10^7 less then in the solution)

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

I love the hint part of the Editorial. Most of time I don't want to read the whole editorial to understand the details of the Solution. All I need is the key point which reminds me of the trick to solve this problem. I think it is a really nice round and editorial. Thank you guys.

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

that's a great tutorial,all tutorials should be written in this pattern..

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

My solution for problem F is very different and am proud of myself to proved it, coded it up, and got it accepted! I became surprise when I saw the solution of the author.

Here is my code: https://codeforces.com/contest/1428/submission/115365132.

Just a short explanation of my solution: Draw a table (on a paper), where rows are the index of strings, and each column (from 0 to n) shows the number of continuous ones if we end at index r (at row r). If you fill out the table on the paper, you'll see when we have a '0' or '1' in the string, how the values for each row changes, which highly depends on the values in the previous row.

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

    The solution runs in O(n log n) and uses segment tree + lazy propagation technique.