Imakf's blog

Codeforces Round 906 (Div. 1, Div. 2)
By Imakf, history, 6 weeks ago, In English

Hello, Codeforces!

waaitg, Cocoly1990 and I are glad to invite you to Codeforces Round 906 (Div. 1) and Codeforces Round 906 (Div. 2), which will take place on Oct/28/2023 17:35 (Moscow time). In both divisions, you will be given 6 problems and 2 hours and 30 minutes to solve them all. Note that one of the tasks is split into two subtasks.

We would like to thank:

Score distribution:

Div. 2: $$$500$$$ — $$$750$$$ — $$$1250$$$ — $$$2000$$$ — $$$(1250 + 2500)$$$ — $$$3250$$$
Div. 1: $$$750$$$ — $$$1250$$$ — $$$(750 + 1500)$$$ — $$$2000$$$ — $$$3500$$$ — $$$3500$$$

As always, wish you all get a non-negative delta in this round!

UPD1: Editorial

UPD2: congratulations to the winners!

Winners and first solves
  • Vote: I like it
  • +544
  • Vote: I do not like it

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

fuka round!

→ Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it +291 Vote: I do not like it

As a writer, I think this Round is very interesting.(btw, Please give me contribution.)

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

As a tester, problems are very cool! ><

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

Hoping that it would be a great contest

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

I hope it will be great contest and get more points.

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

First Div1 contest for me! Hope that i can solve at least one problem!

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I am a newbie, could I take part in Div 2 and solve the easiest problem?

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

Contest timing clashes with El Clásico.

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +41 Vote: I do not like it

    El Classico timing clashes with Contest

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

As a player, I wanna be red.

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

i was forced to test

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

Thanks for the early Score distribution lol:)

→ Reply
»
6 weeks ago, # |
← Rev. 3   Vote: I like it +13 Vote: I do not like it

Chinese round at usual time. It's unusual, isn't it?

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

hope get positive rating delta

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can't wait to become blue

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

2 year contribution? Like you spent 2 years on this contest?

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    The contest was proposed more than 2 years ago, and one of the problems was accepted in another round from 2 years ago but ended up not being used.

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

      I wanted to ask how long do people make contests? LIke there are so many because they are not that hard to make or because there many people who want to make contests?

      → Reply
      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        Contests are not easy to make and require a lot of work, but there are many people who propose them. In fact, currently there is a long queue and you have to wait 1 year (for div2) and 3 months (for div1) to get a coordinator. Then, the preparation and testing phase is usually a few months long.

        → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

GusFring orz

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

Imakf round!

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

This round time clashes with IEEEXtreme (which happens once a year) and many contestants can't do both!

Is it possible to delay this round by one day?

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

    just do that round since its once a year, this is just another regular cf round

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I am new to this. Please advice a math book and algorithms book. I barely can solve even 1200 problems

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

    You don't need books, just pick a random problem and try to solve it. When you're stuck change problem or look editorial(read one statement and try to do left part yourself, if you couldn't, read one more, in the end code solution yourself). If you found anything you don't know in editorial just google it. cp-algorithmms and geeksforgeeks are good to learn topics.

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

    solved div2 AB feeling good

    → Reply
»
6 weeks ago, # |
  Vote: I like it -18 Vote: I do not like it

Is it rated?

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +21 Vote: I do not like it
    How will everyone get non negative delta if it was rated
    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
      ← Rev. 6   Vote: I like it +13 Vote: I do not like it

      I think you wanted to write: "How will everyone get non-negative delta if it was unrated" but it's possible to everyone get non-negative delta if it was unrated.

      If it was unrated everyone would get 0(which is non-negative) delta.

      → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Woah, i can see a lot of reds

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

i want rating!

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping for a lovely round!

→ Reply
»
6 weeks ago, # |
  Vote: I like it -78 Vote: I do not like it

Clashing with LeetCode Biweekly. Would skip this one.

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Codeforces round is always priority.

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it -65 Vote: I do not like it

      Nah bro, Codeforces round are always more on mathematical side and gets boring to me after I read problem statements. At one point, I was only doing CF, now when I went to Leetcode, I cant enjoy CF rounds anymore.

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

        CF contest bring heavy VSM, while Leetcode contests do not Doc.

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

          What is VSM?

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

            Violence, Speed, Momentum. In reference to his DrDisrespect profile pic

            → Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    leetcode clashes with cf*

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

Why do you schedule contests on the same day as IEEExtreme? T~T

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

    We check the CLIST calendar before scheduling contests, and there is no IEEExtreme there.

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Impossible wish: "you all get a non-negative delta in this round!"

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

i'm about to become pupil, good luck

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Write this contest or watch football match Barcelona vs Real Madrid? let's vote

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Grandmaster when?

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to be candidate master tonight! (last round I dropped to expert lol)

→ Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it +17 Vote: I do not like it

I've been consistently losing rating, wish for a positive rating change for me!!!

→ Reply
»
6 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

As a newbie, i am hoping to see more div4 rounds. They will help more newbies like me. Thank you

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

Hope IM.

Upd: Success!

→ Reply
»
6 weeks ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

All top 4( 3700 rating) registered for this contest.

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Yes/No contest

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

6 WA for C Div. 2 C problem. i will get -100 delta :(((((

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

Back to Specialist :(

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hopefully expert

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

I chose not to participate in this contest because Imakf had published the editorials accidentally with just codes beforehand and it was there for around a minute or two. Looking at them gave me an unfair advantage in understanding the used data structures and algorithms. Entering the contest with those ideas would have been an act of cheating, so I decided not to participate. Instead, I did leetcode biweekly.

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

    LMAO fr?

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

      seems like a troll comment to me

      → Reply
      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +49 Vote: I do not like it

        It's not a troll comment, the editorial was accidentally posted for 5 minutes.

        → Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +50 Vote: I do not like it

    Could the authors/CF admins confirm whether the round will remain rated in light of this issue? I could understand unrating the round given that this is obviously a pretty significant issue (even though empirically, it's unclear whether this actually meaningfully affected the Div 1 standings; there weren't e.g. far more solutions to D-F than I would expect), but I'm hoping a decision is confirmed sooner rather than later since I'd rather not spend too much time wondering if I made 3300 today...

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +57 Vote: I do not like it

      The round is rated!

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

      And you did it, Congratulations Jay for this amazing performance!!!

      Excited to witness you in the Top 10 Rated Scoreboard in the future.

      I love your video solutions, so please keep them coming!!!

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

Why such a tight time limit in D and E1...

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    I guess that because they are linear complexity...

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

      I thought both of them are O(n log n), what are the linear solutions?

      Edit : I saw the editorial, and I can understand it now. Both problems and solutions are cool!

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

      Yeah, but on cf 1 second is really rare constraint, don't you think? Even linear problems have at least 2 second... I am not blaming, just curious, as i really would love to be a problem-setter one day

      → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can E2 be done with bitmask dp?

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how do you do C?

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

    Hint: Deque

    → Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Hint 1
    Hint 2
    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do you proof that this will work though, i thought about brute forcing it like this but couldn't proof it

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

        If 2 index are same then doing operation between them does nothing and doing an operation that don't cancel either one of them affects the rest elements outside them also. Rest was proofbyAC.

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

          I was mostly looking to bound the fact that less than 300 operations will work

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

    I simulated it with a string, we have i = 0 and j = n — 1 if i and j are both 0 then we add an 01 at j, if i and j are both 1 then we add 01 before i, and we stop once i >= j. Also, if n is odd then it is obviously no.

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

      And we need to make sure that no.of ones equal to no.of zeros. Than only we can make s good else we can't.

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

    If $$$n$$$ is odd or there isn't the same number of zeros as ones, the answer is $$$-1$$$.

    It seems that fixing the first and last element first with just doing operation at the beginning or end always works (I don't know proof).

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

How do you prove Div1A? I spent 30+ mins trying to prove the obvious approach and got no where before just deciding to try to proof by AC (which worked).

It feels way tougher than Div1B and C1. Div1B actually feels more like a typical Div1A to me in that sense — It requires one fairly simple observation which has a straightforward proof. I suspect the solve counts on it would be equal (if not higher) if their places had been swapped.

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

    prove it by ac lol

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

    for real

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

    Obviously, the string has the same number of $$$1$$$'s and $$$0$$$'s, so if you have the string $$$0xxx0$$$, you can add $$$01$$$ to the end, to get $$$0xxx001$$$, and "remove" the $$$0$$$ and $$$1$$$ from the edges, so you basically go from solving $$$0xxx0$$$ to solving $$$xxx00$$$ in one move (a rotation), and since the string is balanced, eventually you will find a $$$1$$$ to match out with the $$$0$$$ at the end. So at the end, it should take less than $$$n$$$ insertions

    The case with $$$1xxx1$$$ is similar, $$$1xxx1\rightarrow 011xxx1 \rightarrow 11xxx$$$

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally I got negative delta -_-

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

No idea for C, brainstorming

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

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

For C problem(Div 2)

answer exists when number of ones=number of zeroes in input string

but how do we construct answer ?

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

    Just simulate with a deque

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

    I used a deque to construct the final answer ..

    Explanation : whenever you have 0....0 then you can insert 01 at the end to balance the zeroes... --> 0....0 01 now the imbalanced part will be : 0 ....00 1
    as the 0 and 1 got balanced ..

    observation : 0....0 after balancing the conflicting zeroes the resulting string becomes 0 ....00 1 ie the next substring taken into consideration will be ....00

    dont' you think that it becomes the same as the first 0 has reached the last end...

    similarly for 1....1 the string will become 0 11.... 1 after inserting 01 at the beginning ..

    0....0 --> 0....0 01 --> 0 ...00 1

    1....1 --> 01 1....1 --> 0 11.... 0

    → Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • 3 observations we have for problem c.
      1. If no.of zeros not equal to no.of ones, we can't make s good.
      1. By using two pointer approach keeping start at 0 and end at s.size()-1, every time we check if start and end positoins are not equal continue 3.else if start and end are 1 insert 01 at start else insert 01 at end+1. keep running this until ur count reaches at max 300 times.
    → Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it +65 Vote: I do not like it

How to solve E faster than $$$\mathcal{O}(n\log(n))$$$?

Also, what's wrong with my solution to D? 230219737 It looks linear to me.

→ Reply
  • »
    »
    6 weeks ago, # ^ |
    ← Rev. 4   Vote: I like it +62 Vote: I do not like it

    Ok, authors' solution (from editorial) to D works 998ms (time limit is 1s): 230265951. With other compiler 842ms: 230266166. After changing it to use vector like a human being instead of array operated like a stack both times go up.

    Authors' solution to E maybe takes 1247ms (230266784) out of 2s (yeah, that's already way too much) but it doesn't even use any vectors while there two damned trees on the input and we are supposed to create another graph and find SCC in it.

    I don't want to complain, but I actually do. These time limits are a joke (and they would be bad even for these squeezed model solutions, which shouldn't be optimized at all) and I strongly suffered because of them. I expect some action from authors or coordinators (or if I'm retarded and wrong somewhere tell me that).

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      It's my fault. All the submissions from testing got AC comfortably, so I assumed the time limits were fine and I didn't check the running time of the official solutions.

      Next time I will double check.

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

        Thanks for sharing--incidentally, does anyone know why the authors' solution to D is so slow? My code (not optimized at all, makes full use of vectors) runs in 340ms, and a priori I'd be very surprised to see a linear solution with the given bounds take a full second.

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

          The solution runs in 514 ms on Polygon (with C++17). Right now I don't know why it becomes so slow on C++20, maybe it's because of the input.

          → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      I'm sorry. But it is strange that on polygon the intended solutions do run faster or inconsistently, compared to on main site.

      For D, intended solution runs 498ms (with stacks and without any optimization), and one of the testers runs <= 220ms. Considering the implementation for this problem are barely the same for most people, we set the TL to 1s.

      For E, intended solution runs 888ms, and errorgorn's HLD solution runs 795ms. Anyway, for this problem, the TL is tight. It's better to set 4s. I apologize for that.

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

        I'd rather win a round than get an apology, but shit happens. Problems were nice anyway, so don't give up.

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

        Maybe it’s good to say something constructive. Every time when I hear that someone is choosing the time limits to (constant)*(model solution) I lose my mind — it doesn’t work like that at all, it strongly depends on the problem. To choose the time limits you should have possibly many approaches implemented and consider why some of them are slower than the others and what do you want to expect or/and at least consider “what actually could people do in this problem”, like “is it tempting to do something more complicated?” or “is it tempting to repeat something three times?”. For example in yesterday’s E it would be “what if someone wants to create graph with vertices not only for each power of 2 jump, but also extra ones for each edge and vertex of the trees?”. I wouldn’t solve that this way, but I wouldn’t say that it’s impossible.

        Errichto once told me something that works in theory and is kind of automatic. He said that a good way is to set the time limit to be equal to the geometric mean between the slowest solution that we want to allow to pass and the fastest that we don’t want to pass. In practice it doesn’t work like that. An example is a problem with $$$\mathcal{O}(n\log(n))$$$ model solution and slower $$$\mathcal{O}(n\sqrt{n})$$$ solution — it might be a case that we’d have to accept the fact that the squeezed slower one might pass to make the model one pass comfortably (or try to change the problem/limits to fix the issue if it’s possible). For example in yesterday’s D such solution is probably link-cut based — I guess you wanted to don’t let it pass, that’s ok, but I don’t think that 1 second is really necessary to do it with one million numbers on the input.

        About time limits in the round there is also a general stuff. I think if someone asks about most classic most popular cf time limit, the answer is “2 seconds”. So I’m surprised that time limits set to 1 second in many problems where the solution isn’t something that would obviously take zero time (like $$$\mathcal{O}(1)$$$ or $$$\mathcal{O}(factorization)$$$ for $$$n$$$ up to $$$1e9$$$) didn’t bring any attention. Also these 2 seconds are meant for the problems which don’t do anything crazy and problem with $$$\mathcal{O}(n\log(n))$$$ size tree-structure sounds way more complicated. So I don’t think that either 2s for D or 4s for E are automatically good choices.

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

      I think your solution's slow runtime on D (as well as the authors') is caused by an I/O bottleneck. I resubmitted your first skipped solution using cin/cout with standard optimizations (ios_base::sync_with_stdio(0); cin.tie(0);) and then with the original code (in case the slow runtime was caused by poor server performance during the contest). See below (first two results are your solution, next two are with cin/cout): Switching to cin/cout cuts your runtime by about 500ms, easily fitting your solution into the time limit.

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

        What's if my solution would do something more complicated but still linear?

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

          I'm not taking a position on whether the time limit was appropriate--I was just curious about why linear solutions were running so close to the 1s time limit, and once I figured it out I wanted to post in case anyone else had the same question.

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

      The author's solution is hacked (tl). Hack And Benq's solution during the contest also didn't survive.

      And the hack test case is not even carefully constructed. It's just two random chains. I didn't see the TL of this problem make any sense. And it's totally unfair that heavy-light decomposition can pass this problem and binary lifting can't.

      Although I didn't solve this problem during the contest, I feel it's better to rejudge this problem with a larger TL.

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

        Did something happen about it? Model solution not working sounds serious

        → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +46 Vote: I do not like it

      I went here to check if you complained (and if not to complain myself).

      There is a tendency for Chinese authors to write insane constant optimized solutions and then set TL 2x (or worse) from them. I remember one ptz contest where the bottleneck was calculating nimber multiplication, and TL was set as 1.5x from a solution that uses the fastest nimber multiplication code from yusupo judge.

      I don't want any rejudges or anything, but I want coordinators to check those kinds of things.

      → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

D's idea ?

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

    Always use 1 and try greedy

    → Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    If you can merge index x and y then you can merge 1 with x or 1 with y. By contradiction assume that you cannot. So ax < cx and ay < cy. Adding : ax+ay < c(x+y) < c.x.y. A contradiction. x+y < x.y for all positive x,y. Except for x = y = 1

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem C Div-2 : Who else overthinked and overkilled just by ignoring n<=100 constraint..??

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

    haha me) The problem is quite easy with simple insert.

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

    Ohh was it 100?? I literally assumed n of the order of 105 Now it makes sense why the construction is possible within 300 operations

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

bad task div1 C

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

timelimit on E1 so tight (for python atleast) ;(

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

any E ideas? I try scnaline, but, not working for me :)

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why always use 1 works for div2D?

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why do I suck at greedy problems like D?

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the idea behind the problem A in div2

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

    ans=Yes if all elements are same ans=No if no of unique elements>=3 in case of two distinct elements ans=Yes if min(frequency(elem 1),frequency(elem 2))=n/2 answer will be of form a b a b a b...

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

20 points away from CM...

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Casting an ancient curse on Div. 2 problem C authors.

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

    Hey, that's my line!

    Honestly I think that C is not that bad, D however seems a bit troll: 2000 points for a problem where you can just connect the first node with any of the nodes that come after it (not even a real graph problem, just a tiny bit of math).

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

      Sorry for stealing your line =)

      My take on it is that figuring out why connecting everything to the first node in D is correct is much better than calculating all the correct indices on every iteration of C.

      → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

E2 was easy just read the constraints k<=10 bruh

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

What is this message? I was so scared thinking my fraud solutions were exposed and hacked manually by authors

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

Test cases are very weak for Div.1 B, my solution for B passed even on using int, should not this test case be available in pretests

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

screwed up so bad lol

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

1D is one of my favorite problems I've solved in a long time. I was working towards a totally different solution path when I realized that we could drop cycles to solve the problem in one move, at which point I spent several minutes thinking to myself about how cool that observation is before going to implement. Thanks to the authors!

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

https://mirror.codeforces.com/submissions/jiangbowen/contest/1889

Imagine solving C2 and getting FST on C1 lol

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

    How? Codes and languages are same.

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

      Time limit on C2 is 4 seconds but in C1 it's one second.

      → Reply
      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +32 Vote: I do not like it

        Then? Code submitted to C2 takes 982 ms, same code submitted to C1 takes 1000 ms.

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

    lmao

    don't know if it's luck or unluck

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for this awesome Div2 round <3 ....

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

It was a very interesting round! Thanks to the Authors!

→ Reply
»
6 weeks ago, # |
← Rev. 4   Vote: I like it -19 Vote: I do not like it

Guys, here is my submission for Div2 — E1 problem. It says TLE however, I can see there is output printed for the TLE testcase

MikeMirzayanov Cocoly1990 Imakf waaitg , this looks like a linear time-complexity difference. Can you guys help here. I think increasing time-limit in such problems will help ??

Also the below 2 submissions for the problem have same codes. But you can see that the problem have different TLE failing test-cases. Submission 1: https://mirror.codeforces.com/contest/1890/submission/230270545 Submission 2: https://mirror.codeforces.com/contest/1890/submission/230272906

Please help here guys /\

→ Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it 
Easisest solution for C :   (claim : total_operation <= 50)
    Pre-requiite : observation

    When you see the operation, insert '01' what it means?
             :-> Assume it is like a bracket () , 0 -> +1 , 1 -> -1
                 you can create a Perfect bracket sequence with the operation? (sounds cool)
                 Some property :  pref_sum >=0 , at last pref_sum =0
    Now, lets solve the Problem:
             one pointer at the left end , one at right end
             if(s[i]!=s[j]) -> we can continue,and move the pointer respectively
             otherwise, both is '1' or '0'
                 let '1' : we make pref =0, 
                           when we have an subarray whose pref=0 -> we can compensate it
                           otherwise not possible
                           Now you are confused that from which side we check for pref=0 condition
                           it turns out that  for '1' check from right pointer
                                              for '0' check from the left pointer
                 vice-versa for '0'

            Yaa We are done :
→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It Indeed Was A Great Contest :) :)

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It was soo cool

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

Thanks for the nice Div2 round. I'm finally CMMMMMMMM.

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

is it too much to ask for another 6 points to become cyan :(

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I hate Doremy

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for such an amazing round! The tasks were truly enjoyable!

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Very interesting round, thank you!

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

Finally, I became a master. Thank you for this interesting round!!!

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Div 2, in Problem C only 1 operation insert 01 but in Editorial can insert 10 ?

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    q.push_front('1');
q.push_front('0');

    If you mean this lines, you have to read it carefully, he is pushing 1 to front first then 0 So it's inserting '01' at front but step by step.

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

problems are good, but i think it could be better to include the statement ("not necessarily adjacent") in div2 E . i thought that the days should be consecutive and fell into wrong idea.

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B, how is 1010101 a bad string ?? (test case 4)

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

    t=1010101 is a good string. However s=101100 is not a good string, and you cannot make it a good string by inserting t (as often as you want). This is because s contains the substring 11 and even inserting t between those two 1s doesn't help as t both starts and ends with 1, i.e. you just end up again with the substring 11 after inserting t.

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The div2 C's implement is not easy...

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow my first time First Solve . Div2B

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why did the space come in qingshan loves strings 2 -1st output?

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

Dear Imakf in this contest . I just do a copy paste from a user in [problem:1890B]question .I am very regreatfull for that inccident.I am making you sure that i will be never happend again. Please do not ban my account.

→ Reply