Stepavly's blog

Codeforces Round #725 (Div. 3)
By Stepavly, 3 years ago, translation, In English

Hello, Codeforces!

UPD: Since the round seems a little more complicated than usual after testing, we extended the round length by 15 minutes.

<almost-copy-pasted-part>

Hello! Codeforces Round #725 (Div. 3) will start at Jun/10/2021 17:35 (Moscow time). You will be offered 7 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating 1600 or higher, can register for the round unofficially. The round will be hosted by rules of educational rounds (extended ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round, it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

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

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

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 trusted participants of the third division, you must:

  • take part in at least two 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, then the round will be rated for you.

The problems for this round were invented by MikeMirzayanov, Supermagzzz and Stepavly.

Thanks to Fly_37, -is-this-fft-, A_Le_K, sstrong, ANZ, hocky, Lihwy, Sho, ASIXER, songsinger, OlegZubkov, AlexFetisov, darkkcyan, ivanzuki, kocko, Gassa for help with testing the round.

Thanks to MikeMirzayanov for platforms and coordination of our work. Good luck!

</almost-copy-pasted-part>

UPD: Editorial

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

Comments Comments (194)
| Write comment?
»
3 years ago, # |
  Vote: I like it +77 Vote: I do not like it

It's my first time as a blue coder in a (Div 3) contest. I was waiting for this for a long time. Best wishes to all the rated contestants.

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

    Same here, I feel like our individual hard work has finally paid off. Good Luck for purple. :D

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

      I'm try my best to reach the blue coder. But failed again and again. I didn't lose hope. I'm still trying. The main painful things, I solve problem after contest, But contest time I feel stressed. What should I do? any advise?

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

        Have patience And keep trying . You are not alone in this

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

        There's no need to be stressful. Focus more on problem solving than rating. That's what I'd say. When I thought of reaching expert I stayed cyan but when I focused on solving till D, positive delta was complimentary. I made silly mistakes in some contests and got AC right after the contest ended. I think that's a part of the learning curve too.

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

          I think, It will work. Although I've done silly mistake again in problem D and got AC right after contest ended, But I'm satisfied. I only focused in solving problem. Next time, I will keep it mind. Thanks.

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

        Don't lose hope. In your stage, I suggest practice more Light OJ, CF (C, D) problems. Try to practice more and more binary search, (bfs, dfs), number theory, and DP problems. Here is a native Bangla Youtube channel Bangladesh Advanced Computing Society — BACS that may help you.

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

      Hoping for positive delta this time.

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

    Wow! You have a nice participation graph — you are the first person I see that participated in 1970. How was it back then? :)

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

    same :)

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

Round 719, yes I have arrived in past.

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

Hello! Codeforces Round #719 (Div. 3) will start at Wednesday, May 5, 2021 at 20:05UTC+5.5.
<almost-copy-pasted-part>
I think it should be <fully-copy-pasted-part> instead

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

I am missing vovuh for Div-3 rounds.

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

    I guess vovuh has betrayed div3, Curious why he is staying loyal to educational rounds xd

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

      I wouldn't say I betrayed Div.3, if I got the meaning of this word in your sentence correctly. Just a combination of circumstances forced me to stop doing them. I'm also not doing Educational Rounds, though. Guys just take my problems from time to time (rarely), that's all.

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

        I see. But Still, we miss you in div3 rounds.

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

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

Any motivational lines please?

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

I waited so long for this day! At last, unrated in div3 for the very first time *_* Cant't wait more for the contest.

→ Reply
»
3 years ago, # |
  Vote: I like it -9 Vote: I do not like it

finaaly i realy miss div 3 contest :(

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

Aiming for specialist.

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

UPD: Since the round seems a little more complicated than usual after testing, we extended the round length by 15 minutes.
Hard problems coming up

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

Suddenly my rating changed to 1601 from 1598. Will the round be still rated for me lol?

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

Wow!!!! This is the first unrated contest for me!!!

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

fingers crossed no technical issues for this contest

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

Since the round seems a little more complicated than usual after testing, we extended the round length by 15 minutes.

This is super sus.

→ Reply
»
3 years ago, # |
  Vote: I like it -27 Vote: I do not like it

E is the worst problem I've seen.

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

    Why?

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

    Why? It was my idea of the problem. I found this problem to be a rare case of not a math puzzle, but rather a programming problem (and not on standard algorithms). I think it is okay. The only issue: we didn't guess its correct position in the set.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it -20 Vote: I do not like it

      I think the input format was bad. But it is okay for the story

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

        Why? I think it is clear and natural. Also, it is easy to read in most programming languages. In my code (and I've read some others), I didn't find any complicated code to read the data.

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

        I disagree. I loved the problem and enjoyed solving it. The input format was all right.

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

      During pre-solving that was the best in the set for me :)

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

    [name changed]

    the name before: cmii02

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

      [name changed]

      the name before: cmii02

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

Sequence of problems should be A->B->C->F->D->G->E

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

I started implementing E and then it was while parsing the input when I realized that it was a bad idea..

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

My first time solving the entire contest

"the round seems a little more complicated than usual" must be a joke

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

    Weird flex, but okay

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

    Congrats. We based on the results of the testers. I am glad that the round was quite suitable for most of div3 participants.

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

      thanks Mike, it is really suitable for div3.

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

is F that easy more that 4K solved it sadly I have no time to see it :(

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

Very balanced round
B = C = D = E = F = G

Only A was sadly out of the pack

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

    Well, to be more precise

    Ranking by the amount of time I spent + penalty time

    D(44) > C(31) > G(28) > E(19) > F(8) > A(5) > B(4)

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

A moment of silence for those who were trying to solve D using Gcd to handle the No case

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

Is there a purely mathematical solution for G, I wasted an hour trying to fit the right formula but couldn't figure it out, then I realized there exists a thing called binary search.

Binary Search Solution
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    logic? or how you decide that x gifts can be made?

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

    If we take $$$N$$$ gift sets of type 1 ($$$a$$$ red, $$$b$$$ blue) and $$$M$$$ gift sets of type 2, then we want the maximum $$$N + M$$$ constrained by $$$Na + Mb \leq x$$$ and $$$Nb + Ma \leq y$$$, which are two lines. The optimal point is at the intersection of those two lines. So we get an $$$\mathcal O(1)$$$ solution.

    Submission

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

      Ah.. just recalled it from my linear programming course, thanks!

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

      Yeah, But I tried to solve them using simplex and get an WA, I think using Simplex here is OverRated.

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

        lol yea simplex was actually my first thought when reading the problem as well, but simplex can't find the optimal integer solution, just optimal solution in general.

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

      Oh, I've looked into your solution, that's much simpler then mine... I did coordinate transformation $$$N=K+G$$$ and $$$M=K-G$$$ so I could maximize $$$K$$$ without regards of $$$G$$$ (since $$$K=\frac{N+M}{2}$$$) and then needed to check for $$$K<G$$$ and $$$K<-G$$$. But judging from your submission I totally didn't need that transformation.

      I guess I did that, because I wasn't sure, that the ideal solution will be at the intersection. After performing the transformation it was obvious, that the solution will be either at the intersection or at $$$N=0$$$ or at $$$M=0$$$. But I still continued my calculations from there with the transformation which made it more laborious.

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

    Same with me.

    Except that I quickly decided that I'm too stupid for math and started to write binary search from the start

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

    I solved G with a logic/math solution similar to neal's first ac submission (he resubmitted with binary search uh oh) which is $$$\mathcal{O}(1)$$$. I'm not confident that it is correct (bcz I suck at proofs) but it seems to intuitively make sense. My general approach was as follows:

    Assign $$$\min(x, y)$$$ to $$$x$$$ and $$$\max(x, y)$$$ to $$$y$$$. Then, attempt to balance $$$x$$$ and $$$y$$$ by subtracting $$$\min(a, b)$$$ from $$$x$$$ and $$$\max(a, b)$$$ from $$$y$$$ until either $$$x$$$ and $$$y$$$ are balanced or $$$x$$$ has been exhausted. Then, evenly subtract the rest from $$$x$$$ and $$$y$$$ by alternating $$$a$$$ and $$$b$$$ (starting with $$$\min(a, b)$$$ for $$$x$$$ and $$$\max(a, b)$$$ for $$$y$$$). My solution code is below.

    pls hack this or smth

    Does anyone else have this solution?

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

I think Problem-F should be placed before Problem-D or may be also before Problem-C.

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

    can you give some hint for F

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

      use prefix sum idea

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

      First find no. of digits that will change from 1 to r & then find no. of digits that will change from 1 to l.
      And subtract them.

      You can check this solution — 119034121

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

      from 0 to 10 made by 11 change.
      from 0 to 100 made by 111 change.
      ...............

      so for 212 can just 2*111+1*11+2*1
      then ans = (from 0 to b)- (from 0 to a)

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

      Prefix sums are not necessary for this problem. See this: 118992669

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

WTF was the positioning of F. I read it when there was 1 minuite left!

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

problem D is bad itself(case consideration), and moreover, I had to change longlong->int and map->unordered_map to pass tl, G with ternary search with stupid trick can be easily passed, some other problems I can't remember, they weren't interesting, not very good round for me:(

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

    What is wrong with D? Probably, you just have bad implementation. My solution is short and clear, no corner cases. You see it is part of the programming skill to write in such a way that there are no corner cases and huge code.

    G is also my problem. I think it is good) Ternary search, probably, is wrong in this problem.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      it's just my opinion, I wasn't able to come up with a good solution, so I spent my nerves on consideration), also I think that G can be solved in that way is not really good, but most likely it will be hacked, I suppose. Anyway, most of the previous div3 rounds were more interesting for me, so...

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

      Agreed!!

      I wrote a poor code in D, but still fail to understand why my TLE submission got AC after changing a lots of heavy lines of if-else statement into single if-else statement.

      Does that affect the code somehow :-(

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

    What's wrong with case analysis? The fastest solution for D runs in 30 ms, how can you say the TL is was strict?

    But it would be nicer if the TL was 4-5 seconds or if ${T} was decreased to 1000 from 10000. This would allow solutions in slower languages to pass comfortably, without compromising the core idea.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      case analysis is boring:/, tl is just not enough strict for wrong solutions or on the contrary too strict if solutions using straight factorization are considered correct

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

    It can be tempting to say a round isn't very good because you found it difficult, or what you tried didn't work. A good round has a range of problems of different difficulties, not 7 easy problems that anyone can get. I think this round was good, because it had interesting, and in some cases unusual, problems, which were varied in difficulty.

    I struggled on G too because I tried ternary search. I got it wrong, and then had a different idea which worked. That's part of the fun.

    D I also got wrong initially because I missed a crucial pruning insight. Again, that's part of the fun.

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

      firstly it's just my(very important:)) opinion, secondly, I said nothing about difficulty, but I think you're right about the correlation between difficulty and fun. But in my opinion, that's not a such case

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

well that was embarrassing

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

Any hints for D?

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

    There are only two cases to consider to get both numbers a and b to the same number c: if operations are too much or little...

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

D ruined the contest for me.

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

Solving F but not solving D army !!

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

Here's my video of the contest (including solutions) on YouTube: https://www.youtube.com/watch?v=FXcIKhU_3IU

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

is it just me or the time-limits on D and memory -limits on E were strange for some reasons ?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  1. what is the trick for problem C.
  2. Help me in problem D where i am doing wrong. https://mirror.codeforces.com/contest/1538/submission/119067539
→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is C literally that easy? How to do it?

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

    binary search for the good range of all numbers >= a[i] excluding a[i] for each i

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

Problem E should be put in the position of the problem G.

And for new competitors, you don't need to solve these questions in default sequence, if you have solved problem i, the next problem you are going to solve is unsolved problem j that have maximum accepted users, j don't need to be i+1.

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

I solved C using point compression and segment tree, was there an easier solution?

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

    just sort it and use lower_bound and upper_bound for l — vec[i] and r — vec[i] for each index to the right

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

    Binary Search

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

      please explain

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

        let's say have 1 5 3 4 2 and l = 5, r = 8 sort -> (1 2 3 4 5) next iterate and for each element (from left to right) at index i, find 2 things:

        1) first greater or equal element index to l — vec[i](just c++ lower_bound function): index1

        2) first greater element index + 1 to r — vec[i](just upper_bound) both in [index + 1, end): index2

        for each element answer is index2 — index1. sum up all answers and get the final

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

    You can also use a 2 pointer approach.

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

      How? I tried but got stuck

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

        You can check my solution, but the idea is that you can sort the array and process it in order of increasing a[i]. Now you need to solve how many pairs are such that a[i] + a[j] <= X. If you start from the smallest a[i], all the numbers <= X — a[i] will be valid pairs. As you move to the next i, a[i] will increase, and the numbers <= X — a[i] will only decrease so you can use a pointer.

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

My greedy solution for G passed pretests, does it survive system testing?

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

How to prime factorize (count the number of prime factors) the two numbers in D in 2 seconds ?

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

    I precomputed the primes till $$$\sqrt{10^9}$$$ and then iterated over it code

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

    Use wheel factorization.

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

    Store all prime numbers upto $$$4e4 (sqrt(1e9))$$$ there are about $$$3000$$$ of them, then check only these numbers atlast check if there is a prime factor greater than $$$4e4$$$ (there can be atmost 1).

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

    First, we need primes <= sqrt(1e9), we have approximately 4000 primes You can do it by sieve. Then you can use those primes to factorize. Like this: for prime in primes, while(num % prime==0) { num/=p; power++;} do it until prime < sqrt(num). In the end if num > 1 then it is also a prime. Max count of prime can be approximately 13 for a number < 1e9. For each prime power count can be at max 28. So it will pass.

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

How to solve E ?

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

    We need store 3 first and 3 last character of each string, then merge them easily

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

I registerd yesterday and I did not get any ranking points, why?

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

    Registered yesterday as an Alt you mean. Well, I'd guess it's because you're not a Trusted Participant, but you must have read that from the announcement. But I guess you missed it.

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

In problem D when using int it is getting accepted but showing TLE for long long! why??

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

    Because long long eats up memory stack, you are not supposed to use long long everywhere, use it only when you suspect an overflow.

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

Pretty easy but my hands aren't fast enough to AC all :(

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

imagine all above Mike's comments written by radewoosh...

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

You can solve C using Dynamic segment tree!

Link

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

This is ridiculous, how the time limit for D is so strict for c++ but not for other language?

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

    Do you even understand what you're saying?

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

      I've just resubmit with c++17 and got accepted so this is a part of the unbalanced multi languages system?

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

        I think you just forgot that Long Long is often slow. Here is your code but with c(int x) in C++11.

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

          Thanks, I forgot that but why c++17 is faster than c++11 due to the same code no matter how I try to resummit with c++11 and it still got a TLE? Just wondering...

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

10^9forces

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

What is the expected time complexity of D?

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

Can anyone please explain me why in my function getPf changing getPf(int x) to getPf(ll x) gives TLE for question D

TLE code: 119084091

AC code: 119084144

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

    If there is no need in long long use int because long long is slower

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

Can anyone suggest me problems like F. Interesting Function.

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

119063957 119067741 119066275 check all solutions of these people they are the same ... They did this in all contests....

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

Is there any discrepancy in the test case for Problem C, This guy naitikvarshney has hacked more than 100 AC solution. MikeMirzayanov please look into the matter.

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

    Your code got hacked due to Arrays.sort() function which in worst case have O(n^2) time complexity.

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

      I was hacked by this since I used java's Arrays.sort() method, but when I reversed the input array before sorting, I got accepted. This is because the test case used in the hack was deliberately chosen for this java's specific implementation of dual pivot quick sort to run in its worst case, when nearly any other array could be sorted much faster. My submission where I reversed the array could easily be hacked as well by simply reversing the input, which is why I think something may need to be done about this. Either way, the Collections.sort() method will always run in O(NlogN), and will always be accepted.

      Solution without reversed array that got TLE: https://mirror.codeforces.com/contest/1538/submission/119093728

      Accepted solution with reversed array: https://mirror.codeforces.com/contest/1538/submission/119099990

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

119083149

Anybody, please help!

I am not able to figure out why I am getting TLE in question D https://mirror.codeforces.com/contest/1538/submission/119083149

I really appreciate any help you can provide.

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

    Instead of long long use int

    Got accepted in my case

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

      Thanks, worked

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

I kind of applied the same logic in D as mentioned in the editorial, but not able to pass the tests. Can anyone tell me what am I missing link

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

    missed the condition when a and b are equal and k!=1. My bad :(

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

119082014 for D i have calculated prime factors for both the numbers in O(sqrt n) then also giving tle.

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

Nice contest. I wish the authors of the tasks success in the future!

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

I personally believe the level of this contest was not exactly same as other Div 3 contests. Its difficulty level was somewhere between regular Div 3 and Div 2. Again, it's a personal opinion.

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

How come all the java submissions are being hacked (tl)by naitikvarshney, while the same solutions in C++ and python are working perfectly fine ?

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

Can someone tell what is wrong in this code of Bugaboo C — Submission I am not able to see testcase on which it went wrong.

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

Can anyone tell which corner case I am missing in the solution to problem D? I am getting WA on token 1021 of test case 2. Here's my link 119065848. Thanks.

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

For the first time I was able to solve 4 questions :)

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

I wasted more than 100 minutes on problem D and still couldn't solve the problem in the contest (WAs throughout), only to find out later that I had taken return type for a function (counting prime factors) as "bool" instead of "int" ! I have never felt so useless before lol

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

Do runtime errors count in wrong submissions?

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

    I think every error after the first test case counts as WA submission.

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

A bit confused, after how long will the ratings be updated? (also if someone can share blog post on codeforces which talks bit more on this)

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

    System testing hasn't started yet. First that'll happen and after it's finished the ratings are updated within the next hour or so.

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

      Hi, I'm not quite familiar with codeforces system. Could you please tell me when will the system testing begin?

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

        There isn't any specific time for system testing, it happens soon after the round is finished in Div.2 , and after the hacking phase is finished in Div.3 and edu contests

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

Hey! This is my first time giving a contest so I have a few doubts. My rating has not changed from 0 till now. I did successfully submit 2 ques near the end of contest. So will they not be counted cause I took too much time??

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

Hi ! MikeMirzayanov when will you update the rating?

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

I can't understand why this round was made unrated Can anyone explain me the reason. Thanks in advance.

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

I'm wondering about division system? Is it based on rating? If yes then how is div1 div2 and div3 divided?

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

    Kind of based on the rating of participants rated

    Div3 1600-
    Div2 1900- if there is a concurrent div1 round, 2100- otherwise.
    Div1 1900+

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

      Thanks for the information @WitchOfTruth

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

why E had so less submissions? I felt it easier than many other problems.

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

Why hasn't the Rating been updated

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

fahimfardous8 and Toxic_046 both account is mine. I tried to solve Codeforces #725 contest problem in both account.When I solved problems A,B then submttefd in both of my accounts.I apologise for that.I can give proof that both of the account is mine.

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

    It's still wrong even if both accounts are yours, you are essentially bypassing all the WA penalties. How do you expect CF to know which account belongs to which human on earth. If 2 accounts use the same solution, they should be penalised.

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

I have been accused of plagiarism against my own solutions. Please look into this.

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

？？？？？？？？？？？？where's my rating??????bro???????????

NO rating ??????????

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

Thank you to the authors for such a great contest! This contest helped me a lot to become specialist for the first time!! :D

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

Why are the problems for this round not getting rated???????????????

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

    Have you missed the announcement? It was a Div.3 contest. Rated only for greys/greens/cyans.

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

      Dude!!!! I mean the rating of the questions.

      → Reply