steven.novaryo's blog

Codeforces Round #831 (Div. 1 + Div. 2, based on COMPFEST 14 Final)
By steven.novaryo, history, 2 years ago, In English

logo

Halo, Codeforces! 🥰🥰🥰🥰

COMPFEST 14 is happy to invite you to participate in Codeforces Round 831 (Div. 1 + Div. 2) on Oct/29/2022 12:10 (Moscow time). Note the unusual time of the round. The round will be rated for everyone. You will be given 2 hours and 45 minutes to solve 9 problems.

The problems are written by NeoZap, Nyse, Pyqe, and steven.novaryo.

Scoring distribution: 500 — 1000 — 1500 — 1750 — 2000 — 2500 — 2750 — 3000 — 3500

We would like to thank:

COMPFEST itself is an annual event hosted by Universitas Indonesia. It is the largest student-run IT event in Indonesia and competitive programming contest is one of the competitions hosted.

We hope you will enjoy and have fun in the contest. Semoga beruntung dan selamat bersenang-senang!! 💪💪🔥🔥

Edit: round was delayed by 5 mins due to delays of onsite contest.

UPD: contest is over!

Congratulations to our winners!

  1. jiangly
  2. heno239
  3. maroonrk
  4. never_giveup
  5. Isonan
  6. ksun48
  7. Um_nik
  8. hank55663
  9. ugly2333
  10. Vercingetorix

We will try to post the editorials as soon as possible. Please stay tuned!

UPD 2 : Editorial

We are very sorry for the late editorial. We did not anticipate the workload of maintaining an onsite contest, especially since this is the first onsite contest held by our university in three years. We will use this experience to learn and improve our preparation next time.

Finally, we are delighted that the contest ran very well and that many of the contestants are enjoying the contest.

See you next year! 🥰🥰

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

Comments Comments (207)
| Write comment?
»
2 years ago, # |
  Vote: I like it +80 Vote: I do not like it

minum susu gaming

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it first time 2 hours and 45 minutes long contest?

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Very excited to participate

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

Note unusual timing

→ Reply
»
2 years ago, # |
  Vote: I like it +30 Vote: I do not like it

As a tester, this is the first div1 of errorgorn as the coordinator.orzorzorz.

→ Reply
»
2 years ago, # |
  Vote: I like it +74 Vote: I do not like it

Seems that the contest coincides with CSP (an important contest in China in which almost all high-school students doing OI have to participate). Many Chinese participants aren't able to participate in this contest ... /sad

Is a rescheduling possible?

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

    I know about it already. But this contest is based on COMPFEST 14, the only possible way to avoid the conflict is to reschedule it after ABC (clashing with ABC would have more complaints), but by then the contestants of the onsite contest would have gone home and would have access to internet which is obviously not ideal.

    Therefore, it is impossible to reschedule due to these constraints.

    → Reply
»
2 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Unusual time.

What does rama_pang for drinking milk; mean?

→ Reply
»
2 years ago, # |
  Vote: I like it +56 Vote: I do not like it

As a tester, problems are good and I recommend participating

→ Reply
»
2 years ago, # |
  Vote: I like it -31 Vote: I do not like it

However, the contest time conflicts with csp-2022 senior. Please change another time!

→ Reply
»
2 years ago, # |
← Rev. 5   Vote: I like it +4 Vote: I do not like it

Note unusual timing

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it -43 Vote: I do not like it
Every Codeforces user can relate with this
→ Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it +12 Vote: I do not like it

I hope that problem statements should be short as there are 9 problems, so one can go through it easily

→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

As it will be my first contest,I hope i can solve 1 or 2 questions.

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

Yay! I can't wait to participate in this mirror contest! I didn't manage to get into the finals of the official COMPFEST 14, but I'm glad I can join this rated mirror contest!

→ Reply
»
2 years ago, # |
  Vote: I like it +32 Vote: I do not like it

As a tester, I think the problems are very interesting, and I hope you enjoy them too!

→ Reply
»
2 years ago, # |
  Vote: I like it +33 Vote: I do not like it

As a tester, I hope you all enjoy the problems and get positive deltas!

And also, Note the unusual time again. It will be 2 hours and 45 minutes to solve them!

→ Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

It's a pity that I can't participate in this contest because I participated in CSP-S, but I will definitely come to look the problems after the contest.

And I am looking forward to the problems of this contest, hoping to surprise me.

→ Reply
»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

nice emojii   ..!

→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Keren

→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

wow 9 problems and 2 hours and 45 minute. This is first time for me

→ Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Good Luck!!

→ Reply
»
2 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Postponed by 5min

→ Reply
»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

delays 5 min to drink milk...

→ Reply
»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Is it just me or site is crashing for everyone?

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

C is way more difficult than D and E

→ Reply
»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Fast forces :(

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone know what is pretest 6 in E? This contest is so much WA-in-pretests...

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    I had multiple different brain-fade solutions in E, and each of them gave WA 6, so likely it's just a normal case catching many of those WAs. The correct solution is to take the max height you can, or allow your children to take the max height they can, and so on.

    Example: if you have a tree 

    9
1 2 3 3 5 6 1 8

    the answer is $$$7$$$, because you can assign

    $$$a = [8, 5, 4, 9, 3, 2, 1, 7, 6]$$$ and remove them in the order $$$[7, 6, 5, 4, 3, 2, 9, 8, 1]$$$.

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

      Oh my god that's literally an one-sentence answer that I've been trying to come up for almost two hours! Thank you! I've got to the part where I thought of the "depth or width" stuff, but I didn't find the general formula for it.

      → Reply
»
2 years ago, # |
  Vote: I like it +162 Vote: I do not like it

Thanks for the round! All problems up to G are pretty nice (haven't read further).

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

got back to specialist!!

→ Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it +30 Vote: I do not like it

Thanks for the great round! How to solve F?

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

How to do E ?

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

    Since you can only remove leaf node, consider the vertices in topo-sorted order. You have two option: 1. continue the sequence from some child. 2. End the sequence here.

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

    You can solve it with some kind of tree DP. At each vertex, you decide if you want to go further up the branch and if you want to stop at the vertex and merge the longest branches of the child nodes.

    The explanation seems a bit abstract, so I upload 178381518 together.

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

    Solution for E:

    Let $$$dp[i]$$$ be the answer to subtree i.

    Consider in two cases：

    Case 1:node i is not in the answer.In this case,we can easily get:$$$dp[i]=\Sigma dp[j]$$$,$$$j$$$ is son of $$$i$$$.

    Case 2:node i is in the answer.Through observation, the answer must be a chain.

    In general,$$$dp[i]=max(\Sigma dp[j],depth[i]-max(depth[k])+1)$$$,$$$j$$$ is son of $$$i$$$,$$$k$$$ is descendant of $$$i$$$.

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

      Can you please elaborate, maybe some proof or insights?

      How does you get $$$dp[i] =\Sigma dp[j]$$$ in the first case and why the answer in the second case is the chain?

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

        Case1:

        You only need to prove the following process is the optimal:first,take all the nodes of subtree $$$son[i][1]$$$.Then,take all the nodes of subtree $$$son[i][2],son[i][3],...$$$

        Hint:use proof by contradiction.

        Case2:

        You need to notice:

        • In the sequence,the position of node $$$i$$$ is always greater than its descendants.

        • In the sequence,the value of node $$$i$$$ is always not greater than its descendants.

        So if node $$$i$$$ is in the answer,all numbers in the subsequence must be equal,which must be a chain.

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

      how are we deciding the permutation array a?

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

        Bro did you get how it's chosen ?

        Why isn't answer for the first case Not 6 ?

        → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    for each node calculate (a, b) where a is LIS endint at this node and b is LIS not ending at this node (considering this node's subtree)

    transition for a is max of childrens' a +1

    transition for b is sum of all childrens'(max of a or b)

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

    Consider painting each node with black or white.

    • If you paint node $$$x$$$ with black, then its score will be the maximum point among its children plus $$$1$$$.

    • If you paint node $$$x$$$ with white, then its score will be the sum of all its children.

    The answer will be max(black(1), white(1)).

    → Reply
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

how to solve problem C??

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

    Use this test case:

    1
6
2 3 12 25 27 28

    Expected output: 36

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

      36 still , got WA :'(

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

        You are not considering placing small in middle

        1
3
27 19 6

        Expected output: 34

        Your output: 29

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

          ahh , yes , thats it :( what is the approach actually ?

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

            got it only considered higheset ones in middele , but shold have considered lowest ones also , so dumb I am :)

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

    Video Solution for Problem C

    Hint:
    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

do you do dp for E? I can't figure out the transition in time ;-;

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

    Yeap, dp[i] = max(depth[i], sum_of_all(dp[children])

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

    yes, transitions are pretty simple

    dp(i, 1) = max(dp(u, 1) + 1), over all child u if i

    dp(i, 0) += max(dp(u, 1), dp(u, 0) for all child u of i

    i, 1 -> if we include i as next next element of longest subsequence

    i, 0 -> if we exclude i and only take its children in longest common subsequence

    base case is as following dp[leaves][0] = 0

    dp[leaves][1] = 1

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

      thanks! i had the same approach but the excluded one seems a bit counter-intuitive for me

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

        I just thought it would be helpful to think this way but at the end dp(i, 1) just came out to be height of every node, still thinking which element I am putting on the back to increase length of longest nod-dec subsequence helped me visualize the solution better

        → Reply
»
2 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Pak Chanek I hate this name.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B?

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

    It's optimal to always place the block so that it's height is bigger or equal than width .

    Now placing the blocks in asc/desc order will be enough.

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

      How did you prove this? I proved it, but I doubt so many people would be able to prove it the way I did it. Maybe there is an easier way... or they just proved by AC

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
        ← Rev. 2   Vote: I like it +14 Vote: I do not like it

        Proof by picture:

        You want to maximise the green lines. So you place the blocks vertically. The length of the red and the blue line is the same. Not sorting the blocks will lead to blue being longer than red. A shorter length is not possible, by nature of $$$max(height_i)$$$ and $$$\sum width_i$$$.

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

          Nice. I guess this part would probably be obvious to all. In such an arrangement, the answer = max_height * sum_of_widths.

          What I found difficult to prove was why can't I rotate the longest (by height) block so that the max_height gets reduced, and hopefully the increase in total_width would by such that we end up with a better answer. Of course after rotation, the last block would conveniently be placed in between so that the blocks remain sorted by height.

          Again, I proved this algebraically but I believe there should be an easier proof.

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

            You don't need to sort the last block after laying it flat. Actually the blocks need not to be sorted. Having a highest block and the sizes to the left and the right of it non-increasing is sufficient. With this you can also proof your case of rotation simply by picture.

            → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1. Rotate the box such that x axis is aligned with minimum length side (Reason: Its perimeter cannot be minimised by overlap, so try to minimize the length)
    2. Sort the (length,breadth) of all pairs
    3. Calculate perimeter by excluding the overlap
    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    178390392 Could someone provide test for this?

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

    Rotate blocks in such a way that width of block be minimum. Then place them in ascending order of their hight and calculate perimeter.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what's your approach for D?

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

    Figuring out minimum number of cells without a card needed to carry a card from cell (1,1) to cell (n,m)

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

      Exactly, but I thought It would be (n + m — 3), After the contest, I realized only 2 were enough. Thanks for your comment. It helped me to rethink my solution!

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

        thanks bro. this comment was much helful for me .

        → Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Huinea

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

In F if we define with $$$M$$$ maximum frequence of some value in array and with $$$D$$$ number of distinct elements in array.

Is it correct to claim that all multisets with at least $$$M$$$ elements, and none of them larger than $$$D$$$ are valid?

And if yes, how to code it in less than O(N^3)?

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

    No. Consider frequency array of original one is [3,1,1,3]. M=3, D=4. But we cant make sizes of sets to be [4,3,1].

    → Reply
»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Is this approach for F correct — Count all partitions such that largest size is less than or equal to number of distinct numbers and number of partitions is >= maximum occurrences of a number.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I liked sample test cases, they were pretty good : )

→ Reply
»
2 years ago, # |
  Vote: I like it +33 Vote: I do not like it

This was a nice round! A-D felt really logical and required very little to none background knowledge. Was already tired and satisfied so did not really give too much into E but seems like a cool problem as well. Will try to solve later.

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

Solution for E:

Let $$$dp[i]$$$ be the answer to subtree i.

Consider in two cases：

Case 1:node i is not in the answer.In this case,we can easily get:$$$dp[i]=\Sigma dp[j]$$$,$$$j$$$ is son of $$$i$$$.

Case 2:node i is in the answer.Through observation, the answer must be a chain.

In general,$$$dp[i]=max(\Sigma dp[j],depth[i]-max(depth[k])+1)$$$,$$$j$$$ is son of $$$i$$$,$$$k$$$ is descendant of $$$i$$$.

→ Reply
»
2 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Disgusting time limit in B

Python just can't handle reading so many lines without magic with acceleration

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

    Just don't code in python)

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

    Probably this counts as "magic with acceleration", but after getting TLE a couple of times with Python because of slow input (in earlier contests), I found that adding

    import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

    as the first two lines of the code helps a lot. You just add these two lines, no other changes required for inputting integers. With this I passed B in Python in 233 ms. I now have these lines standard in my Python template.

    Note that when inputting a string, you now need to do input().decode() instead of just input().

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

      What I actually cannot understand is that I first submitted with PyPy 3 64-bit and I got TLE. Then I decided to rewrite in C++. But after contest I submitted exactly the same code with Python 3 instead of PyPy and it ran in 500ms. I always thought PyPy should be faster.

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

        There are some blogs on Codeforces which discuss this in detail, search for "pypy vs python". Summary: for Python 3, actually Python is faster for input than PyPy. However, for some structures such as sets and dictionaries, PyPy is faster. So maybe it would work to submit on Python if you expect that the input takes the longest, and on PyPy if you expect the algorithm takes the longest.

        → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anybody with Problem C approach is it greedy or dp

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

    Not dp

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

      What's the idea for this

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

        we can always get > max — min by taking min in 2 sets, max in 3, the rest in 1. So it is impossible for elements 1 < 2 < 3 to exist, otherwise taking these three we get less than we could. So all elements of 2 are a prefix or suffix. Then think a little about how best to distribute the remaining ones and iterate over the length of the prefix/suffix

        → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the key observation of C?

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

    Suppose you have an array a of 3 elements 1,3,5. How you should rearrange these elements so that abs(a[0] — a[1]) + abs(a[1] — a[2]) becomes maximize?

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Sorry I dont quite understand. I will make 1,5,3 but how it helps?

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

        Yes This is the intuition. Suppose array a is now 1,3,4,5. So your plan is to re arrange it like 1,5,3 as it gives the best answer but you have to put 4 also on the bag but in which bag you should put it?? Obviously on middle bag, otherwise if we arrange it like (1,4) (5) (3). Then the person will choose 4,5,3 which will not give the best answer so we will arrange like (1),(5,4) (3) so best answer is (1-4) + (4-3).

        Now we will always look for a maximum element and two minimum elements or one minimum and two maximum elements. Why is that? Suppose a minimum element is min and a maximum element is max abs(max-min) will give better answer than (max-(min+1)).

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

    consider array: 1 2 10 12

    if you put 1 in bag 2 alone, the best answer is |1-2|+|1-12|. you see you can always subtract the number you want (in this case is 1) from the biggest number in the array (in this case it's 12) but the problem is nuber 2 because you can't get rid of it if you have chosen 1.

    but if you put 1 and 2 in bag 2, now you have the value |2-10|+|2-12| which is much better. so the answer is max(|a[i+1]-a[i]|+|a[n]-a[i]|) for all i.

    and you need to consider the case when the pivot is the biggest so max(|a[i]-a[i-1]|+|a[i]-a[1]|

    I hope you got it now.

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

      Why do we always take a consecutive segment from the largest/smallest element for bag2 ?

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

        so, it's important! first we make estimation of what value we can achieve. It's this: $$$>=$$$ than mx_el_of_a $$$-$$$ mn_el_of_a. Now, You Don't Give bags with stones to MINImizer-guy such that there exists w_from_bag1 $$$<=$$$ w_from_bag2 $$$<=$$$ w_from_bag2. I repeat DO NOT GIVE bags with such configuration of stones. There is no point in giving bags with such configuration of stones: you (maximizer-guy) can do not worse, already. Therefore bag2 is a prefix or a suffix. // this explanation was read by me from hacker:great_fortune, but he hasn't got your upvote, so I concluded to unravel a bit more. Was not able to come up with a solution for hours and hours. but. next time maxmin-problem will be percieved easier by me, alternative is not an option

        → Reply
»
2 years ago, # |
  Vote: I like it +198 Vote: I do not like it

Amazing problemset, big thanks to authors! G just blew my mind. F is also very nice, and H is one of the coolest data structure problems I have seen in a long time.

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

    I found COMPFEST problems to be nice every time , there was a compfest round (unrated) few months ago, that had great problems too

    → Reply
»
2 years ago, # |
  Vote: I like it +77 Vote: I do not like it

Really good problemset, I especially liked problem D, however I think problem E was easy for its position.

→ Reply
»
2 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Thanks to the round!

→ Reply
»
2 years ago, # |
  Vote: I like it +7 Vote: I do not like it

All problems were really good, but WA on pretest 2 for C was quite annoying.

→ Reply
»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

me(planning how can I quickly do problems so I could finally reach expert) Problem C: I am going to ruin this man's whole career

→ Reply
»
2 years ago, # |
  Vote: I like it +34 Vote: I do not like it

pretty nice set! (just E to F gap was really high)

→ Reply
»
2 years ago, # |
  Vote: I like it -10 Vote: I do not like it

H is standard dp on hld problem, refer to joi 2018 catdog

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

→ Reply
»
2 years ago, # |
  Vote: I like it +108 Vote: I do not like it

There used to be this scale, back in the days when I was smol. Something finally coming useful from childhood.

Helps in solving D
→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nostalgic! (◦'⌣'◦)/

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

    I also thought of this same scale when solving problem D lol.

    → Reply
»
2 years ago, # |
← Rev. 5   Vote: I like it +1 Vote: I do not like it

In problem D How does Case like gives no answer ?

2 2 4

3 4 2 1

my sequence of moves is just

  • move 3 to cell (1 , 2)

  • move 4 to cell (2 , 1)

  • move 4 to cell (2 , 2)

  • move 3 to cell (2 , 2)

  • move 2 to (1 , 2) and then to (2 , 2) and doing the same for 1 isn't that valid ?

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

    The statement says $$$3\le n,m$$$, so this kind of case doesn't exist.

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

      ok but why in most of the solutions they keep 4 cells empty and the just consider moving the card onto n * m — 4 cells

      why 4 , in my solution (Wrong one) i thought i can move cards onto any free cell if it exists or to some other cell that has its top card greater than the current card by 1

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

        Because if we keep $$$4$$$ cells empty we can move a new card to anywhere we want, so it's only nessesary to verify whether there's enough empty cells or not.

        And we can't put two cards on one cells at the same time. I guess this is the mistake of your approach.

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

        If you want to move a card from (1,1) then it is necessary to have 2 empty cells except (1,1) and (n,m). and if you want to move your card which is not on (1,1) it is necessary to have 1 empty cell except (1,1) and (n,m).

        → Reply
»
2 years ago, # |
  Vote: I like it +45 Vote: I do not like it

TLX teams always provide amazing problems!
Personally, My favorite point is that the samples have less information than usual.
I like F the best, even $$$O(n^3)$$$ (or slower) is cool and the speedup is also interesting!

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

    By the way, when I read problem E, I went to reading the sample explanation (because I accidentally confused myself thinking that we remax instead of remin), and then I just coded the solution without proving it (well, I kinda convinced myself that it is intuitively obvious, but point stands)

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

    what is the speedup from N^3?

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

      Hi, I'd like to share my code, maybe you'll find it helpful :D

      178435674 $$$O(n^2 \log n)$$$

      As I know there also exists $$$O(n^{5/2})$$$ solution, could someone share it?

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

        Thanks! that cleared it up for me

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

        Can you explain your solution, please?

        → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I submitted a solution for problem E in python using dfs and was getting runtime error on test 3, after some investigation got to know that it was giving recursion limit error in a normal dfs of 10^5 nodes. Below is my code to it, if anyone can explain me how to solve this using recursion then it would be great.

Thanks

Problem : 1740E - Hanging Hearts

Solution : 178403205

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

    I'm lazy to provide an actual code but one possible solution is using threads. You can set an increased default stack size when you make a new thread.

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

Why result is 63 in testcase2 of propblem C ???

4
17 8 19 45
63
→ Reply
»
2 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Impressive gap between E and F.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Guys can someone pls explain problem E (hanging hearts) to me pls? I have read many of the solutions but have understood none of them. Also I am very salty because I only solved problem D after the contest after I realised that I added an extra "+1" for no reason that gave me WA.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone provide a testcase for this? 178391526

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

    1

    3 3 6

    1 2 3 4 5 6

    this case must give "YA".

    I think this is the worst case in the problem.

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

      Can you elaborate on how is this possible?

      At start there are $$$7$$$ vacant cells $$$(3 \times 3 - 2 = 7)$$$

      When $$$1,2,3,4,5$$$ are removed from the stack then there are $$$ 7 - 5 = 2$$$ vacant cells. But the minimum free cells required to move from $$$(1,1) \rightarrow (n,m)$$$ is equal to $$$3$$$ $$$[(n+m)-(1+1)-1 = n+m-3]$$$.

      So how is this testcase giving YES?

      UPD: Just realized I need only $$$2$$$ vacant cells to move one card from $$$(1,1) \rightarrow (n,m)$$$. Updated it in the program and got AC. Thanks!

      → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it -35 Vote: I do not like it

I was just glancing at problem I because I was late but still wanted to read the problems. The problem seemed interesting, and the (seemingly obvious?) properties I observed is that the answer is $$$-1$$$ when we cannot construct $$$S \bmod m$$$ (The initial sum of all elements modulo $$$m$$$) with the format of $$$kt \bmod m$$$ ($$$t$$$ being any arbitrary integer), and otherwise the answer is never $$$-1$$$ (I may be wrong on the latter point). Then I thought there may be some invariant property conserved when we follow the optimal method. My expectation of the time complexity is $$$O(nm \log n)$$$ or a bit slower. For anyone who got their hands on problem I — what was your approach so far?

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

    1

    3 3 6

    1 2 3 4 5 6

    this case must give "YA".

    I think this is the worst case in the problem.

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

    I didn't have time to think about the problem, but there is a stronger condition that is maintained: let $$$g = \mathrm{gcd}(n, k)$$$. Let $$$S_i$$$ be the sum of all elements with indices equal to $$$i$$$ modulo $$$g$$$. Then all $$$S_i$$$ are increased or decreased by $$$k/g$$$ after every move, and hence these sums must have the same remainder modulo $$$m$$$, and this remainder must be divisible by $$$\mathrm{gcd}(m, k/g)$$$. I have a feeling that this is probably sufficient

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

      Well this is sufficient because we can first make all these sums equal to 0 by doing random increases, then we can transfer $$$1$$$ by $$$k$$$ positions in either direction using and increase and a decrease, therefore we can transfer $$$1$$$ by $$$g$$$ positions, hence we can transfer all nonzeros into one cell for each index remainder modulo $$$g$$$. Don't know anything about the optimality, though

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone give me a small testcase for which my submission would fail? I'm not able to understand where I'm going wrong.

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

For problem C:

4

17 8 19 45

What I did was put the maximum in the first bag and the min in the second bag. Or put the min in the first and the max in the second. And take the maximum of them.

Bag 1={45}, Bag 2={8}, Bag 3={17,19} => Ans: 46

Bag 1={8}, Bag 2={45}, Bag 3={17,19} => Ans: 63

So the answer is 63. Can someone tell me where am I wrong?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell what is the correct approach for #C? I can't figure out!

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

    consider array: 1 2 10 12

    if you put 1 in bag 2 alone, the best answer is |1-2|+|1-12|. you see you can always subtract the number you want (in this case is 1) from the biggest number in the array (in this case it's 12) but the problem is nuber 2 because you can't get rid of it if you have chosen 1.

    but if you put 1 and 2 in bag 2, now you have the value |2-10|+|2-12| which is much better. so the answer is max(|a[i+1]-a[i]|+|a[n]-a[i]|) for all i.

    and you need to consider the case when the pivot is the biggest so max(|a[i]-a[i-1]|+|a[i]-a[1]|

    I hope you got it now.

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

    Consider the sorted array. Since we have to distribute to 3 bags. We can always find 3 consecutive segments like below: ...(elements in w1)(elements in w3)( elements in w2)...

    So, the second person, to minimize the result. No matter what values he choose, he has to choose them in consecutive segments. Otherwise, the result will increase.

    We now greedy choose first segment [0]. And therefore, the second person will has only 1 choice is to choose last element in w3 and first element in w2.

    Just draw it on paper, you will get my point.

    Now, we also have another option is greedy choose last segment [n-1]. consider segment like ...(w2)(w3)(w1) (just reverse above) Also draw it on paper, you will see he has only 1 option : last element in w2 and first element in w3.

    w2 has to be in rightmost or left most to maximize the result

    → Reply
»
2 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Seems that there's a big gap between E and F

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

    sry i thought F, G would be about 300 lower than they are

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you please explain problem D ❤️

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

    If the number of non-blank cell is lower than or equal to $$$n * m - 4$$$ (if don't have the rule 2(You cannot move a card onto cell $$$(1, 1)$$$) and 3(You cannot move a card from cell $$$(n, m)$$$), it will be $$$n * m - 2$$$), it can be proved that we can move any card on any cell to any cell without passing $$$(1, 1)$$$ and $$$(n, m)$$$.

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

Hey, I tried solving problem E without using dp and it managed to pass all the tests but I'm not sure if it is the correct solution or not. If someone could hack it that would be great. If it is indeed right can someone prove why it works?. This what I came up with, instead of randomly going to a subtree of a node I visited the subtree with the deepest nodes first and assign values to a node when we have visited all nodes in its subtree. Then I just stored the subtree min in the same order and calculated the LNDS.

Thanks in advance.

178446226

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it -19 Vote: I do not like it

E

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

    It's just your alt account isn't it? You can't fool anyone with this lame excuse

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

    lol kid do you think we are fools out here?This is not your home or kindergarten school where you make fool of your parents and friends.The friend that you are talking about is actually your main account and things occurred like this according to my analysis skill:

    1.You submitted D and got WA in your main account

    2.Then you thought that ,"Let me just keep submitting in alt as long as I don't get AC and save point deduction from main account."

    3.In the end you submitted the AC solution again but this time in your main account

    I would ask MikeMirzayanov to skip solutions from both of your accounts

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In the C problem, why was I getting it wrong can someone explain? I was talking about the lowest in one bag(including repeats), and the biggest in another bag(including repetitions).and the rest others in one bag, and then I was iterating with all the elements with the equation from that bag to get the min by thinking both a[0] and an [n-1] in the W1 bag and W2 bag. at last, I choose the max one from both of them. My submission

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

    Consider the test case

    1

    4

    1 12 88 100

    Your code's output is 111.

    You are considering this configuration as optimal:{1}, {100}, {12,88} =|100-1|+|100-88|=99+12=111.

    But consider this configuration: {88},{1,12},{100}

    Here

    option1=|1-88|+|1-100| =87+99=186.

    option2=|12-88|+|12-100|=76+88=164.

    Therefore, the answer should be 164.

    → Reply
»
2 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Editorials please :)

→ Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Contest is very good, Editorial please :-)

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem C, if we consider array [1,2,3,4,5,6] and put balls with weights 1 and 2 in bag2, balls with weights 3 and 4 in bag1 and balls with weights 5 and 6 in bag3 answer should be 12 but the correct answer is 6. Anyone please explain. Thanks.

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

    • Because in this case that person (the person who want to make you loose in problem D ) will chose 2 from bag 2, 3 from bag 1 and 5 from bag 3, so the result is 4.

    • one of the ways to the best answer is to put 1 in bag 2, 2 3 4 5 in bag 1 and 6 in bag 3.

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

SecondThread when is the screencast coming?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain me why I am getting Denial of Judgement verdict on problem D. submission https://codeforces.me/contest/1740/submission/178637268

→ Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

The contest was really helpful to me, I really made a good knowledge of it.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Codeforces Language Picker -- chrome extension to fix codeforces language picker.

→ Reply
»
2 years ago, # |
  Vote: I like it +14 Vote: I do not like it

I received an announcement for this past contest 9 minutes ago. Anyone else?

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

    Yep i did as well, it is probably because an update was made to the post (editorial is published)

    → Reply