intrusiv's blog

By intrusiv, 11 months ago, In English

Hello, Codeforces! Or, as we like to say in Romania: Dacă voi nu mă vreți, eu vă vreu, Codeforces!

I am glad to finally invite you to participate in Codeforces Round 915 (Div. 2), which will start on Dec/16/2023 17:35 (Moscow time). You will be given 6 problems and 2 hours to solve them.

The problems were supposed to be authored and prepared by valeriu, but in reality they were by tibinyte.

I would like to thank:

  • Say_my_name for LGM testing

Scoring Distribution: 500-1000-1500-2000-2250-2250

The problemsetters wish you good luck & have fun :)

Editorial is available here.

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

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

As a newbie tester, I enjoyed solving problems authored by a fellow newbie.

»
11 months ago, # |
  Vote: I like it -36 Vote: I do not like it
»
11 months ago, # |
  Vote: I like it +24 Vote: I do not like it

what was your contri in the round

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

Thank you sir intrusiv for teaching us what recherché means.

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

what's TBD ?

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

As a native, wtf does recherché mean?

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

    High quality, sophisticated.

    Example: The recherché mustard in your profile picture is arguably the best you can get on the romanian market.

»
11 months ago, # |
  Vote: I like it +15 Vote: I do not like it

As a tester, the round is very nice and I wish you all to solve everything you can and get a high rating!!!

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

Hope to become Expert in this round

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

hope to solve E on this round

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

Another newbie tester?

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

newbie problem setter 😱

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

If you don't want me, I want you, Codeforces!

»
11 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Why does it tell you a cheater when I hover your handle?

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

Hope I will be Legandary Grandmaster after this round !

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

How to become purple? i think i can solve E after the contest,but when i solve D ,100 minutes has been used ,so i dont have enough time

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

Excited for the round ?

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

Are tibinyte and valeriu the same person ??

»
11 months ago, # |
  Vote: I like it +25 Vote: I do not like it

cf contests >>> university exam prep

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

As a tester, I really liked the problems, and I hope that you will like them too

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

Does it rate?

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

Hope to be a Master this round!

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Hope to become pupil this time!!!

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

Hope to get to -39 rating after this round!!!!!

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

will it be rated?

»
11 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Geothermal will win Codeforces Round 915 (Div. 2)

»
11 months ago, # |
  Vote: I like it -8 Vote: I do not like it

is it rated?

»
11 months ago, # |
  Vote: I like it +16 Vote: I do not like it

STORY OF MY LIFE:


Day After Day, Inconsistency after incosistency,

Yet here I come, to solve another 3 problems and then get stuck at 4th, getting angry at problem setter for not explaining problem statement clearly, and in the end realising my own mistake and succumbing to my own dumbness and accepting that I am not made for this...

Till next time... ( Yet here I come, to solve another 3 .... )

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

Interesting score distribution; Looking forward to the round!

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

    What's exciting about this?

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

      E/F not really being much higher than D

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

win114514 ORZ

Possibly the highest gain from a Div. 2 contest — rank 1 (barring FST) with prior rating: 2099

Edit: Apparently not anymore.

»
11 months ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve D?

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

    $$$MEX(a_1, \ldots, a_i) = min(a_{i+1}, \ldots, a_n)$$$ for permutations, therefore sum of prefix mexs == sum of suffix mins. After this observation problem is pretty standard, iterating over all cyclic shifts and recalculating cost in some way

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

      Ahh yes you are right

      Thanks for your answer

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

      lmao, had the observation but had no idea how to do the rest...

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

      sevlll777 I approached it this way, please tell me if im wrong: I took some example permutations and got to a conclusion that the function for sum of cyclically shifted permutations is bitonic (increases, attains peak value and then decreases back) hence i tried to find that point using binary search but it gave WA on test 2.

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

        I think people mention that the result is not convex (could increase and decrease multiple time), so it probably won't work

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

          I just found a tc where it failed, my bad!

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

    The way I solved it was to look from the end rather than the beginning — then the sum of MEXs is related to the sum of suffix minimums.

    Then I split the problem into two sub-problems: if you cut the array at a certain index and then swap the two parts obtained you get a cyclic shift. I solved the problem separately on those two parts. I did it in a very convoluted way with monotonic stack + binary search on a bunch of arrays but there is surely a better way.

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

    Segment Trees worked for me. Basically, found all initial mexes, and then, did cyclic shift one element at a time, calculating the updated mexes. So what should happen when removing a[I] from the start of the array is considered. All mexes greater than a[I] will fall to a[I], also, adding a[I] to the end again simply adds n to the mexes. This is just done for all I from 0 to n-1

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

    Another approach: compute mex values for the array, and encode them using run-length-encoding: RLE = [(mex1, cnt_mex1), (mex2, cnt_mex2), ...]. This array will have increasing sequence of mex values. Then you can implement left cycle operation: it will remove some of mex values from the end of RLE, and add two more values: [(x, removed_length), (n, 1)]. Doing so you can also keep total sum of mexes in the RLE. It is possible to show that such implementation gives linear complexity: https://codeforces.net/contest/1905/submission/237518768

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

Why O(n) didn't work for C ?

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

    It's working. I think you're just wrong in your estimate of the asymptotic

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

      Yes i didn't knew appending string+= is faster than string = "something"+string :(

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

Is cost function in D convex by any chance? I guess it's really not, binary/ternary search shenanigans were my last hope anyway.

A and B were almost too easy, difficulty of C was sensible, then it's just pondering problem D for the rest of the remaining time.

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

why trying to kill nlogn in D?

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

cool contest, although it felt like you should try to solve both D&E, but have too little time, 2 hrs 15 min would be better

how to solve E can anybody please tell? i think i got it at the end but im not sure

  • »
    »
    11 months ago, # ^ |
    Rev. 4   Vote: I like it +31 Vote: I do not like it

    A $$$O(n)$$$ solution would be simulating the whole segment tree process, adding $$$v \times (2^\text{No. of leaves in left subtree} - 1) \times (2^\text{No. of leaves in right subtree} - 1)$$$ to the answer each time.

    By trying some smaller cases, you may observe that at each depth, the maximum difference of the range that the node represents are at most 1. So, for each depth, you can group the nodes into at most 2 sets, and then you can quickly calculate the contribution of each set of nodes to the answer (in $$$O(1)$$$ time complexity). The final time complexity would then be $$$O(log N)$$$.

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem A looks like John Conway's Game of Life.

»
11 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Segment trees are not ugly, segment trees are poetic.

»
11 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Probably overcomplicated B, but here's my thought process:

  1. It's always optimal to remove 2 leaf nodes at every stage.
  2. Naturally, we'd want to remove the farthest leaf nodes. In other words, we want to remove the diameter of the tree at each stage. Of course, finding out the diameter at each stage is tricky, but lucky for us, we don't have to print the choice of vertices.

Remembered about the Tree = edges of a diameter + forest representation from TheScrasse blog. Then, if you visualize the tree as forests hanging on the diameter, you can see that no matter how the diameter is computed, after each operation, the number of leaves reduces by 2. Hence, answer is $$$ceil(leaves/2)$$$.

Image

Submission

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

    great approach

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

    Do we need to remove diameter leaves? I think it's ok to choose any pair of leaves, i might be wrong thou. I'm just asking

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

      Counter Example

      If you do a random merge:

      • Collapse 8 and 9. Vertex 6 remains.
      • Collapse 6 and 7. Vertex 4 remains.
      • Collapse 4 and 5. Vertex 2 remains.
      • Collapse 2 and 3.

      But, it can be done in $$$ceil(5/2) = 3$$$ steps. The catch here is to avoid creation of leaf nodes after merging, unless absolutely necessary (for example, when there's a single forest hanging on the diameter, except for this case, in all other cases, you can guarantee that if there are atleast 2 forest, leaf node counts will go down by 2).

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

      No, I think if you take any leaves at random, try taking adjacent leaves for Balanced BST

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

B?

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

    ceil(leaves/2)

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

      count the root too if it has one edge. (I usually never call a root a leaf).
      Ans --> ceil((single edge nodes)/2)

»
11 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Here is my screencast of solving all problems in the contest (HD will be available once YouTube completes processing)

I will also discuss how I solved all the problems in the post-contest discussion stream.

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

Do we needed tree/graph knowledge to solve B or do there was any other way to solve it.

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

    Not really, you only needed to know what is a tree and adjacency list representation of the graph.

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

How come the answer for B isn't just the ceiling of the number of leaves divided by 2?

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

    It is?

    Edit: I can't view your submission at the moment. But maybe you're calculating the number of leaves by DFS, which will disregard the root.

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

    if root has only one child you have to count it as a leaf.

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

    not only leaves, all the nodes connected by only one edge, that means, if the root is have only 1 edge, it will be counted too.

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

    that's the answer. You used "tree[v].size() == 0" to find leafs. it will be tree[v].size() == 1

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

      Ah I see! I made the mistake of treating this tree as directed. Thank you so much!

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

C >>> B for me can someone please explain how to solve c?

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

    I don't think my algorithm is good but here's how I did it.

    First, I extracted the lexicographically greatest subsequence(lgs) from the given string. Then after reversing the lgs is it sorted or not? If it's sorted then the answer can be found. If there is an answer then, I've replaced the sorted string with the given string in the original position. Finally, I've checked if the given string is now sorted or not and printed the ans.

    my submission

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

    lets say the largest subsequence is zzba in the first iteration,then in the second iteration will be zzb, because after one right shift it becomes azzb,so now we cant take 'a' in the largest subsequence, this observation is very useful in solving this problem

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

guys why was my code outputing 1 less than the answer in B

ll t[maxn];

void run(){ ll n; cin >> n; for(int i =0 ; i < n; i++) t[i] = 0; for(int i =0; i<n-1; i++){ ll v,u; cin >> u >> v; t[v]++; t[u]++; } sort(t,t+n); reverse(t,t+n); ll c = 0; for(int i = 0; i < n; i++){ if (t[i] == 1) c++; } cout << (c+1)/2 << nl; }

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

    nodes are numbered from 1 to N but you are iterating from 0 to N — 1 either iterate from 1 to N or decrement u and v by 1

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

      Thx, yeah I'm so maddd

      if it wasn't for this I would have solved to C

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

A strange distribution of complexity. A very simple C, and a complex D for such a C.

Anyway, if someone solve D, how?

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

    Sorry I don't think C is easy, it's hard.

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

      I think this is a trivial problem, just do what you are asked to do. According to clist it about *1300 problem

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

        for me I didn't know how to get the Lexicographically largest sub-sequence but if you know how to get it you can easily observe the answer

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

    You mean C is too simple? How? I do have no thought about it.

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

    let $$$mx_i$$$ be the highest index $$$j$$$ (0 based) such that $$$p_j \leq p_i$$$.

    Then the cost is $$$n^2 - \sum_{i=0}^{n-1} mx_i$$$.

    We can simulate cyclic shifting using a sum-segment tree that supports adding a number and assigning a value to a segment.

    See my code for more details: 237511939

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

    C (40+min) is harder to debug than D(20+min).... Because I misread it as substring lol.

    And I solve them using the same algorithm using the decreasing stack. For C it's to find a largest subseq, for D it's to find the min value on the right.

    For D, you can start with x x x x x x x 0 and then start to put numbers from left to the right. The mex of the new moved number is the min(moved number). Using a decreasing stack can maintain the count simply.

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

Hoping to become Pupil in this contest :)

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

How to solve C?!

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

    notice that the largest lexicographical subsequence after all the moves will get reversed (because it will be non increasing so doing the operation until it gets reversed is optima)

    so just reverse it and check if the string is sorted or no

    and the answer is (size of the subsequence) — (the frequency of the first element in it)

    you subtract the frequency of the first element because there's no need to shift the because the elements behind it will all come in front of it

    here's my submission

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

I confirmed with author that "sorted state" means "non-decreasing" close to the end...and i was trying to debug C for over an hour just because I output 0 instantly if the given array is non-increasing...

Shouldn't "sorted" be more clarified in statement?

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

has anyone tried dp on problem D? for two different cases: i < index[0] and i> index[0]?

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Operation "Problem A" Struggle Report

Hour 0: Entered the battlefield with confidence, assuming an easy victory.

Hour 2: Reality check. Explored different algorithmic approaches to tackle unexpected challenges.

Hour 5: Delved into online forums, particularly Stack Overflow, seeking insights from cryptic responses.

Hour 8: Consulted textbooks, tutorials, and documentation in a desperate quest for understanding, attempting to reshape the problem into familiar forms.

Hour 12: Embraced creative madness, resulting in a code resembling an abstract art piece – a chaotic masterpiece born from unconventional solutions.

Hour 15: Faced a low point but chose resilience. Rewrote code, refactored, and debugged tirelessly.

Hour 18: Pieced together fragments of wisdom, forming a makeshift strategy. The problem, once formidable, started yielding to relentless effort.

Hour 20: Eureka! A breakthrough moment! The culmination of struggle, frustration, and experimentation led to a working solution. Celebrated the hard-fought victory.

Verdict: The journey through the Problem A labyrinth was a relentless pursuit. From conventional to chaotic, desperate to creative, every avenue was explored. In the end, triumph emerged from the crucible of hardship. To fellow warriors: persevere, adapt, and conquer! #ProblemAStruggle #CodeWarriorPersistence

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

C is too hard for me. RIP my rating

try again next round

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

    same. Smh got WA on second pretest twice, wasted 2 hours on that problem

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

      by the way, any ideas why it fails? 237512765

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

        I don't know why it fails, but I tried with the test I found my solution failed with and it turned out yours failed too.

        1
        8
        aabbddcc
        

        The answer is 2, and your solution says 1.

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

For C, I don't get how "cyclic shifting the string to the right" works. Is $$$t$$$ a char or can $$$t$$$ be a subsequence? Where are the characters that are not selected in the subsequence? For example, zbca, is there an intermediate step of bzca after selecting our subsequence zca?

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

    The characters not selected in the subsequence remains at its position and you cyclicly shift only the choosen elements among their own indices without effecting other indices

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

    you make shifting to the right on the subsequence you pick which is the lexicographical maximum in each operation

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

Did "D" literally 10 seconds after the contest :").

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

    been there... wish I didn't search for that bottle of water.

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

AHHH Why can't my segment tree pass problem D

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

    It seems they intentionally failed segment tree solutions.

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

    Lazy Segment tree is too slow. You need to use stack to keep track of the sum of suffix minimums. It's possibly to remove element from this stack when sliding in O(log n) using binary search and some tricks (I did this, it passed as bin search is much faster than lazy segtree) but it turns out it isn't needed. Because the biggest suffix will always have 0 as minimum which doesn't contribute to the sum.

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

      My nlognlogn solution with lazy segtree + bsearch passed in C++ 20 somehow but not in C++ 17.

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

This is the 4th Div. 2 in a row I solve the first 3 problems, any advice to start solving D's ?

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

    Convert it into another problem. We want the n + (maximum possible sum of (minimum suffix array) over all possible arrays from shifting)

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

    Stuck at 3 problems as well. For me, if D is some math issue that I cannot solve even if I have 24h, then I will let it go. If it's something just related to the algorithm, I will spend more time to upsolve it after the contest. By shortening the solve time, I can sometimes finish D now.

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

can someone please explain how B is ceil(leaves/2)?

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

    You can take a path and compress it every move. Compressing a path removes 2 leaves.

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

      Actually when you have 3 leaves, you can at most remove 1 leaf in one operation.

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

    we select 2 leaves every operation

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

choking on B by thinking about diameter of the tree :v

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

    initial thought was same but then realised problem won't be that tough for B.

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

How to compare the results of two different cyclic shifts for D fast? All I know is force and pick the MAX.

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

You really couldn't come up with a name for problem F, could you?

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

does anyone use segment tree for problem D?

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

Just a heads up: Is it allowed to compress the code and execute it to make it difficult to hack? Example submission Last line is the obfuscated code: exec(decompress(b'\x1f\x8b\x08\x00s\xc2}e\x02\xff..')

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

    See codeforeces rule

    Rule 16
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any idea why this fails for C?

Also, todays ABC C and CF B are kinda same, there you remove nodes, here you remove paths of nodes.

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

    It fails on this test:

    1
    8
    aabbddcc
    

    The answer should be 2.

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

      Thanks a lot! It passed now.

      Man, I'm so sad. I got the solution for this problem and fully wrote the code when there were only 500 solves. And then spent the entire time trying to figure out the mistake but I couldn't. Another day of losing rating :(

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

        I'm sorry for you, I know how it is, it happened to me. But look at the good part: Div.3 in 3 days! You can get more rating there :)

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

        Same happen to me too

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

    Yes. I had the same thought during the contest! :p

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

Do this round was difficult ? for me it was difficult though.

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

Excellent problems!

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

I advise the authors to study what segment tree are, because they don’t know

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

ooops, maybe I never become pupil! only two solves!

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

How to solve C?

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

    Part 1 : Finding the lexicographically largest substring.

    Hint : If you iterate end to start and maintain a char (largest so far), and if current char is largest, include it.

    Part 2 : Note that only these characters (or a subset of them) are part of every move Hint : Every time the set reduces by exactly one character

    Part 3 : You observe that the set of characters selected in 1 will eventually be reversed.

    Part 4 : Can you construct a string where (step 3 is fulfilled)

    Part 5 : check if string is sorted.

    Nice Move ? : Intentionally left one edge case for you to solve.

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

      That true if I see now, in 6th test case, edge case is present and I might have caught that if I didn't check for sorted array before. :)

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

      I get it. I found that my output format is incorrect during the contest.

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

Can anyone tell me logic of Problem D

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

    Note — the answer depends on the last element, then the next smaller element left to it...and so on till it reaches 0.

    Shift the array such that 0 occurs at the 1st position,

    now ans[i] = ans[previous_smaller_position[i]] + array[i]*(i-previous_smaller_position[i]);

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

I got pretest passed for "A. Constructive Problems". Since my solution wasn't Accepted, does this imply that it was wrong? Please guide.

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

    It says Accepted to me

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

      I just checked and the verdict is Accepted. Thanks !

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

    during the contests there are certain tests which are not checked these are checked after the contest during system testing hence the tests during the contest are called pretests and on passing all the pretests you are shown pretest passed.

»
11 months ago, # |
  Vote: I like it +5 Vote: I do not like it

AC code

TLE code

How when I add this line get an AC?

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

someone explain me the proper logic behind B please

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

    in every operation you can choose u and v as leave nodes and compress them. so in every operation you can decrease total no. of leaves by 2 so if no. of leaves is even it will take leaves / 2 operations. if no. of leaves is odd it will take leavs / 2 + 1 operations. ans = (leaves + 1) / 2.

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

      ya..i get it..

      was just being dumb and thinking that only leaves attached to a single node could be grouped in pairs of two...didn't realize that all the leaves present could be grouped in two...

      every time i got an element grouped with more than 2 , I was calculating its ceil(connections/2)...my bad

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

Hello. There is an issue on the task C. During the contest, I had sent my code with c++20 and got TL. 237525118 But after the end of the cf I sent the same solution on c++17, and it was accepted.237531478

Pls do something with that.

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

    That sometimes does happen man.

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

    I think this has something to do with you using '+' operator to concatenate the strings, as it has higher time complexity. If you use push_back(), it will run smoothly. Submission

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

It appears that there is a discrepancy in the Problem C description. The task requires sorting a given string, but the sorting criteria are not explicitly defined. However, the jury's answer specifies that the output should be in non-decreasing order. This creates confusion because, for example, the input string dccbba is already sorted in non-ascending order, but the jury's expected output is 5. In contrast, the output could also be 0 since the string is already sorted. wdyt? intrusiv tibinyte valeriu

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

    The statement was meant to clearly represent non-descending order. We are sorry for the confusion. We will analyze further for further action.

    But, if we are to be pedantic, "sorted" then doesn't really mean anything, because if we so desperately need a criteria, we can choose any permutation to denote the actual order of the letters.

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

      Thank you for your reply. I grasp your point. Thanks again.

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

I have just upsolved problem C, for me it's easier than B.

Thank you guys for the great contest!

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

my first problem was accepted at 7th minute and no wrong submission. I got rating less than 700. but I checked the ranking there are so many contestant having less ranking than me and their submission time was more than 7min too but their rating is even higher than 900. Can anyone explain me what did I do wrong?

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

Can anyone please help me understand why changing the CPP Version is resulting in different behaviour with the same code.

https://codeforces.net/submissions/ma_da_fa_ka

I got ACCEPTED, TLE, RTE with different version of cpp compilers.

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

Problem D: We can use Binary lifting if the input array was not always a permutation of set $$$(0,1,2,..,n-1)$$$

Submission: Link

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

Has anyone solved question D using Python? I'm getting runtime issues on test 11 and I'm losing faith after checking the c++ solution and seeing it's very similar to mine.

the sumbission in question

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

Why is my D getting TLE ? I tried to optimise the inner loop by jumping to the next smaller element each time using a stack, it should not be N^2 ?

237525237

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

    You can try the following test case

    Test case generator in Python3
    Actual test case
    Explanation
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i hope tibinyte wins his battle with worse

The round was good and I'm happy that I broke my negative delta streak

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

I know i did stupid in finding the subseq. in contest in problem C :(, but am feeling good in solving it without any standard implementation..:)) here's my submission.. My Submission

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

It was my first Contest and was only able to solve first problem. Any suggestions for a newbie

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

    I've been solving problems everyday (did it for the past 62 days in a row) and am targeting 800-1400 rating problems

    I think it is good if you keep practicing, so work on what motivates you, try to be consistent and use some of your time to practice problems harder than what you are used to even if you need to see the editorial to understand them

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

I am newbie unable to find editorial for problems. Can you please tell me where to look for editorial for a particular problem???

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

    The editorial link is provided in the last line of the blog, but if you still cant see it, here is the link.