yash_daga's blog

Codeforces Round 921 (Div. 1 , Div. 2)
By yash_daga, 10 months ago, In English

Hi Everyone :)

I would like to invite you to my first Codeforces Round, which I set with my friends JaySharma1048576 and mexomerf — Codeforces Round 921 (Div. 1) and Codeforces Round 921 (Div. 2) which will be held on Jan/27/2024 17:45 (Moscow time). This round will be rated for both divisions.

Both divisions will be given 6 problems and 2 hours to solve them.

One of the problems may be interactive. So, you are advised to refer to the guide on interactive problems in case you are not familiar with them.

We would really like to thank:

Good luck, have fun!

Disclaimer

UPD: Scoring Distribution

Div. 1: $$$500 - 1000 - 1500 - 1750 - 2500 - 3000$$$
Div. 2: $$$500 - 1000 - 1250 - 1750 - 2500 - 3000$$$

UPD: Here is the editorial

UPD: Congratulations to the winners

Div. 1:

  1. jiangly
  2. maroonrk
  3. Benq
  4. gamegame
  5. maspy

Div. 2:

  1. kto_eto
  2. fractum_locum
  3. okok
  4. beiyuli
  5. BabaVoss

First solves -

Div. 2:

Problem Participant Time
A jayeshkriplani007 0:01
B Ianlsam 0:02
C rolandpetrean 0:08
D Ignut 0:16
E CoanCoan.com 0:38
F HexShift 1:13

Div. 1:

Problem Participant Time
A Geothermal 0:02
B Benq 0:15
C gisp_zjz 0:13
D Rebelz 0:28
E gyh20 0:32
F Szoboszlai10 1:20
  • Vote: I like it
  • +190
  • Vote: I do not like it

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

good luck

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

I've been waiting for this competition for so many days!

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

Oh, it is my turn: 🥹

As a tester, the problemset is delicious and I hope you enjoy.

Also, ahmet23 orz!!!

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

How many problems are there in both divisions?

btw the duration of 2h is pretty nice :)

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

Eagerly waiting for this contest sir!

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

orz sir yash_daga

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

mexomerf orz

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

Too delighted and proud sir.

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

Where is the score distribution? Best of luck to all contestants!

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

    Scoring distribution will be released strictly before Saturday, January 27, 2024 at 16:35UTC+2

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

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

    Can relate.

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

    Meanwhile ,the expert:

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

    I Swear I think I solved it 30 seconds after contest ended, if it's correct i need 48 hours to rc this damage

    JJK spoiler

    Edit: it was correct, so sad

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

GOOD LUCK!!!

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

So why is the registration limit for Div.2 round changed to less than 1900?

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

    It's always been that way in rounds with separated divisions. See for example round 908

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

      tku, maybe I mistook the upper limit for 2100, just like the last round

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

        The upper limit is 2100 in Div 2 (and Edu) rounds without a corresponding Div 1 round. The idea here is that Candidate Masters may find Div 2 A-C boring, so they may as well start from D2D = D1A (or D2C = D1A, depending on the number of shared problems)

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

m

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

ok nice me also from jharkhand :) waiting eagerly

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

Thank you guys for the info, I will try in my home town.

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

Guess Which problem will be Interactive for Div2

1.C 2.D 3.E 4.F

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

orz yash_daga sir!!!

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

Opened CF after months just to upvote this, hail ISM!!!

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

All the three problem setters have solved most problems related to maths and greedy. So, I suspect Mathforces or Greedyforces incoming.

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

right before usaco :c unfortunate

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

    Fortunately to you, Usaco's website is down rn.

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

its going to be my first contest written by indians and i am very excited for this.

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

I am getting back with coding after a few years with the contest, with a determination to stick to it until I improve this time

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

All the best

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

I Hope to rank up to pupil :DD

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

Good luck!

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

I love the way he writes "You".

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

rp++

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

ORZ%%%

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

Claimer

There may be some pieces of paper harmed during my participation of this round :(

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

This is my first competition i have ever done, I'm not that good, but ill see what I can do lol

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

This is my first contest after eight months away...felt so good back to this cf vibe again!

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

    what were you doing in these eight months ?

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

    Seems like nothing changed lol. This 10 min delay feels like bringing me back to before

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

why delayed

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

One refresh costed me 10 mins of time

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

This is becoming a habit now.

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

Delayforces again...

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

Waiting for love :(

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

Did anyone see the questions

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

1 Refresh cost me 10 min.... :)

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

GoodBye 2023 is that u?

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

GLHF

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

: )

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

why this website is being too heavy to reload in browsers??

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

I could have finished my LoL ranked game, now I lost a star and 10 minutes waiting.

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

    It was your choice to stop playing before you could check if the round is delayed. It's not like the delay was shown 1 minute after the round started.

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

I wasted hours on origami to do 1C.

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

Paperforces

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

What is wrong with question C

I dont get why my code is failing ahhhh damnn it !!!

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

WAForce

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

It took me 10 minutes to do Div2D while 75 minutes to do Div2C,i'm really bad at implementation.

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

    hint?

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

      Linearity of expectation of binomial distribution. Answer is: 1/nC2 * k * sum(f) + m * k * (k-1)/2 * (1/nC2)^2

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

Was I alone to do so? :D

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

    As a Grandmaster...

    → Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it +68 Vote: I do not like it

    I tried folding the paper without drawing any lines, but it ended up being not useful at all since I couldn't tell which creases were mountains / valleys ...

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

    Wish I had a squared paper around me. The pattern was too obvious.

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

      You can get a square paper from a rectangular paper. Just fold a vertex.

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

        yeah, although at times the thickness of the paper from the resulting fold makes it harder to fold even more

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

          Maybe I was unclear.

          • Fold a vertex.
          • You get an isosceles right triangle. Cut the rest.
          • Undo the fold.
          • You get a square with the same thickness as the original rectangle.
          → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Was lazy segtree expected on E ? I got tle on pretest 32...243653603

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

    I used ABI and got 823ms. I really hope authors have a good solution, and not this ugly implementation that almost everybody did

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

      My code got ac after submitting in C++ 64 bits :/

      I think they have an "easier" solution that is to store the sum between each pair of harbors and handle manually the harbors on the side but I think it's less convenient

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

    I eventually used 2 lazy segment trees for E but still less than a second man (C++ 17 7.3.0)....

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

div1B is disgusting

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

    disgusting == I couldn't solve it ?

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
      ← Rev. 2   Vote: I like it +65 Vote: I do not like it

      no, disgusting == simple idea but solution very hard to implement correctly

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

      no. idea is obvious, just implementation + data structures. nothing interesting.

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

Thanks for the round! Feedback on the problems:

A: Good problem, appropriate difficulty for its position.

B: Not my favorite problem (unless there's a better solution than just killing it with a segtree / a set?); all the ideas involved felt standard, but because DS was involved it still took a decent chunk of the round to implement. (Also, implementation would have been mildly less annoying if the array X was sorted; I also would have found it easier if the input was passed as (X, V) pairs and not as an array X followed by an array V.)

C: I strongly disliked this problem. It felt basically like a pattern guessing test--maybe some people had the visualization skills to solve the problem rigorously, but I basically guessed a pattern that seemed reasonable, checked that it works for small cases, and then got AC.

D: Realizing that the problem reduces to "find the number of sequences of A balanced bracket sequences with total length B" was pretty nice. The rest of the problem was damaged by the constraints in one of two ways. After thinking of smart ways to count these sequences since the mod suggested FFT was unintended, I ended up just throwing in the KACTL FFT with arbitrary modulus template, which got AC, though running somewhat close to TL (800ms, not slow enough that I was worried about FST but definitely slow enough to TLE FFT templates with bad constant factors).

I don't know whether this solution was intended or not. I suspect not because of the choice of mod, but if this was intended, then I strongly dislike the choice not to use 998244353 as the modulus, and I also don't like the TL (I would have set something like 3s if FFT/NTT was intended).

Assuming this solution was not intended, it's a tougher situation, especially if the intended solution takes O(n^2) memory or O(n^2 log n) time. If one of these is the case, I honestly might have just let FFT pass anyway (and set a more friendly modulus and TL) since I think it'd be really hard to cut FFT cleanly and the first observation is nice enough to justify the existence of the problem. If there was room, though, I would definitely have set n = 5000. As is, I think "FFT works, but you have to use a slightly unconventional template and it runs close to TL" is a very bad state for the problem.

E: Probably my favorite problem of the round (though I'm biased in favor of EV problems). Not hard enough for its position or point valuation imo.

F: Interesting problem, I had no nontrivial ideas. I think the story got in the way of the statement, and you could state the problem more formally in a shorter and more readable way. I think something to the effect of "there exists a hidden integer x from 1 to n, you can query ranges and judge will output 1 if x is in the range and 0 otherwise, judge is guaranteed not to tell the truth or lie three times in a row" would work, without all the flavor text about the students or explicitly enumerating the four cases.

→ Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 14   Vote: I like it -10 Vote: I do not like it

    Will You stream solutions? How did you do C?

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

      I don't plan to do a stream. This solution seems likely to TLE, as with x = 1e8 and n = 1, your solution loops through 1e8 values per test case, which will TLE when t = 1000.

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

    Bro Can you explain C

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

      2C: We construct the shortest string T that is not a subsequence of S as follows. Iterate through the characters of S and maintain the list of characters we've seen so far. Once we've seen all k characters, add the last character we reached to T and reset the list of characters we've seen. Once we finish going through S, add any character we haven't seen yet to T. Any shorter string can be found in S (we can find the first character of such a string in S before the first character of T, the second character of the string before the second character of T, and so on); I'll leave it as a (simple) exercise to prove that T cannot be found in S.

      If T has length at most n, add additional characters until it has length n and output it as our answer. Otherwise, no answer exists.

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

        During contest I submitted this just as a pure guesswork, totally no clue why we should add last char from each T. Now after some thinking it's a becoming slightly more evident, but still very vague. Something like if it wasn't the last char that is missing, then it should've finished T earlier.

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

        Thanks for the explanation. Very helpful.

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

    I think D might just be https://en.wikipedia.org/wiki/Catalan%27s_triangle. I just checked some smaller cases and didn't prove though.

    → Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it +20 Vote: I do not like it

    Hi, Thanks for the feedback!

    Intended soln of D :)
    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Nice, figured there was likely something like that :) In this case, I would have just set n, m up to 1e6, which clearly passes your solution but fails FFT and other such nonsense.

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

        Yeah, it was a trade-off we did to make the solution less guessable. I initially proposed it as div2D but the testers feedback made us feel that it's harder.

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

    the only good thing about D2F/D1C is the fact that you can play with origami paper while solving it :D (still, definitely an annoying problem lol)

    → Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it +23 Vote: I do not like it

    The model solution of Div. 1F does require some non-trivial ideas. I will release the detailed editorial shortly but till then, here is one of the ideas that you may have missed.

    Hint

    Thanks for the feedback. From next time, I will try to keep the statement concise.

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

      Thanks for sharing! I'll give it a bit more thought :)

      → Reply
    • »
      »
      »
      10 months ago, # ^ |
      ← Rev. 4   Vote: I like it +15 Vote: I do not like it
      Improving Number of Queries
      → Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    On Div2D I figured out the correct fraction quickly but wasted the second half of the contest on figuring out WHAT IS A FRACTION MODULO 1e9+7. Also on trying __int128 or Python, because the unreduced denominator can reach 10^20 and goes beyond the long long limit. Could you please tell if this is avoidable?

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

      Store all numbers $$$p/q$$$ in the form $$$p \cdot q^{-1}$$$ mod 10^9 + 7. It can be shown that addition, subtraction, multiplication, and division (where $$$a / b$$$ is computed as $$$ab^{-1}$$$) all work normally under this representation of fractions. Since all numbers are less than 10^9 + 7, the arithmetic operations can be performed using long longs.

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

    I googled this explicit formula for the convolution of Catalan numbers: https://codeforces.me/blog/entry/87585

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

    I have a solution for C, based on capes of paper, once you fold the paper once there are the same number of capes upward and downward(this mean that all steps before that increments both values equally) so you have V=M + 2*sqrt(2). So in every steps the number of capes get multiplied by two, while the perimiter of the square is multiplied by 1/sqrt(2) then you have a geometric progression.

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

Too curious to know where I failed on C. T_T

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

For d1C, was anyone able to reproduce N = 7 irl? The most I could get is N = 4.

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

Was submitting C in last 30 seconds, but Checking if the site connection is secure take a minute

→ Reply
»
10 months ago, # |
← Rev. 4   Vote: I like it +158 Vote: I do not like it

Is it the problem setter of d1B in a loss of loved ones that he doesn't even guarantee $$$x_i$$$ is in an ascending order but doesn't even show it in the sample either?

btw, i don't understand what the data range is for for d1D.

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

How the hell to mod a rational number? I've managed to get a working solution for d, getting nominator and denominator, but i still don't have an idea how to convert them into valid answer...

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

    check this

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

      Damn, I shoud've learn this earlier... Thanks.

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

      took me 20min to find the solution exactly there. For those still confused:

      • fraction: 1 / 7
      • numerator: 1
      • denominator: 7
      typedef long long ll;
const ll mod = 1e9+7;
ll inv(ll a) {return a <= 1 ? a : mod - (ll)(mod/a) * inv(mod % a) % mod;}

void solve(ll numerator, ll denominator){
    cout << (inv(denominator)%mod * (numerator%mod))%mod << "\n";
}
      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        For me it took 20 minutes just to read the problem statement.

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

        when p is a prime number, inv(a) can be calculated by a^(p — 2) mod p. (^ means power, not bitwise xor)

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

    Link

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

Div2D was so nice.

For every excursion, our answer increases by (total sum of friendship values)/(# of pairs) on average, and the total sum of friendship values increases by (# of non-zero friendship values)/(# of pairs) on average.

This hand-wavy "average" logic works because of the linearity of expectation.

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

    I find it hard to call problem nice when 60% of input is not even used.

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

      I suppose writers originally had this as a much harder problem, then realize they need something for d2d, so they just go fkk it and repurpose it without removing the now reduntant part

      If you consider the problem without the useless information it's not bad.

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

        Agree, overall it's a nice intro to modular arithmetic

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

    Can you please show me your code?

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

mathforces...

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

Anyone thought the position of harbour in div1B/div2E is sorted and keep getting WA at pretest 5?

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

couldn't solve Div2C(Div1A) in 100 minutes

I'm such a brainlet

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

why does binary search not work in B?

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

    it'll work, first stores all the divisors in array , then sort it , now find out that what can be the average difficulty for each sub problem , now we know that our max difficulty won't exceed this average, so use lower_bound on the array of divisors

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

C was definitely one of the problems ever.

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

Too much implementation for a div1 B ...

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

My rating gonna drop due to C. Fuck C

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

C anyone?

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

    I think the point was to check for all intervals of length n if every one of the k letters are in it, if not then the answer is no. Again I'm not sure but if that premise is right you can easily think of a way to construct a string that is not possible.

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

      I thought of that too but there's some flaw in the logic. Take for instance the case when the string's length is greater than n * k. This gives you some 'buffer' characters to play around with, which means that the interval of length n may not necessarily hold all the characters.

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

      1 3 3 11 aabbccabac

      test case where you can fail.

      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it 
        void solve() {
    int n,k,m;
    cin>>n>>k>>m;
    string S;
    cin>>S;
    vector<int> count(k,0);
    map<char,vector<int>> mpp;
    for(int i=0;i<m;i++){
        count[S[i]-'a']++;
        mpp[S[i]].pb(i);
    }
    string ans="";
    for(int itr=0;itr<k;itr++){
        if(count[itr]<n){
            char ch = itr+'a';
            for(int i=0;i<n;i++){
                ans+=ch;
            }
            cout<<"NO"<<endl;
            cout<<ans<<endl;
            return;
        }
    }
    for(int itr=0;itr<k;itr++){
        char ch = itr+'a';
        vector<int> v = mpp[ch];
        for(int i=n-1;i>=1;i--){
            int index = v[i-1];
            int occurence = n-i;
            string ans="";
            map<char,int> temp;
            for(int j=index;j<m;j++){
                temp[S[j]]++;
            }
            for(int p=0;p<k;p++){
                char check = 'a'+p;
                if(check==ch){
                    continue;
                }
                if(temp[check]<occurence){
                    cout<<"NO"<<endl;
                    for(int hehe=0;hehe<i;hehe++){
                        ans+=ch;
                    }
                    for(int hehe=0;hehe<occurence;hehe++){
                        ans+=check;
                    }
                    cout<<ans<<endl;
                    return;
                }
            }
        }
    }
    cout<<"YES"<<endl;
}

        Can you tell where does this code fail??

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

    Straight DP:

    Find first position of all k letters. It would base for len = 1.
    Then for each i = 2..n you must have all k letters after all k letters positions for i - 1. If you keep it properly with reverse link, then construct answer should be easy.

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

    https://codeforces.me/blog/entry/125112?#comment-1110782

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

WTF I didn't submit 1D just because of this 'Just a moment' thing!!!

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

Task C is a very funny task. 10 sheets were damaged

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

I tried to solve problem B using segment tree. But I couldn't do it in integers, because I was required to combine several multiplications; and I couldn't also pass it using floats. How to pass segment tree?

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

    I used Segment Tree and I passed. You store the answer of each position, and operation 1 is range equal to zero and range add an Arithmetic sequence.

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

      My code

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

      Ough, I did other quieries. When I'm adding a harbour $$$p$$$, there are closest to the left harbour $$$l$$$, and closest to the right $$$r$$$. Then I add to segment $$$[x_{l+1}, x_{p-1}]$$$ value $$$-(x_{r}-x_{p})*v_{l}$$$ and multiply to segment $$$[x_{p+1}, x_{r-1}]$$$ value $$$\frac{v_{p}}{v_{l}}$$$

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

    I used lazy segment tree, but instead of multiplying when pushing y just maintained a vector of push's, bit it gave WA on test 8 :(

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

how D?

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

That C..

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

why am i so dumb

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

I felt statement of Div2D to be ambiguous and misunderstood several times. I initially thought once a pair is picked, then its value keep on increasing by one for every next excursion irrespective of what pair is chosen next.

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

    Exactly I wasted a lot of time figuring out the logic for the misunderstood problem, they could have atleast explained a normal test case.

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

I was so close to solving Div2C or at least I hope I was T.T

Edit: nope, not even close

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

too much server problem, but overall good contest and good questions.

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

Hope I will become green this contest.

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

I somehow liked Div1C and Div1E, disliked Div1B, but anyway: Please polish the problem statement before the round (Div1B: "next harbour" concept is strange, Div1D&Div1E: two variables are interchanged, etc.) and please check it carefully for the clarification (I got two wrong responses in this round...).

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

    Sorry about that, will take extra care in future.

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

      Maybe consider sacrificing some pieces of paper in favor of making round even more ideal? :-)

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

I solved 3 problems, I am enjoyed this contest. Thank You

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

i was so exited to participate since this is my first contest lmao , until i spent all the time in the first problem and couldnt solve it lmao , any tips so i can improve ??

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

Can we use binary search to solve Div2 B ? i was trying it at first but i didn't understood where its failing here is my submission 243579415, then i just used linear approach.

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

    I don't think binary search could solve Div2B. Because if K is the answer so every number that smaller than K should be all satisfied. However, if x = 10, n = 2 then all subsets we have are 1-9, 2-8, 3-7, 4-6, 5-5 => gcd of them are 1,2,1,2,5 respectively. So there is no way to split 10 into 2 numbers that have gcd equal to 3 or 4.

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

      Thanks man ,I'm an idiot who forgot how binary search works

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

why CF doesn't let us submit code to check after contest ends :( Just missed submitting E by few seconds and now waiting to see if my solution is correct. Pretty frustrating to wait more.

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

I had fun in this contest. The D reminded me of JEE days. Thank you for fun contest.

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

what is wrong in my solution for question C. My Submission

what I was doing to divide string s into a complete chunk of k alphabets and if someone is missing in last chunk I take this character to form a valid subsequence not present in s.

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

    counter_eg: 2 3 6 aabcbc

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

      Why is it counter to the described idea?

      2 chunks: aabc bc

      a is missing in last one, so ca is final answer.

      I submitted exactly the same idea and it passed pre-tests.

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

        consider 3 chunks and according to your approach, it will give NO, and output "aa" but "aa" is present in the string

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

          I've posted the link to my submission, hack it if you are sure about your counter. To me it seems you misunderstood the proposed idea

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

            You can check the above submission, you will get your answer.

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

Cloudflare is horrible

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

div2B O(n^0.5) with n = 1e8 timed out in python :(

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

What is "orz" btw?, I saw some people saying that?

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

Waiting for tutorial :)

How to know when it will be released?

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

The test cases are very weak for Problem Div2 B. some solution of complexity 1e10 also passed

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

    yes my solution passed with the same problem I'm sure it will TLE now I should have iterated till sqrt(x)

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

Lol, spent last 33 minutes of the round debugging Div.1B, only to understand after the round that coordinates are not guaranteed to be sorted.

In my opinion, such problems problems should contain coordinates already in adequate order.

Div.1B/Div2.D should check participant's ability to invent and implement solution, not ability to carefully read problem statement...

Otherwise, problem is quite nice

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

    wtf i spent 90 mins on B and still didn't figure this out :ded:

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

    Happened to me as well. Noticed after the contest (;-;) hurts

    → Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

Weak pretests on B, need n = 1 case

C is the opposite, yet another brutal pretest

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

speed forces yet bricked

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

DM, how to solve C of div 2?

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

    u just need to count the number of times all the alpha occurs

    → Reply
»
10 months ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

sry for the misconception i realised the error but how can i del this comment

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

Welp... i did 1 problem at least. I didnt know that the contest was delayed by 10 mins, so I was confused and thought it was starting on the end time. I ended up starting like 1 hour into the contest, and did problem A at least. A lot learned! Hoping to be at the next competition as well

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

I might be risking losing all my testing privileges here, but I would like to point out that div1A (or div2C), as well as div2A, were pointed out by me during testing to be very close to a certain CSES problem. According to the judgment of the coordinator, "D2A can be not really new," so I kind of assumed they'd be removing the div2C (it was A2 earlier) but not the div2A (which was A1).

My question is — is this expected by contestants? My perception is that it is not, and I feel there should definitely be some more originality in problems that are supposed to be around D2C in difficulty (D2A being unoriginal is probably arguable, so I won't comment on that).

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

Really good contest! Very nice and fun to solve these problems. Thanks for the round JaySharma1048576 mexomerf yash_daga and all testers!

Solution for Div2C (if anyone needs):

-> After solving Div2A, you can see that to get all possible strings of length n using first k characters, the string s should have n groups of the first k characters.

Eg: if n = 5, k = 3 (a, b, c) then s = "abc abc abc abc abc"

-> so in the given string s, traverse from left to right and form such groups of first k characters and find how many such groups you can make (call it cnt)

-> if cnt >= n, ans is YES

-> else, take the last character of each group and combine it with the missing character of the missing group, this newly formed string will definitely not be a subsequence of s, because theres only one such character in each group and we combine it with the missing character.

Eg: if s = "aabbccabab":

the groups are "abc" "cab" "ab"

so taking last character of every group and missing character, we get "cbc" which is the answer

Submission for reference

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

    Hey can you explain the intuition more clearly about this line "because theres only one such character in each group and we combine it with the missing character."

    what I can get from solution is that since we are making blocks as soon as we get first entry of last remaining element that element will always be single. So it is deemed to be remain unique in pattern as opposed to elements who are repeating more than one time.

    also I am thinking that any single element will also be sufficient for concatenating answer but for sake of simplicity we taking last element which automatically will be single because after that we are terminating that block.

    → Reply
»
10 months ago, # |
← Rev. 4   Vote: I like it +12 Vote: I do not like it

A: It is easy to find out, that size of our answer is $$$nk$$$ (at least because it must contain all $$$aa...aa$$$, $$$bb...bb$$$, etc). So, we can just break our answer into $$$n$$$ blocks of length $$$k$$$. Each block will contain all first $$$k$$$ letters of the alphabet. So, our answer is $$$"abc...$$$($$$k$$$-th letter) $$$"$$$ repeated $$$n$$$ times. $$$O(nk)$$$ per test.

B: Basically, we need to find such array $$$a$$$, that $$$a_1 + a_2 + ... + a_n = x$$$ and $$$gcd(a_1, a_2, ..., a_n)$$$ is maximum ($$$a_i > 0$$$). If $$$gcd(a_1, a_2, ..., a_n)$$$ is equal to some $$$k$$$, that means, that each $$$a_i$$$ can be represented as $$$k * \frac{a_i}{k}$$$, so our sum will be $$$k * (\frac{a_1}{k} + \frac{a_2}{k} + ... + \frac{a_n}{k}) = x$$$. From here we can see, that $$$k$$$ will be divisor of $$$x$$$, so we can iterate over all divisor of $$$x$$$ (let it be $$$d$$$) and check if $$$\frac{x}{d} \ge n$$$, as we want to make each $$$a_i > 0$$$. $$$O(\sqrt{x})$$$ per test.

C: We can do a greedy approach to find such string, that doesn't occur as a subsequence. The algorithm is basically the same as when we solve "Does string $$$t$$$ occurs in $$$s$$$ as subsequence?", but we want to shift our pointer as further as possible. So, we will pick the furthest first occurrence of some letter starting from our current position, after that we will shift our position to the right of that picked one and remember letter on chosen position. If we didn't lack any letter during $$$k$$$ iterations answer is $$$YES$$$, otherwise we can construct answer as follows: we write remembered letters one by one, after that we add letter, that we lack and until size of our answer $$$< k$$$ we will add letter $$$a$$$ to the end of it. $$$O(nk)$$$ per test.

P.S: Funny, that C is a checker for A.

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

After solving D2A D2B I thought D2D would be easy and got the right answer within O(1), but THIS IS THE FIRST TIME I come across fraction representation like "Calculate p⋅q^−1 mod(10^9+7)" and didn't know how. Also the unreduced denominator can be n^4 which is 10^20 and goes beyond the long long limit. That left me stuck trying python or __int128

:(

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

Problem E basically have the same solution with this atcoder problem ARC114E.

Atcoder

Though it seems this did not affect the standings, as I did not found many others solving this lightning fast. (Not that this particularly affected me as I solved this problem pretty quickly when practicing)

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

    Hi, I thought of the problem after solving the atcoder one and mentioned in the round proposal that my problem is inspired from this one.

    According to me, my solution is very different from the solution of that problem. Only the concept of linearity of expectation is common.

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
      ← Rev. 2   Vote: I like it +7 Vote: I do not like it

      To me, there are two key components of the solutions, aside from linearity of expectation.

      Solution

      With these two key concepts the rest of solution should be basic calculations.

      But by far, the first part is hardest one and take the longest to come up with. Unless the intended solution is very far from what I described then I can see your reasonings.

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

        Yeah my solution is slightly ugly and doesn't use the first concept mentioned by you.

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

div2D was one of the easiest problems I've aeen in a while, and yet i spent four tries, first because i summed without modulo, then because i divided by 2 and not multiplied by 2^-1. i should really get a modulo template

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

    what was your approach for div2 D?

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

      well the base expected value is just sum(f_i)/(n choose 2), and then there is exactly m/(n choose 2) probability to add 1, so in expectation it adds 1 * m/(n choose 2), and that's true for all the stages, and it carries over to the rest. so it's ((k-1) + (k-2) + ... + 1) times that m/(n choose 2).

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

Here is my advice about the problems (Div 2):

A
B
C
D
E

Anyway, kudos to the authors of the round, it was still an overall good contest

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

    Implementation of C felt easy to me, you can check my solution, My logic was to check if i can make n or more continuous substrings of the strings or not with every substring satisfying the condition that it contains all the characters from 'a' to 'a'+ k at least once

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

When I submit solutions after the contest is over ?

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

Why is this giving memory limit exceeded for Div2,C? 243648118

I even tried using map instead of set, yet ntg changed. 243653296

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

    For some reason size of your answer is $$$> n$$$ before last while loop, so it becomes infinite.

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

      Right. The variable cnt when goes beyond n, it goes in infinite loop.

      Thanks for the help.

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

FST on test 24 of B... Please, let me get a huge negative delta then I can farm the next div 3

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

I wanna Duhhhhhh!!!!

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

approach for Div2D ??

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

FST Div2B, fail to solve C, endup solve A only

going to buy rope today

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

for DIV2 C

What should be answer for this?

Spoiler

According to me it should be NO. I thought problem states first k lowercase characters.

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

    The problem statement says that the string s will contain only the first k characters, so your test case is invalid anyways.

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

failing System Tests has got to be one of the worst feelings

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

C ka logic btao bkl iski

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

My submission for div.2b got tle on tc 23. Although I had this feeling that it might get tle still I overlooked as it passed the Pretests.

Atleast they could've provided strong pretests :(

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

WA in test case 3566 in C,any?

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

    consider the following test case:

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

12 fricking FST's in B in my room which were so easliy hackable 😢
Lesson learnt

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

why test cases are not visible now???

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

My submission 243558996 passed pretests but wasn't evaluated in the final submission. Coordinators, please investigate.

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

Thank you for the contest!

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

What is the expected rating of C?

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

so many Div2B solutions failed on system tests

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

Test cases of div-2 B :(

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

Easy and elegant solution for E using only fenwick tree and std::set: https://codeforces.me/contest/1925/submission/243668425

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

Can anyone tell what is wrong in my submission? https://codeforces.me/contest/1925/submission/243671686

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

    1 3 3 13 aaabbbcccaabb should give No(ex bac)

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

Why this solution doesn't work for Div2C, I've tried to find testcases where it might fail but cant seem to do so. (I know it might TLE I just wanna get the logic right).

https://codeforces.me/contest/1925/submission/243668507

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

    consider the following test case:

    Test
    Result
    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      Thanks for pointing it out, I will try to solve it now.

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

can someone please tell about the rating system in contest?? why is it showing increasing alot then expected for ones who locked their problem how does this automatic lock hacks others problem and increase up thier ratings?? how?

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

someone please check my submissions for div2 C , it is showing wrong answer for testcase 1 , and showing accepted test case 1 in next submission even when the output is coming same . Plus the output which is coming on submitting is different from custom invocation .

what is this happening ?

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

I feel soo good

for the first time i solved a question

and this is where my Journey started...

Lets goo :>

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

Finally became pupil

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

As a div.2 participant, I find it very strange, that problem creators decided to leave the link to the wiki page of modular multiplicative inverse in statement of 1925F - Fractal Origami but not for 1925D - Good Trip . I didn't manage to figure out how to restore the answer from rational number, even though i had completely correct solution.

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

What would be the rating of C?

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

My approach for problem C was initially this.



#include <bits/stdc++.h>
using namespace std;

void generateSubsequences(set<string>& subsequences, string s, string current, int index, int n, int k) {
    if (current.length() == n) {
        subsequences.insert(current);
        return;
    }

    if (index == s.length()) {
        return;
    }

    generateSubsequences(subsequences, s, current + s[index], index + 1, n, k);
    generateSubsequences(subsequences, s, current, index + 1, n, k);
}

void generateAllSubsequences(set<string>& subsequences, string s, string current, int index, int k) {
    if (current.length() == k) {
        subsequences.insert(current);
        return;
    }
    if (index == s.length()) {
        return;
    }
    generateAllSubsequences(subsequences, s, current + s[index], index + 1, k);
    generateAllSubsequences(subsequences, s, current, index + 1, k);
}

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n, k, m;
        cin >> n >> k >> m;

        string st;
        cin >> st;

        string s = "";

        for (int i = 0; i < n * k; i++) {
            s += 'a' + (i % k);
        }

        set<string> subsequences;
        generateSubsequences(subsequences, s, "", 0, n, k);

        set<string> orig;
        generateAllSubsequences(orig, st, "", 0, k);

        set<string> missingSubsequences;
        for (const auto& subseq : subsequences) {
            if (orig.find(subseq) == orig.end()) {
                missingSubsequences.insert(subseq);
                break;
            }
        }

        // cout << "Missing subsequences for which the answer is NO:" << endl;
        

        if (orig.size() == subsequences.size()) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
            for (const auto& missingSubseq : missingSubsequences) {
            cout << missingSubseq << endl;
        }
        }
    }

    return 0;
}


Is this code correct not considering TLE?
→ Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Div1D one-liner?

Use the usual interpretation of sequences as walks of $$$(+1, +1)$$$ and $$$(+1, -1)$$$. WLOG $$$n \geq m$$$, then the longest subsequence has length $$$(\min y) + m$$$ (minimum y-value plus down arrows count). Using the well-known catalan reflection argument gives a final answer of $$$\binom{n+m}{k} - \binom{n+m}{k-1}$$$, with an edge case at $$$k > \min(m,n)$$$.

243676528

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

Can C be done with DP?

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

I guess people don't like to see what I wrote, and unfortunately I can't delete the comment (no option to do so), Treat this as a DELETED COMMENT.

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

Finally, I could make use of my squared office papers

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

Tilting round :/

A was a good & funny problem. I only got the greedy after thinking through the naive DP over and over and realizing that it can be transformed to greedy.

B, I knew that the problem was basically just this, but it seemed like overkill. Plus, I hadn't actually solved it so I didn't feel like copying somebody else's code. So I over-engineered a terrible set + segtree solution with 5 WA's under my belt B)

C, I literally got the main observation within minutes, and worked out the formula shortly thereafter. Spent 30-40 minutes not being able to implement goddamn complex number arithmetic.

I asked ChatGPT this prompt:

give me a c++ library that supports multiplication, division, addition, and subtraction of numbers represented as a + b*sqrt(2). The underlying type should be a pair of long longs. 

To handle division, we're working over the field 999 999 893

and it AC'd first try.

For comparison, this was my upsolve: 243684462

and this was ChatGPT's library: 243685245

Lesson of the day? I don't know, massive skill issue :(

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

Any hint or counter test for my div2C??

Here is the submission 243684563

The idea was to split the string in groups where each group has at least one of each first k letters. For example "aabbccbbaaaacb" will split into aabbc-cbba-aaacb. If there is more than or equal to n groups, then ans is yes. Otherwise, no. So in case there are less than n groups, the string could be formed using the last char of each group, and complete the string with the first char wich is not present in the last group. Example: abc-cba-ab => would be c,a,[c]. the last one is c because it is not present in the last group.

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

    Just because a stupid error like:

              // int cte=ans.size();
          for(int i=0;i<n-ans.size();i++){
               ans.pb(cc);
          }

    I needed to use a constant var for ans.size() :'/

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

    Can you look into this submission? 244387004.

    I too had the same exact logic. In the above submission I used a set to keep track of found alphabets.

    Later, I did it with a bool array and a variable for size. 244388047

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

Hi, my problem B during the System test doesn't test again for the main test. After I woke up this morning, I saw my score had been minus but problem B wasn't in the main test. I tried to submit again with that same code and the code seems to be AC (I didn't get hacked or sth). MikeMirzayanov yash_daga Can you help me please?

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

WHERE IS MY B? ⚈₃⚈

→ Reply
»
10 months ago, # |
  Vote: I like it +3 Vote: I do not like it
Fun Fact :)
→ Reply
»
10 months ago, # |
  Vote: I like it +1 Vote: I do not like it

The pretest of B is weak resulting in many people got hacked and fst.

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

243558075 I solved question A, the pretest passed, and didn't get hacked, but the final settlement showed that only BCD was done, A didn't show "Accept",. I then handed over the same code, which was Accept, why?

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

MikeMirzayanov In the last DIV2 921 my submission for C shows pretests passed , but it neither shows AC nor FST on the final standings . Can you please check once . I solved 3 problems but it shows only 2 problem solved . https://codeforces.me/contest/1925/submission/243641450

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

PROBLEM B-> DIV 2 void solve() { int a, b; cin >> a >> b; int temp = a / b; int num1 = temp — 1; int num2 = temp + 1; if (a % temp == 0) { cout << temp << endl; } else if (a % num1 == 0) { cout << num1 << endl; } else if (a % num2 == 0) { cout << num2 << endl; } else { cout << 1 << endl; } } why this sol is getting WA on testcase 2 on 94th

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

I've got abrupt rating changes in this round 912 div2. kindly see to this image

yash_daga please solve this issue

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

    I do have same issue, unexpected rating change for my result. Hope this will be fixed.

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

Simple solution for DIV 2D 

        int n, m, k;
        cin >> n >> m >> k;
        int a,b,fi,f = 0;
        for(int i = 0; i < m; i++){
            cin >> a >> b >> fi;
            f+=fi;
            f%=mod;
        }
        int num =( n * (n - 1)/2ll) % mod;
        int sum = ((((k * f) % mod * binexp(num, k - 1)) % mod) + (((k * (k - 1))/2ll % mod * binexp(num, k - 2)) % mod * m) % mod) % mod;
        num = binexp(num, k);
        num = binexp(num, mod - 2);
        sum = ((sum * num) % mod);
        cout << sum << endl;
→ Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Good contest!

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

Anyone using sqrt decomposition to solve div2 problem E? I divide the sequence into $$$\lceil\sqrt n\rceil$$$ blocks, with each block at most $$$\lceil\sqrt n\rceil$$$ length (the last block is cutoff to a lower size). Then for each insertion of harbour, I find its left harbour $$$l$$$ and right harbour $$$r$$$ and then update the blocks in $$$[l,r]$$$; for each query $$$[l,r]$$$, I also retrieve the information in blocks in $$$[l,r]$$$. I think it should cost $$$O(q\sqrt n)$$$ and should get passed. However I got time limit exceeded: https://codeforces.me/contest/1925/submission/243770890. Could anyone help?

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

yash_daga, JaySharma1048576 sir orzzz

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

c was very enjoyable

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

The Contest was really enjoyable

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

The fact that X was not sorted in B is pure evil. Why would anyone create and approve such a version?

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

can someone tell me in which test case my code is failing?

void solve(){

int n,k,m;
cin>>n>>k>>m;
string s;
cin>>s;
int a[k]={0};
for(int i=0;i<m;i++){
    a[s[i]-'a']++;
}
for(int i=0;i<k;i++){
    if(a[i]<n){
        cout<<"NO"<<endl;
        for(int j=0;j<n;j++){
            cout<<char('a'+i);
        }
        cout<<endl;
        return;
    } 
}
vector<int>b(k,0);
for(int i=0;i<m;i++){

        int c=s[i]-'a';
        b[c]++;
        a[c]--;
        for(int j=0;j<k;j++){
            if(a[j]<(n-b[c])){
                // cout<<j<<" "<<c<<endl;
                cout<<"NO"<<endl;
                for(int idx=0;idx<b[c];idx++){
                    cout<<char('a'+c);
                }
                for(int idx=0;idx<n-b[c];idx++){
                    cout<<char('a'+j);
                }
                cout<<endl;
                return;
            }
        }

}
cout<<"YES"<<endl;
→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't really get why I was being downvoted.

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

      because of the way you wrote the code in your comment, the first few lines have a very large font size , and the rest are very small with no ne lines for each statement , it's not readable and it takes up a lot of space.it's a common practice to put your code in a spoiler

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

      And also you can send your code as a link

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

maybe sample of div1F should be t=2 yash_daga

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

Will 1 1 1 b be a valid testcase for Div.2 C?

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

Disclaimer

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

Hey folks, here is the solution video to the problems A to E (Div 2) of the above contest for those of you who'd like to upsolve them or reflect upon alternative techniques to solution etc. The video stresses upon the intuitions to solve the problems mostly from scratch. I believe this will benefit budding CPers who're trying to level up, and it shall inspire them to do better in upcoming contests. I'll try to consistently post videos on some of the upcoming contests and would be excited to see the community grow together! See you all! Feel free to write to me about any doubts/issues/feedback. Thanks!

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

For div2C/div1A, Can anyone please tell why am I getting memory limit exceeded on this submission https://codeforces.me/contest/1924/submission/244323304

→ Reply