AlphaMale06's blog

By AlphaMale06, 14 months ago, In English

Hello, Codeforces!

ognjentesic, wxhtzdy, OAleksa, AndrewPav, Acanikolic73 and I are glad to invite you to the Codeforces Round 900 (Div. 3).

It starts on Sep/26/2023 17:35 (Moscow time)

You will be given 7 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round is 10 minutes.

Also note that there will be a 12 hour open hacking phase after the round.

Remember, that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

  • take part in at least five rated rounds (and solve at least one problem in each of them)
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, the round will be rated for you.

Problems have been created and prepared by AlphaMale06, ognjentesic, wxhtzdy, OAleksa, AndrewPav, Acanikolic73, and Vladosiya.

We would also to thank:

  1. Vladosiya for the amazing coordination and help with preparing a balanced problemset, and for giving us the opportunity to create a Div. 3 round.
  2. MikeMirzayanov for the amazing Polygon and Codeforces platforms.
  3. JovanB, abc864197532, sevlll777 for red testing
  4. NemanjaSo2005, n0sk1ll, allllekssssa, Alexdat2000, misorin, Hyperbolic for yellow testing
  5. DAleksa, ljuba, alex.kudryashov for purple testing
  6. MihailoT, SashaT9, BULLMCHOW, Chrisedyong, --tofu-- for blue testing
  7. Andrijanikolic73, Mihajlo18, UrosNedic, Klaus26, Escaquejant, mxon, max0n for cyan testing
  8. Budimmm for gray testing

Also a very special thanks to the most dedicated tester I have ever seen, NemanjaSo2005.

I wish you luck, and hope you like the problems and learn from them.

Update: Editorial is out.

Congratulations to the winners:

Unofficial:

  1. jiangly

  2. SSerxhs

  3. BucketPotato

  4. neal

  5. risujiroh

Official:

  1. hackerjohn

  2. wahb

  3. kutcoder

  4. Sxy_Limit

  5. not_rainboy

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

| Write comment?
»
14 months ago, # |
  Vote: I like it +26 Vote: I do not like it

As a coordinator, it was fun to work on the contest in English for the first time!

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

    As a problem setter, I'm proud to have made the first (mostly) Serbian Div. 3 round :)

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

Best of Luck Guys . Surely this would be fun .

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

Serbian div 3, orz!

»
14 months ago, # |
  Vote: I like it -13 Vote: I do not like it

is it rated?

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

As an author i didn’t make any tasks.

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

As a tester, I hope you to enjoy the contest and read all the problems. Good luck!

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

As a tester, problems are well balanced and really interesting. Hope you will enjoy solving them and get positive delta!

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

    I will be taking part after reading this statement and having faith in your words :). I don't have any rating hopes as I am more interested in enjoying the round :).

    Will give my review after the contest !!

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

As a tester I can confirm that NemanjaSo2005 is a tester any author would wish to have. orz.

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

Happy 9th centennial! 100 to millennium!

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

100% SERBIAN BESTEST ROUND!!! SERBIA!!!

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

As a special tester, the problems are good and test data should also be good!

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

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

As a tester, the problems were interesting. I hope all of you enjoy this round.

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

As a tester, I recommend you to read all the problems.

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

Sorry but shouldn't the 900th contest be rated for whole community. I think 901st and this round should be swapped.

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

    Don't really see why it should? It's just a number. Maybe if it was 1000th.

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

As a tester, I hope you to enjoy this round, because the problems are interesting and balanced. Good luck!

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

As a late one tester I wish you all good luck!

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

Screwed up the edu round, hopefully this will make up for it!

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

900! damn i feel old

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

This will be my first official Div.3 contest in 5 months

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

ًWish i get green

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

will there be 12 hour hacking phase round??

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

Round #900 hope to be special for me <3.

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

Cool

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

Do we get 10minutes less if we submit a wrong submission??

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

Hope i can color upgrade ヾ(⭐▽゚)ノ

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

    Me too.. missed by 12 pts last round:(

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

      how do some coders start their journey from 1400 rating? how ?? you are one of them, i'd like you to answer

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

        The codeforces ELO was initialized to 1500 at that times (2018 prob go search yourself idc).

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

        Codeforces rating actually starts from 1500, but a few years ago they made some adjustments so a fake rating is shown for the first few rounds (e.g. your rating is 1400, but 500 is shown). The adjustment becomes less and less, and after like 5? rounds it disappears.

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

Just a comment to get some contribution:)

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

first div3 as out of competition :)

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

    Hopefully I also get to this point someday ^⁠_⁠^

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

Finally an Alpha Male Round :D

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

Can anybody explain what 10 min of penalty means

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

    As you take more and more time to get to the answer, Points get deducted

    For example a guy who solved a problem in 10 minutes would get better rank than guy who solved at 20 mins(Assuming both solved it correctly in the first submission itself)

    But if the 10 mins guy made an incorrect submission before his accepted answer, 10 minutes worth points will be deducted from that problem's points, So in this particular case both 10 and 20 minutes guy will get same points even tho 10 min giy solved it earlier

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

    In Codeforces, you usually lose 0.4% of the task's points for every minute between contest start and submission time, plus 50 points for every failed attempt, the penalty caps out at 70%. Here, the failed attempt penalty is 4% of the total points rather than flat 50 points.

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

      He asked about exICPC penalty rules. Not Codeforces rules.

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

        You're right, I forgot ICPC rules are used for Div3+ rounds (for those who don't know — there's no points, first sort key is total problems solved, second key is the sum of deltas of submission time and contest start + 20 minutes per failed attempt, except here it's 10 minutes instead).

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

Best of luck everyone :D

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

do not have a point of 1900 or higher in the rating.

Shouldn't it be $$$1600$$$?

»
14 months ago, # |
  Vote: I like it -12 Vote: I do not like it

Why always in queue :(

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

Nice.

»
14 months ago, # |
  Vote: I like it +5 Vote: I do not like it
Le authors:
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I think u should just stop founding problems in others and focus on getting better. U are responsible for every problem in ur life bro :)

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

    just use treap)

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

I really liked your ordering of D and E.

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

QueryForces!

»
14 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it
I love number theory too. Thanks for this problem ^_^
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    could you please explain your reasoning behind F? The only one that came to mind was counting divisors in N^1/3 but couldn't proceed from there?

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it
      Hint
      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you for the reply. I get it now since the gcd(a,n)==1, if I may ask the method of counting diviosrs is the same as this [N^1/3] or is there an easier way (https://codeforces.net/blog/entry/22317)

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

          factor the number given in the input and just maintain stuff on a map

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

            Thank you for the reply, and the excellent problem set as well, hopefully, I reach blue this time :)

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

    Answer is "yes" when n is divisible by d(n).
    Reason:
    lets say if we prime factorize $$$n$$$ then we get: $$$p_1^{a_1}*p_2^{a_2}*p_3^{a_3}*...*p_k^{a_k}$$$
    so $$$d(n) = (a_1+1)*(a_2+1)*(a_3+1)*...*(a_k+1)$$$
    let $$$x = \frac{n}{d(n)}$$$. so we need to multiply $$$d(n)$$$ with $$$x$$$.
    now we can just multiply $$$n$$$ with $$$a = p^{x-1}$$$ where $$$p$$$ is a prime number not contained in $$$n$$$. Thus $$$d(n*a)$$$ will be $$$d(n)*x$$$

    ps: I replied to my own comment by mistake lol

»
14 months ago, # |
  Vote: I like it -10 Vote: I do not like it

CF was lagging as hell today!!!

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

Problem B solution:

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

    just print any odd sequence of length n

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

      Yeah, but this one also fits the restriction of a_i <= 3 * 10^5 =)

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

Do we really need to know splay tree to solve a div3D? or there is easier solution.

Btw, problem is same as: https://www.hackerrank.com/contests/w7/challenges/helix/problem

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

    No...

    It's just counting the number of reversals that cover each index (because the reversals are symmetric wrt the segments, the order doesn't matter), so it can be done with a "sweep line" sort of thing (idk if it's technically a sweep line).

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

    There is a simpler solution.

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

    Even easier can be done with Treap. Implementation is very simple, so you might as well learn it if you haven't already. Here is my 30-line template, if somebody wants it:

    Spoiler

    Practice Problems:

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

Cool round! D,E,F are good (even i solved D&E with segment tree lmao)

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

I believe this is not the intended solution, but we can solve D using Splay(or other BST).

This trick is a well-known template on a Chinese OJ called Luogu. There are also similar problems on many other OJs.

We can maintain the reverse operation in $$$\log n$$$ time. So just copying one template code and simulating the requested operation is enough to get AC.

__gnu_cxx::rope also offers this functionality. However, the 1s TL is too stringent, causing it get TLE due to large constant factor.

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

    Of course it's not the intended solution.

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

Wrong answer on test 7 in problem F when there was only 2 minutes left :((

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

I got TLE in problem D on test 10 :((((((

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

    Because yours solution is $$$O(n^2)$$$ lol:)

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

I have solved problem E using sparse table and binary search, but it feels like an overkill. Is there an "easier" solution?

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

    Fairly sure that is the intended solution, you can't precompute because the value of k varies. Anything else that involves solving bitwise seems much more overkill to me than sparse table / binary search.

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

    I did it using prefix concept and binary search.

    You can have a look at the solution https://codeforces.net/contest/1878/submission/225351971

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

    Yeah, you will see once the editorial is out

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

    If you fix l and iterate over r, then AND will change atmost 32 times. You can precompute the next index at which it changes

»
14 months ago, # |
  Vote: I like it -22 Vote: I do not like it

can someone tell me why am i getting TLE submission . terrible div 3 BTW

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

    Don't use memset, because you will get unnecessary reset when the number of test case is high. Just use for loop to reset the value of "pre" array instead.

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

      .

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

      i removed the memset still TLE submission

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

        the inner loop, j will smaller than n, not N (n here is the number of element in the array, not the N = $$$2 * 10^5$$$ you defined)

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

          yeah i saw that silly mistake. fixed it and the solution is AC NOW. i really wanna kms again

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

    It's because you're using memset in each test case which resets the whole array with size $$$N$$$ not size $$$n$$$.

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

      انا هقتل نفسي بجد. هنقص عشان الغلطة الهبلة دي :)

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

        اديك اتعلمتها بالطريقة الصعبة مش هتنساها تاني بعد كده

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

Is it really div.3

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

Problem G seems cool. Is it use LCA + Binary Lifting + Ternary Search the Answer?

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

    It is LCA + binary lifting. I don't see how ternary search could be applied, though.

    My solution may or may not be wrong (feel free to hack because I feel like it's probably wrong and/or too slow and/or too memory inefficient) but what I did was to sweep line on the first/last occurrences of each bit. Implementation requires binary lifting as you said.

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

      From what I observe (still not sure) for a path of $$$p_1, p_2, ..., p_k$$$ I notice that the results forms a parabolic function and we need to pick an optimal $$$i$$$ so that the result is maximum

      But I'm still not sure about it tho

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

        ternary search does not work because: 1. too slow (log^3) 2. wrong because the function of the answer is not not strictly increasing

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

        We can unroll the path into an array and create segments for each bit, which range from the first occurrence of that bit to the last occurrence. The problem is then reduced (with some extra details) to finding a point covered by the maximum number of segments. AFAIK, ternary search doesn't work here.

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

    LCA + binary lifting don't really seem like a Div. 3 approach, do they?

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

      It appeared in round 881 problem F2, which barely anyone solved ;)

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

    are you sure ternary search would work? I think binary searching for 30 places. where bit count of left side is exactly i (i from 1 to 30).

    can you please explain how would you do ternary search??

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

      Nah I'm still not sure. Just a hunch. What about yours?

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

        i think we can binary search 30 times like this ->

        for each i from (0<=i<=30) we can search binary search for first index j (vertex) from left where OR from first vertex to j vertex has bitcount of i then current value = bitcount(0 to j) + bitcount(j+1 to last). this way left and right will be divided 30 times, then max over all 30 values.

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

          Wow this one's pretty neat. Cool approach. Thanks

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

          I used the same idea in my implementation. It gives TLE as its complexity is O(N*log(N) + Q*30*log(N)*18). 225432018

»
14 months ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it
Secret
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    I actually think it's a good div3. Not too easy to be speedforces but not too hard to be div2

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

      gap between C and D

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

        True DE should have been swapped but my point still stands

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

          Yeah, we had to change D in the last moment, the initial D was actually good enough for div3D.

          Also I think E is too hard for div3D

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

      Yeah dude, problems are ones of the best i've seen in div3, enjoyed them a lot

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

does G have a better solution than $$$O(q\cdot log^{2}n\cdot log(max A_i))$$$?

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

Pretty sure E can be done in $$$ O(q * log ^ 2 n)$$$ . Just had not enough time to accomplish it.

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

I hope i can reach LGM after sys test

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

How to pass E so fast? Right! use ACL! 225318799

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

If someone prefers video explanations or interested in knowing how to think in a live contest or reach to a particular solution.
Here is my live screencast of solving problems [A -> E] (with detailed commentary in Hindi language).

PS: Don't judge me by my current rating :(

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

A good contest QueryForces :)

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

Python is pretty slow for E (drawbacks of using python I guess...):

https://codeforces.net/contest/1878/submission/225408163 This submission TLEs

However when I change bits to 31 instead of 32, it passes:

https://codeforces.net/contest/1878/submission/225409398

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

    Yeah, my C++ 32 bits kept TLEing, but 30 bits passed; I'm such a clown made 4 TLE submissions because of that.

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

    It is ur problem using 32 instead of 30 bits.

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

I solved F successfully after 2hrs + 5min but didn't submit as i thought round was of typical 2hr duration.Clown moment for me.

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

someone tell how to reverse the string from a to b in o(n) time when q queries are given .it is easy if q queries are of the form i to n-1-i but here its i to j ig and its not symetric

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

    It is symmetric for each interval separately, because they are disjoint

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

      u are saying that i need to calculate no. of reversals for eacj index and if its even leave it as it is and if its odd take that character to n-1-i th position?

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

        No, but you can basically treat each l, r as a separate test case and then solve a much easier problem

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

          what do u mean by l,r?those are arrays in the question...

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

            Yeah, you can basically divide the string into substrings from $$$l_i$$$ to $$$r_i$$$ and solve a easier problem for all $$$i$$$

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

StructureForces

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

    Structures are beautiful :)

    Also E required prefix sums and that's the only structure on the whole contest lol

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

    E is pref sums or segtree or sparse tables. If pref sums is structure than using arrays is also structure.

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

D and E were extremely cool problems. First time getting to use segment trees in an actual contest :)

»
14 months ago, # |
  Vote: I like it -31 Vote: I do not like it

worst contest i have ever seen in my life ... the level was suddenly increased .... a request to mike that do not allow people like them to make contests

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

Dichotomy combined with segment tree, what a nice problem E!

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

Too many data structure problems can be solved by using template, and the questions are so long that the reading experience is poor. May D is too difficult for Div.3.

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

    wdym, only E is a data structure, and even that can be solved using prefix sums

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

      D can be solved with treap or splay tree tho

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

      problems are all nice, its just can be solved by using template. Whaterver, I just say that D is not easy to fast get meaning for me non-native English speaker

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

      Womt prefix sum give tle?

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

        It's $$$O(Q \cdot logn \log(maxA)$$$ so it's not

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

      how prefix sums??

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

        For each bit, build prefix sums (if the bit is present in $$$a_i$$$ then add 1 else don't add anything) now we can check for each bit if it exists in the whole subsegment $$$[l,r]$$$, if $$$pref_r-pref_{l-1}=r-l+1$$$

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

My B's solution is completely random, I just picked three primes and created the array, checked for some random N <= 100 then submitted. Can someone try hacking it? Btw, overall nice round! Good problem set, except D, which was googlable.

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

    Your B won't be hacked cause your code is absolutely correct

»
14 months ago, # |
  Vote: I like it -9 Vote: I do not like it

https://codeforces.net/contest/1878/submission/225409196 WHY THIS SOLUTION IS GIVING TLE ON 10TH TEST CASE?

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

Had got the logic for question D. messed up by using lower bound instead of upperbound. Got AC on D after the contest

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

    Something similar happened to me. I was using the lowerbound on the 'l' array and therefore there were some edge cases on which the solution was not working and I got WA 3 times. Right after the contest I submitted it using lower bound on the 'r' array and it got accepted. I wasted a lot of time on this.

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

Superb contest. Educational and fun to solve

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

In problem D, I just wrote brute force, I was not able to handle time complexity. Can anyone help me to reduce the time complexity of this program?

void solve()
{
    ll n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    vector<ll> l(k), r(k);
    for (ll i = 0; i < k; i++)
        cin >> l[i];
    for (ll i = 0; i < k; i++)
        cin >> r[i];
    ll q;
    cin >> q;
    vector<ll> x(q);
    for (ll i = 0; i < q; i++)
        cin >> x[i];
 
    for (ll i = 0; i < q; i++)
    {
        ll xx = x[i];
        ll a, b;
        for (ll j = 0; j < k; j++)
        {
            if (l[j] <= xx && xx <= r[j])
            {
                a = min(xx, r[j] + l[j] - xx);
                b = max(xx, r[j] + l[j] - xx);
                break;
            }
        }
        reverse(s.begin() + a - 1, s.begin() + b);
    }
    cout << s << "\n";
}

**Submission Link**

https://codeforces.net/contest/1878/submission/225389151

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

    There are $$$q$$$ updates, each one of which will reverse a string of length $$$n$$$ (in the worst case). Reversal of a string of length $$$n$$$ if $$$O(n)$$$ and thus, your code is $$$O(nq)$$$.

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

      Yes, I understood you. But I cannot reduce it. Can you help me to reduce it?

      or if possible you can edit my code.

      • »
        »
        »
        »
        14 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it
        Hint 1
        Hint 2
        Hint 3
        Hint 4
»
14 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Although I wrote poorly in this round, I know it is my own problem, and I hope I can learn from it and strive for a higher score and ranking in the next round

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

Why are O(n) solutions to C getting hacked? Isn't it guaranteed that the sum of n <= 2*10^5. If you didn't want O(n) why don't you just increase n?

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

    You kinda just admitted you can't read the constraints

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

      Yup, we allowed precalc for gauss sum because not everyone know the formula, we even bolded it lol

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

      Lol, I just read again after I saw this. I guess muscle memory made me see "it is guaranteed it doesn't exceed" Still why not just increase n to maybe 10^9 or something.

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

        Answered that in the comment above

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

        Well, yeah I kinda agree on that. Like, it's a Div3C, you are usually expected to know the formula.

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

    Actully, it isn't)))

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

    Read again: Note that the sum of n over all test cases may exceed 2⋅105 .

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

Great contest hope to become expert after it

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

First time using Square root decomposition in a contest (for E). Took a lot of time to debug it but got AC!

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

Learning From The Contest: A C++ map may return a garbage value for an entry that is not present instead of 0. Costed me an AC on F(was pretty simple acc to me. D >>> F ) :(

WA bec didn't check if the entry is not there in the map 225417281

AC just after adding a check 225413613

However it is not the intended behavior, can anyone confirm?

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

    D isn't harder than F, you can divide all intervals and treat them like separate test cases basically so it becomes much easier

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

      Ikr. The substring reversal thing was kind of a good observation I would say to apply in the merged intervals to avoid repetitions and it got framed into a really nice problem where pairs of positions were just getting swapped.

      It may be possible but personal opinion I found F pretty standard. Like we need to do what exactly is told. (And regarding the division which is to be done by Prime Factorisation is also a pretty standard technique)

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

        Yeah, but F is kind of weird in a sense where if you know basic number theory you will probably solve it and if you don't you are doomed

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

    I don't know, but I have always assumed that map and unordered_map always return the default value for int(which is 0) when the key is not present, and I have never encountered this issue before, which is quite strange. In fact, my solution to F relies on this behaviour.

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

    I agree D>>F

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

    Accessing mpp[x] where x isn't in the map will return 0, but it also inserts x into the map so the other check (mpp.count(dn)) would then return true for values that shouldn't be in the map.

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

definitely didn't create the same segment tree Q times on E :(

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

Does this relation always hold true? a&b=a+b-(a OR b) physics0523

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

    (a XOR b) + 2*(a & b) = a+b is famous. Try to proove it from this.

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

can we prove in C that we can make every number b/w (k*k+1)/2 and (n + n — k + 1)/2 ?

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

    For example $$$n=10$$$ and $$$k=3$$$.
    $$$\{1,2,3\} , \{1,2,4\}, \{1,2,5\},\dots,\{1,2,10\},\{1,3,10\},\dots,\{1,9,10\},\{2,9,10\},\dots,\{8,9,10\}$$$ generates every number between two bounds.

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

      how this solution pass ? link

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

        Maybe some optimization in the compiler. I tried to kill this but somehow it's fast enough.

      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Note that the sum of n over all test cases may exceed 2e5.
        

        That's why.

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

          read this line again, "Note that the sum of n over all test cases may exceed 2e5"

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

    We can prove that it is possible to get any sum between the minimum possible and maximum possible sum.

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

Too bad, my C incorrectly used O(k) algorithm, which should have caused TLE, in fact my friend made a mistake once for this reason and corrected it, but my commit somehow passed the test case and got hacked:(

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

What is the purpose of writing such line in Problem C?

Note that the sum of n over all test cases may exceed 2⋅105

I thought the convention is not to write this statement if it's true. Maybe I should disable the Dark mode to avoid missing the Bold text.

Anyway, Thanks for the contest.

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

    It's because people often don't read that and assume that it's true, that's why it's bolded.

    We also allowed that because some people don't know the formula for the sum of first $$$n$$$ numbers, and we allowed it so they can precalc it.

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

Silly of me to just come up with a solution for "C" using pick and not pick recursion. I need to follow Constraints. Can anyone explain the "C" here?

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

    It can be proven that the answer is YES if $$$x$$$ is between the minimum and maximum possible sum.

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

Do we get any points for successful hacks ?

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

Authors, where is systests for sum of n exceed 2 * 1e5 in task C? I made a stupid mistake because of speedforces and fast-reading of easy task. Why didnt you cover this obvious case? Please cover such tests in the next rounds.

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

    Note that the sum of n over all test cases may exceed 2 * 1e5

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

    We actually tested that case and most testers codes failed, so idk maybe you just made it optimized but not optimized enough?

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

Solutions were leaked during the contest and many people cheated. Requesting CF to filter them out and update the ranking accordingly.

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

    Many People have same segment tree solutions on Problem E...

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

Holeee newbies in comments using stuff like treaps, splay trees and idk what not and complaining. Like do people not think that perhaps this is too much? Why would you even learn all that at this level kek?

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

Video Editorial For problem A to F.

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

I can see how D would be done with trees. How would D be done without trees? Would appreciate a general explanation of the overall strategy.

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

    1) we observe that the k segments are independent of each other so we can solve for each segment and then append them to get the full answer

    2) we observe that to solve for one segment ,a range(a,b) in a query is always in the middle of that segment (because it is either from x to r-(x- l) or from l+(r-x) to x ) i.e we can say that each element is either mirrored about the center of the segment or not.

    Now to solve this we can use Difference array to easily perform range updates of +1 to each element in range(a,b) (indicating that letter getting mirrored) .At the end we get the resulting array and for each A[i] that is odd we mirror that letter.

    here is my python solution

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

Solved problem 1878D - Reverse Madness during the contest in time $$$O\left(n \cdot q\right)$$$ by performing all operations by its definition here 225330103 and here 225334036 in 889 ms

UPD Here is non-hacked $$$O(n\cdot q)$$$ submission 225577099

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

    Petition to ban pragmas

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it -18 Vote: I do not like it

      Petition to all problemsetters to make sure unintended optimized $$$O(n^2)$$$ doesn't pass. Although this can be difficult if slower languages also need to pass.

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

    Hacked!
    If the TL was 2s, I think it will pass the systest...

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

      Thanks!

      Here is a small trick: I solved in $$$O(n \cdot q)$$$, then solved problem E, then solved problem F, then re-solved problem D in right asymptotic.

      In ICPC-like format the first non-hacked solution is used by the system for determining the score. In codeforces-like format the last solution is used.

      So, I still have my +1 score for problem D.

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

      Do you want to hack mine $$$O(n^2)$$$ solution as well (it just uses Rust's regular reverse method of the slice)? 225437815

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

      About problem C I use loop to computa the series, i think it can't TL, but how can you hack me, please tell me why, thank you

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

Can someone share to me segment tree solution for E?

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

I've just upsolved problem E with Segment Tree and binary search, some may say it's unnecessary or overkill but I'm happy to realize and apply them.

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

Why i dont in winners of unofficial or official if i had taken 5 place in div3 overall?

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

why my O(n) solution is getting TLE on main Test 24

225340052

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

    Note that the sum of n over all test cases may exceed $$$2 \cdot 10^5$$$.

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

G, so hard

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

    It's probably easier than an average div.3 G, the only hard thing is the topics it requires

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

orz not_rainboy skip spec

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

tough div 3

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

Wonderful G! I like it!

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

When will the contest ends. I mean is the contest live do i get rated if I submit it today

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

I think it's fun and nice.And it makes me a pupil

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

Unlucky me not mentioned in the blog as a winner because I am the 6th place officially : ). That last round was the best performance of me so far I am so proud of it. Thanks for the good round!

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

the question 1 of this contest is wrongly defined