Getaway_Car's blog

By Getaway_Car, 3 weeks ago, In English

Thank you for participating in the round!

Fun facts
Rate this round

2277A - Subset Selecting

Author: Getaway_Car

Hints
Tutorial
Code
Rate the problem

2277B - Sequence Decreasing

Author: Getaway_Car

Hints
Tutorial
Code
Rate the problem

2277C - Edge Addeleting

Author: _O_v_O_

Hints
Tutorial
Code
Rate the problem

2277D1 - Number Operating (Easy Version)

Author: Getaway_Car

Hints
Tutorial
Code
Rate the problem

2277D2 - Number Operating (Hard Version)

Author: Getaway_Car

We'd like to thank RockyYue for providing an optimized solution.

Hints
Tutorial
Code
Rate the problem

2277E - Tree Guessing

Author: _O_v_O_

Hints
Tutorial
Code
Rate the problem

2277F - Token Re-Moving

Author: Getaway_Car

Hints
Tutorial
Code
Rate the problem
  • Vote: I like it
  • +51
  • Vote: I do not like it

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

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

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

if D1 was b then it is not fun fact but horror fact :p

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

I feel like d1 was a bit easier compared to most other div2 d's. Nice round tho!

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

Why is problem E and F easier than problem D

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

D2 is much harder than E...

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

I wish I could participate but gotta study bio for my bio exams in 2 weeks :/

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

I don't like trees, so I skipped C and went straight to D, only to get stuck there :(

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

I had studied but still able to solve till C...!!

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

fast editorial!

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

A is damn hard...

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

speedblitz edu :O

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

fast editorial!!

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

in q c. i did by using dsu path compression as i dont know how to do binary uplifting. we can obervse that any node say x then if x and n have lca other than 1 it can make path longer . so if their lca is not 1 its useful to us.so i use dsu path compression to store par of everyone either its 1 or other (i stored a path from 1 to n in a set and now i stored everyone par as 1 of member of this set) now. for every vertex that we are given to explore. i just see if the par is not 1. then just used that formula . 1+depth(n)-2*depth(common lca)+depth(j).its not the best approach but i am happy first time i solved q. c in contest.

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

    There exists an easier method as well using DFS.

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

could anyone tell me whats wrong with my solution for A 395842509

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

    I dealed with your submission and found that it gives WA for the following :

    Test Case

    Because that you are missing to set your mp[i] variable to 0 when it is insufficient to form a set with max element i.

    Solution : Just write mp[i] = 0 before the last if statement (req > 0 part) in your nested loop. You can check my submissions also.

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

Problem B is confusing. First the problem says, "3. choose one element of this subarray and remove it from b, without changing the order of the remaining elements."

And then in the 4-th testcase, 5 // 2 1 1 0 3 the output is 5. The tutorial assumes that we only can reduce the elements and skip the removal part! What's going on?

NOTE: I can be wrong, please explain your point simply! Tnx!

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

    We can show that 5 works here; by choosing entire array, our first operation can be solely the final element which makes the array 2110 (since 3 is removed), from there we can choose [1,3] at whcih the array can be 000 since it goes 2110->1000->000. I think this is how it might go?

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

      According to the output requirements: "output a single integer — the maximum length of a good subsequence of a, or 0 if no such subsequence exists", shouldn't the ans be 3 instead? Then to all those people who solved it, how did they knew the question has errors?

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

        No the answer is 5. Maximum length is number of elements in the longest subsequences that is good, NOT the largest value of a good subsequence. The question did not have error(s).

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

    They haven't specified the size of the subarray we have to choose in the qs. So since there is already a 0 present in the subarray, we can just take our "good" subsequence as 2 1 1 0 3 and then perform 4 ops on each of the individual elements.

    Take [2] for instance, after 1 op it becomes [1] but we have to remove one element also so it becomes []. Do this for all the other ai > 0. so our final array is just [0]

    We can just extend this idea to the case where we don't have a 0 at all in the array. In general if theres at least one element <= n — 1, we can make the whole array "good".

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

    I mean, one could only reduce an array's size after removing some elements from it?

    For the testcase, You can select the full array as a sub-sequence and test if it's good or not.

    [2 1 1 0 3] For making this good, select the [2 1 1] as a subarray and do the subtractions, becomes: [1 0 0] and remove an element, let's remove 1 becomes: [0 0] + [0 3] = [0 0 0 3]

    Then select [3] as a subarray, decrement to get [2] and remove an element to get []

    [0 0 0] + [] = [0 0 0] As you can see, we have boiled the array down to a non-empty array consisting purely of zeros. So this subsequence is good and because it is the largest subsequence, it is also the answer.

    To make the process easy, you could start by asking:

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

    Take the whole array, reduce it to good array and read the problem statement again. Thank you.

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

    The question is weather this array can be transformed into an array consisting of only zeros or not even if after removing everything and only 1 zero this means that the size of current array is the answer in the example you showed we can remove every element and leave the 0 and that would mean we made it from this array to an array with '0' so this array of size 5 is valid, sorry if i don't make sense you should re-read the problem that might help

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

I am too weak :(

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

My solution discussion stream for ABCD1E

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

My Question to the people who were able to do D1:

How can you be sure during the contest that these two ways were sufficient, and there is no other way of 0 -> (operations) -> n, which gives a more optimal answer ?

Based on my prior experiences, whenever I find two ways of doing a thing and drawing cases show that for some cases first way gives correct answer and for some cases the second way, the general tendency of mine is to take the best of these two ways just to get a WA on test 2. Unfortunately, I did not even try minimising both definitions of f(n) i wrote, during the contest, and later found out that it was indeed the optimal solution.

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

    Wait that was intended, i took a completely different path than yours that requried way more guessing. My subimission:395865736

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

    If you observe f(i) from 1 to 30, you may guess it is correct

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

      Yes, I did something similar, do manual f(i) for i (1 to 32), the reason it's more optimal is because of the way exponents grow. you would never want to build 9 using 3 3s but by using 7 + 3.

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

in D1 i mistakenly read it as (where k is the number of type 2 operations you have performed before) so i just got stuck then i read F and i thought on it got a very long implementation solution started implementing but got time out.

»
3 weeks ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it
D1 alternate sol (much more complicated, slower, and uglier)
»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Such a cool round!

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

Does someone have a proof for why exactly is 1 type-2 operation optimal, as in it was natural to guess this. But is there a solid proof of why it is optimal.

Why can't something like (k + 2 + f(n — 2^k + 3)) be optimal.

Thank you

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

    If we perform a second type-2 operation immediately, we spend one extra move and increase our target from a to a+1.

    but instead, we can solve a+1 optimally and then subtract 1 at the end to reach a. So, f(a) <= f(a+1)+1 Adding a+1 to both sides gives

    (k+1)+f(a) <= (k+2)+f(a+1) This means doing extra subtractions upfront cannot give us a better answer. We can simply perform the necessary reset once and let f decide the best time to subtract later.

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

C is an awesome problem

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

From D1 editorial: "It is easy to show that performing fewer than k type-1 operations is never better."

I do not understand why. Can someone show this?

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

"It is easy to show that performing fewer than k type-1 operations is never better" -- from D1's editorial

Is there some clever way to see this? Intuitively, this feels right, but I'm not able to flesh it out

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

    I guess something like this would work:

    Suppose you want to find f(k). Let

    $$$2^p \leq k \lt 2^{p+1}.$$$

    Consider less than p consecutive applications (say, p-r) of Operation 1, followed by 1 Operation 2.

    The recursion in this case is:

    $$$p + 1 - r + f(k - (2^{p-r} - 2))$$$

    And with p consecutive applications, it is,

    $$$p + 1 + f(k - (2^p - 2))$$$

    We can probably prove the expression below is <= the expression above (might be easier to show for r = 1, and the result for general r would follow)

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

      The way I approached the problem is splitting the operations into blocks of operation 1, operation 2, operation 1 etc. It is then easy to see that the order of the blocks of operation 1 do not matter — only their size does. Thus we can rearrange them to prioritise the block with highest number of operation 1 first. Similarly, you can try to prove it is suboptimal to have 2 blocks with same number of operation 1.

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

I fked up but very interesting problems

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

is my life cooked a is cooked. how do u guys approach a :( i thought sprting wud do it, but realised it might skip a integer, as in that window of length k, u might have bigger nums, so use the smaller ones for assisstance but wtf that took time to get it helpppppppppp

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

I don't believe D2 is 2300-2400. I think at minimum it's 2800. Crazy to think, that something like that is considered pretty standart for lgms to implement.

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

Hi, why can’t I see other people’s submissions? It just shows “N/A.”

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

Damn this was so hard for me, didn't solve a single one TT

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

Proof for the recurrence in D:

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

Nice problems A-D. By the way, the "Bonus" solution with binary search gives $$$O(\log^2 V \log \log V + t \log V)$$$ time, because we need to binary search over a range of length $$$O(\log^2 V)$$$.

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

    you're right

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

      Is this normal? 395868142

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

      I want to practice more problems similar to CF 2277D1, where the core challenge is not implementing DP but discovering the correct recurrence equation from the given operations.

      When I search for terms like recurrence relations or recurrence problems, I usually end up finding DP problems, where the state transition is already obvious. However, that's not the skill I'm trying to improve.

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

i felt b easier than a

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

cool round rly liked d1 & c(even tho came up with a solution for c after the contest) <3. first task was however annoyingly confusing imo.

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

D1 and D2 problem, my approach: https://codeforces.me/blog/entry/158156

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

F can also be solved by processing earlier vertices after later ones and keeping track of their contribution to other vertices: 396325336

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

Cool round & fast editorial :))) IMO: A is a bit harder than B (still, good thing D1 was not B). C was awesome.

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

Hey I stuck at D1 for an hour and a half.