Блог пользователя steven.novaryo

Автор steven.novaryo, история, 17 месяцев назад, По-английски

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! 🥰🥰

  • Проголосовать: нравится
  • +693
  • Проголосовать: не нравится

»
17 месяцев назад, # |
  Проголосовать: нравится +80 Проголосовать: не нравится

minum susu gaming

»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
17 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Very excited to participate

»
17 месяцев назад, # |
Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

Note unusual timing

»
17 месяцев назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

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

»
17 месяцев назад, # |
  Проголосовать: нравится +74 Проголосовать: не нравится

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?

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится +183 Проголосовать: не нравится

    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.

»
17 месяцев назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

Unusual time.

What does rama_pang for drinking milk; mean?

»
17 месяцев назад, # |
  Проголосовать: нравится +56 Проголосовать: не нравится

As a tester, problems are good and I recommend participating

»
17 месяцев назад, # |
  Проголосовать: нравится -31 Проголосовать: не нравится

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

»
17 месяцев назад, # |
Rev. 5   Проголосовать: нравится +4 Проголосовать: не нравится

Note unusual timing

»
17 месяцев назад, # |
Rev. 2   Проголосовать: нравится -43 Проголосовать: не нравится
Every Codeforces user can relate with this
»
17 месяцев назад, # |
Rev. 3   Проголосовать: нравится +12 Проголосовать: не нравится

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

»
17 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
17 месяцев назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

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!

»
17 месяцев назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

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

»
17 месяцев назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

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!

»
17 месяцев назад, # |
Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

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.

»
17 месяцев назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

nice emojii   ..!

»
17 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Keren

»
17 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
17 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Good Luck!!

»
17 месяцев назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Postponed by 5min

»
17 месяцев назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

delays 5 min to drink milk...

»
17 месяцев назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Is it just me or site is crashing for everyone?

»
17 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

C is way more difficult than D and E

»
17 месяцев назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Fast forces :(

»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    17 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    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]$$$.

    • »
      »
      »
      17 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
17 месяцев назад, # |
  Проголосовать: нравится +162 Проголосовать: не нравится

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

»
17 месяцев назад, # |
Rev. 3   Проголосовать: нравится +30 Проголосовать: не нравится

Thanks for the great round! How to solve F?

»
17 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

How to do E ?

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится

    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$$$.

    • »
      »
      »
      17 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        17 месяцев назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        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.

    • »
      »
      »
      17 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      how are we deciding the permutation array a?

  • »
    »
    17 месяцев назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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)

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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)).

»
17 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

how to solve problem C??

»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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

    • »
      »
      »
      17 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        17 месяцев назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        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

»
17 месяцев назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

Pak Chanek I hate this name.

»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve B?

  • »
    »
    17 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      17 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        17 месяцев назад, # ^ |
        Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

        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$$$.

        • »
          »
          »
          »
          »
          17 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            17 месяцев назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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.

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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
  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    178390392 Could someone provide test for this?

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

what's your approach for D?

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      17 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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!

      • »
        »
        »
        »
        17 месяцев назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        thanks bro. this comment was much helful for me .

»
17 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Huinea

»
17 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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)?

»
17 месяцев назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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.

»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
17 месяцев назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

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.

»
17 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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$$$.

»
17 месяцев назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

Disgusting time limit in B

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

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Just don't code in python)

  • »
    »
    17 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    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().

    • »
      »
      »
      17 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        17 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Anybody with Problem C approach is it greedy or dp

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Not dp

    • »
      »
      »
      17 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      What's the idea for this

      • »
        »
        »
        »
        17 месяцев назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        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

»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

what is the key observation of C?

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    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?

    • »
      »
      »
      17 месяцев назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

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

      • »
        »
        »
        »
        17 месяцев назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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)).

  • »
    »
    17 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    • »
      »
      »
      17 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        17 месяцев назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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

»
17 месяцев назад, # |
  Проголосовать: нравится +198 Проголосовать: не нравится

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.

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

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

»
17 месяцев назад, # |
  Проголосовать: нравится +77 Проголосовать: не нравится

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

»
17 месяцев назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Thanks to the round!

»
17 месяцев назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

»
17 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
17 месяцев назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

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

»
17 месяцев назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

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

»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve F?

»
17 месяцев назад, # |
  Проголосовать: нравится +108 Проголосовать: не нравится

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

Helps in solving D
»
17 месяцев назад, # |
Rev. 5   Проголосовать: нравится +1 Проголосовать: не нравится

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 ?

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

    • »
      »
      »
      17 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        17 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

      • »
        »
        »
        »
        17 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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).

»
17 месяцев назад, # |
  Проголосовать: нравится +45 Проголосовать: не нравится

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!

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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)

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    what is the speedup from N^3?

    • »
      »
      »
      17 месяцев назад, # ^ |
      Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится

      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?

»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    17 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
17 месяцев назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Impressive gap between E and F.

»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone provide a testcase for this? 178391526

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

    • »
      »
      »
      17 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      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!

»
17 месяцев назад, # |
Rev. 2   Проголосовать: нравится -35 Проголосовать: не нравится

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?

  • »
    »
    17 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      17 месяцев назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      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

»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
17 месяцев назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

  • »
    »
    17 месяцев назад, # ^ |
    Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

    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

»
17 месяцев назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Could you please explain problem D ❤️

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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)$$$.

»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Какой рейтинг у задач?

»
17 месяцев назад, # |
Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

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

»
17 месяцев назад, # |
Rev. 2   Проголосовать: нравится -19 Проголосовать: не нравится

E

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

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

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    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

»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
17 месяцев назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Editorials please :)

»
17 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Contest is very good, Editorial please :-)

»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    • 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.

»
17 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

SecondThread when is the screencast coming?

»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
17 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
17 месяцев назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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