Imakf's blog

Codeforces Round 906 (Div. 1, Div. 2)
By Imakf, history, 2 years 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 (153)
| Write comment?
»
2 years ago, hide # |
 
Vote: I like it +35 Vote: I do not like it

fuka round!

→ Reply
»
2 years ago, hide # |
← 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
»
2 years ago, hide # |
 
Vote: I like it +121 Vote: I do not like it

As a tester, problems are very cool! ><

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Hoping that it would be a great contest

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

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

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

Contest timing clashes with El Clásico.

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

As a player, I wanna be red.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +192 Vote: I do not like it

i was forced to test

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +19 Vote: I do not like it

Thanks for the early Score distribution lol:)

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

hope get positive rating delta

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

can't wait to become blue

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

.

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

      .

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

GusFring orz

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

Imakf round!

→ Reply
»
2 years ago, hide # |
 
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
»
2 years ago, hide # |
 
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
  • »
    »
    2 years ago, hide # ^ |
     
    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
»
2 years ago, hide # |
 
Vote: I like it -18 Vote: I do not like it

Is it rated?

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

Woah, i can see a lot of reds

→ Reply
»
2 years ago, hide # |
 
Vote: I like it -78 Vote: I do not like it

Clashing with LeetCode Biweekly. Would skip this one.

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

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

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

.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Grandmaster when?

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

Hope IM.

Upd: Success!

→ Reply
»
2 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Yes/No contest

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

Back to Specialist :(

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hopefully expert

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

    LMAO fr?

    → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    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
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it -9 Vote: I do not like it

    I guess that because they are linear complexity...

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

can E2 be done with bitmask dp?

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

how do you do C?

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Hint: Deque

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

    prove it by ac lol

    → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    for real

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

Finally I got negative delta -_-

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to solve C?

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

D's idea ?

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Always use 1 and try greedy

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

bad task div1 C

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Why always use 1 works for div2D?

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Why do I suck at greedy problems like D?

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can someone explain the idea behind the problem A in div2

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

20 points away from CM...

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

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

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

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

screwed up so bad lol

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

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

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

It Indeed Was A Great Contest :) :)

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

It was soo cool

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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

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

I hate Doremy

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

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

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

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

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

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

Wow my first time First Solve . Div2B

→ Reply