Imakf's blog

Codeforces Round 906 (Div. 1, Div. 2)
By Imakf, history, 13 months 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

Comments Comments (149)
| Write comment?
»
13 months ago, # |
  Vote: I like it +35 Vote: I do not like it

fuka round!

→ Reply
»
13 months 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
»
13 months ago, # |
  Vote: I like it +121 Vote: I do not like it

As a tester, problems are very cool! ><

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

Hoping that it would be a great contest

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

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

→ Reply
»
13 months 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
»
13 months 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
»
13 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Contest timing clashes with El Clásico.

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

As a player, I wanna be red.

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

i was forced to test

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

    Thanks for your voluntary test!

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

Thanks for the early Score distribution lol:)

→ Reply
»
13 months 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
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can't wait to become blue

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

.

→ Reply
  • »
    »
    13 months 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
    • »
      »
      »
      13 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      .

      → Reply
      • »
        »
        »
        »
        13 months 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
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

GusFring orz

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

Imakf round!

→ Reply
»
13 months 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
  • »
    »
    13 months 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
»
13 months 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
  • »
    »
    13 months 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
»
13 months ago, # |
  Vote: I like it -18 Vote: I do not like it

Is it rated?

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it
    How will everyone get non negative delta if it was rated
    → Reply
    • »
      »
      »
      13 months 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
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Woah, i can see a lot of reds

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

Clashing with LeetCode Biweekly. Would skip this one.

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

    Codeforces round is always priority.

    → Reply
    • »
      »
      »
      13 months 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
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    leetcode clashes with cf*

    → Reply
»
13 months 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
  • »
    »
    13 months 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
»
13 months 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
»
13 months 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
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Grandmaster when?

→ Reply
»
13 months 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
»
13 months 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
»
13 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Hope IM.

Upd: Success!

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

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

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Yes/No contest

→ Reply
»
13 months 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
»
13 months ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

Back to Specialist :(

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hopefully expert

→ Reply
»
13 months 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
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    LMAO fr?

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

      seems like a troll comment to me

      → Reply
      • »
        »
        »
        »
        13 months 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
  • »
    »
    13 months 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
»
13 months 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
  • »
    »
    13 months ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    I guess that because they are linear complexity...

    → Reply
    • »
      »
      »
      13 months 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
    • »
      »
      »
      13 months 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
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can E2 be done with bitmask dp?

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how do you do C?

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Hint 1
    Hint 2
    → Reply
    • »
      »
      »
      13 months 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
      • »
        »
        »
        »
        13 months 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
        • »
          »
          »
          »
          »
          13 months 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
  • »
    »
    13 months 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
  • »
    »
    13 months 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
»
13 months 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
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    prove it by ac lol

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

    for real

    → Reply
  • »
    »
    13 months 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
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally I got negative delta -_-

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

→ Reply
»
13 months 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
»
13 months 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
  • »
    »
    13 months 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
    • »
      »
      »
      13 months 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
      • »
        »
        »
        »
        13 months 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
        • »
          »
          »
          »
          »
          13 months 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
    • »
      »
      »
      13 months 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
      • »
        »
        »
        »
        13 months 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
      • »
        »
        »
        »
        13 months 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
    • »
      »
      »
      13 months 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
      • »
        »
        »
        »
        13 months 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
        • »
          »
          »
          »
          »
          13 months 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
    • »
      »
      »
      13 months 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
      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

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

        → Reply
    • »
      »
      »
      13 months 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
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

D's idea ?

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

    Always use 1 and try greedy

    → Reply
  • »
    »
    13 months 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
»
13 months ago, # |
  Vote: I like it +13 Vote: I do not like it

bad task div1 C

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

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

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why always use 1 works for div2D?

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why do I suck at greedy problems like D?

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

20 points away from CM...

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    13 months 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
    • »
      »
      »
      13 months 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
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
13 months 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
»
13 months 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
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

screwed up so bad lol

→ Reply
»
13 months 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
»
13 months ago, # |
  Vote: I like it +34 Vote: I do not like it

https://codeforces.me/submissions/jiangbowen/contest/1889

Imagine solving C2 and getting FST on C1 lol

→ Reply
»
13 months 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
»
13 months 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://codeforces.me/contest/1890/submission/230270545 Submission 2: https://codeforces.me/contest/1890/submission/230272906

Please help here guys /\

→ Reply
»
13 months 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
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It Indeed Was A Great Contest :) :)

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It was soo cool

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

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

→ Reply
»
13 months 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
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I hate Doremy

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

→ Reply
»
13 months 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
»
13 months 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
  • »
    »
    13 months 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
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow my first time First Solve . Div2B

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

What is purpose of using priority queue in dijkstra algorithm?? In leetcode i solved a problem which requires dijkstra algo,I implemented it by using normal queue and my solution got accepted but when I'm solving CF problem related to dijkstra I got TLE because of using queue [https://codeforces.me/contest/20/submission/266533020] After that I use priority queue and my solution is accepted [https://codeforces.me/contest/20/submission/266536259] can anyone explain what is the reason??

→ Reply