GlebsHP's blog

By GlebsHP, history, 20 months ago, In English

Hello, Codeforces!

Zlobober and I are glad to invite you to compete in Nebius Welcome Round (Div. 1 + Div. 2) that will start on 12.03.2023 17:35 (Московское время). The round will be rated for everyone and will feature 8 problems that you will have 2 hours to solve.

I feel really thrilled and excited about this round as this is the first time I put so much effort in a Codeforces contest since I quit being a round coordinator in December 2016 (wow, that was so long ago)!

We conduct this round to have some fun and we also hope to find some great candidates to join Nebius team. Solving 5+ problems in our round will be a good result and will count as one of the coding interviews. Apart from that top 25 contestants and 25 random contestants placed 26-200 will receive a branded Nebius t-shirt!

Some information about Nebius. I have joined this new start-up in cloud technologies in November as a head of Compute & Network Services. It's an international spin-off of Yandex cloud business with offices in Amsterdam, Belgrade and Tel Aviv. We offer strategic partnerships to leading companies around the world, empowering them to create their own local cloud hyperscaler platforms and become trustworthy providers of cloud services and technologies in their own regions.

We know that competitive programming makes great engineers. It boosts your algorithms and coding skills, teaches you to write a working and efficient code. We aim to hire a lot of backend software engineers for all parts of our cloud technology stack that ranges from hypervisor and network to data warehouse and machine learning.

Here you can check Nebius website and open positions. If you feel interested in joining Nebius as a full-time employee, go on and fill the form.

Fill in the form →

Special thanks go to:

Fingers crossed all will be well, you will enjoy the round and we will be back with a new one in several months!

UPD2 The scoring distribution is 500 — 1000 — 1000 — 1500 — 2000 — 2750 — 3500 — 3500.

UPD3 The editorial is here!

UPD4 Congratulations to winners!

1-st place: jiangly

2-nd place: tourist

3-rd place: Um_nik

4-th place: isaf27

5-th place: Ormlis

UPD5 T-shirts winners!

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

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

Auto comment: topic has been updated by GlebsHP (previous revision, new revision, compare).

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

Make sure to have strong pretests this time ;)

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

Woah, Glebs and Zlobober. I haven't seen these two names in a long time.

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

Cool! Will this contest be rated for everyone?

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

How to solve Div2E/Div1C ? my idea was to sort the vector of vectors based on the max value of every vector and in case of equality i sort them by the one with the less number of inversions ,, i felt it is correct but getting WA on test2

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

    Actually you did it correct but you did not check for the case where n==1

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

      Can you specify the case more clearly ? because my solution just works very well with small test cases

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

    Wrong blog

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

No testers this time?

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

There appears to be a conflict with Atcoder Regular Contest 158. Pushing back the start of the round by 30 minutes will avoid the conflict.

Link to round: https://atcoder.jp/contests/arc158

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

Hoping to become specialist in this round, have been trying for specialist for quite a long time now, every time I was close there was one contest that would bring me down, this time for the past 5 contests, I have been gaining +ve delta, I am at my all time highest rating, need +23 to get to specialist. Sometimes, it demotivates me that I am not able to hit specialist despite all my other friends are already specialist but at the end of day, it's all about learning new topics and loving problem solving....

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

Why is this round (and some others) not numbered?

»
20 months ago, # |
  Vote: I like it -33 Vote: I do not like it

I don't even wan't to waste my time on these contests they are very hard.
Only one problem can be done hardly ever.
I advise you to not waste your time in this and help me with my " I wan't Div.5 " campaign.

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

Make sure to make the first question easy so that number of participants who solve the first question increases.

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

    As long as it is a good problem, Doesn't' care about the difficulty to be honest , i will solve it anyways.

»
20 months ago, # |
Rev. 6   Vote: I like it -60 Vote: I do not like it

Nebius is an israeli company, so i will boycott the contest. I hope all arab do this as well

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

Auto comment: topic has been updated by GlebsHP (previous revision, new revision, compare).

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

Hi. Is it a requirement to move to one of Belgrade, Amsterdam or Tel Aviv in case of job offer?

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

At my first glance, I read the round as Newbie Welcome Round — simple and friendly problems to welcome new people join Codeforces.

»
20 months ago, # |
  Vote: I like it -61 Vote: I do not like it

Will there be some classical problems?

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

Let's gooooooooooooo

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

When can we expect to see the score distribution?

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

8 problems in 2 hours!?

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

As a first-time tester, I'm sad I can't participate:(

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

    u will be much happier, when you will get salary.... xD

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

      Testers don't get paid

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

        as a new account you know that... and even after participating in around 100 contests, I don't know that.

        My whole life is a lie...

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

magga orz

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

No Score Distribution ?

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

No Score Distribution?

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

Scores distribution???

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

Auto comment: topic has been updated by GlebsHP (previous revision, new revision, compare).

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

As a tester, I'm really happy to test this contest. Zlobober's codes are super straightforward and easy to understand so I studied his codes when I was a candidate master. And Finally, I could become a master and His codes were really helpful to be a master.

Zlobober is my eternal idol, and I am really proud to test his contest.

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

Please, Let me become GrandMaster!

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

D is the Worst Problem I Have Ever Seen!..

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

    Yeah just concatenation of two different trivial problems :p

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

      Which problems?

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

        Find minimum, and find maximum. Both are trivial but asking for printing them separately with space is obviously a new problem.

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

    This problem teaches to write stress test

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

is problem C literally just luck?

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

    I guessed on the upper bound of the triangle number to search and passed pretests, so I'd say yes it was possible to be lucky. Although I feel like there was some closed form solution to find the minimum triangle number in O(1), I couldn't find it

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

    Sum $$$1 + 2 + 3 + ... + 2n = ((2n+1) \cdot 2n) / 2 = n \cdot (2n+1)$$$ thus $$$mod$$$ $$$n$$$ you did a cycle.

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

      I was lost making maths equations in first 45 minutes than realized there is a cycle :)

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

How to solve C ?? :((

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

    Basically the problem asks for if there exists a value $$$1\leq i\leq p$$$ such that $$$x + \frac{i (i+1)}{2}$$$ is divisible by $$$n$$$.

    Since For $$$i>n$$$ we can break the fraction into something like $$$\frac{(an+b)(an+b+1)}{2}$$$ you know testing $$$i$$$ until $$$n$$$ will be enough because you think it's just a repeating pattern afterwards — no, don't forget there is a 2 in the denominator, the pattern length can be as long as $$$2n$$$.

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

    Just check that when f is 2*n then it will come back to its original position.

    So run a loop from 1 to 2n and check

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

    My approach:

    Given $$$f$$$, the displacement is $$$\frac{f(f + 1)}{2}$$$. We want $$$x + \frac{f(f + 1)}{2} \equiv 0 \pmod n$$$. But this is equivalent to the existence of $$$q$$$ for which $$$x + \frac{f(f + 1)}{2} = qn \iff 2x + f(f + 1) = 2qn$$$. So we can simply try each value of $$$f$$$ from $$$1$$$ to $$$\min (2n, p)$$$ to see if $$$2x + f(f + 1) \equiv 0 \pmod {2n}$$$. We don't need to check beyond $$$2n$$$ because the LHS only contains multiplications and additions, which are invariant under modulo, i.e., trying $$$f$$$ yields the same result as trying $$$f \bmod (2n)$$$.

    (Note that division is not modulo-invariant, so trying $$$x + \frac{f(f + 1)}{2}$$$ for $$$f$$$ from $$$1$$$ to $$$n$$$ is not sufficient; you have to try until $$$2n$$$)

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

ImplementationForces all the way

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

    Personal take: ImplementationForces sometimes is actually good! Many real-life problem only require brute-force, yet hard solutions. ICPC-style contests also features many implementation-heavy problems. You do not need crazy algorithms or math knowledge to solve C,D, yet the amount of solves are perfect for problems of that level. Stress testing for D to find the exact solution is also a skill we need to have in real-life programming... The problems are also not misleading, so the only person that you can blame if you WA is you, right?

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

What was the logic for C ??

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

    Math knowledge: Sum from 1 to N is N (N + 1) / 2.

    Modulo knowledge: T (T + 1) mod N = (T + N) (T + N + 1) mod N

    Therefore, just check I from 1 to N for I * (I + 1) / 2 + X mod N == 0.

    That's what I thought, but WA on case something... change for from 1 to N to 1 to 2 * N works, but I don't understand how :D

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

      Because if N=2 for example, the sum from 1 to 2 is not 0 mod 2(due to the over 2 at the bottom)

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

      Just check that when f is 2*n then it will come back to its original position. So run a loop from 1 to 2n.

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

      Because in congruent equations, from I * (I + 1) / 2 + X == 0 mod N, you can obtain the equivalent equation by multiplying everything by 2 (including the mod). Thus it will be equivalent with I * (I + 1) + 2*X == 0 mod 2*N. But now you have to check all possible remainder after division by 2*N.

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

      My intuition behind it is because of something like this :

      If $$$\frac{d(d+1)}{2} mod N = T$$$, then at some point, it will produce some modulo cycle (e.g. adding movement with the value of $$$d_1$$$ will results in the same finish point for another value of $$$d_2$$$ for some value $$$d_1 < d_2$$$)

      And the cycle will repeats every $$$2N$$$ times. Because when $$$d = 2N$$$, then the value of $$$\frac{d(d+1)}{2}$$$ will be $$$\frac{2N(2N+1)}{2} mod N$$$ or $$$N(2N+1) mod N = 0$$$ because $$$N(2N+1)$$$ is a multiple of $$$N$$$

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

Hope my annealing simulation will pass systests in E.

Upd: it did!

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

How to solve E faster than (2^n)*(n^2)?

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

so for A my idea was to alternate with the longest side so it'll double up and reduce one and if both inputs share same pairty it's double

why didn't this pass ? ~~~~~ Your code here...

int a = sc.nextInt(); int b = sc.nextInt();

if(a == 0 || b == 0)
     {
         int res = Math.max(Math.abs(a) , Math.abs(b));
         System.out.println(res+res-1);
     }
     else
     {
        int x =  Math.max(Math.abs(a) , Math.abs(b));
        int y =  Math.min(Math.abs(a) , Math.abs(b));

           if((x+y) % 2 == 0)
           System.out.println(x+x);
        else
           System.out.println(x+(x-1));
     }

~~~~~

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

    It will always be x+(x-1) if x > y I think, because in the last step you reached the destination

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

Oh no! I have been writing question D, but it continues to WA on pretest 5. Can anyone explain that? thanks!

My idea is to find two consecutive $$$1$$$ in a row and divide them into a group for the minimum value. For the maximum value, divide $$$01$$$ and $$$10$$$ into one group, in addition, divide $$$00$$$ into one group, and group the rest separately. If the number is not enough, divide the two into a group.

my code: https://mirror.codeforces.com/contest/1804/submission/197124751

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

Why was the rating change predictor( carrot or CF-Predictor ) not working for this contest ??

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

could someone please tell me ,why am i getting WA on this submission 197128613

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

rainboy finally rainboyed a contest, by being the only one to solve the hardest problem. Congrats!

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

How to solve D?

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

Auto comment: topic has been updated by GlebsHP (previous revision, new revision, compare).

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

One of the nicest contests in a while. Very cool problems!

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

D was looking doable but i couldn't finish it :(

»
20 months ago, # |
  Vote: I like it -24 Vote: I do not like it

The worst D problem I've ever seen

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

this user BFU-marve is submiting in assembly, is this allowed?

»
20 months ago, # |
Rev. 7   Vote: I like it +15 Vote: I do not like it

Solved A-D. I passed pretest of E but I think my solution will be very likely getting FST. If it passed system test I'll get a large positive delta.

A: First, WLOG we can assume a>=0, b>=0 (by setting a=abs(a), b=abs(b)), and by looking for small cases we can get ans=a+b+max(0,abs(a-b)-1).

B: The problem is equvalent to "each pack of vaccines can be used on some patients with arrive time {t1, t2, ..., t_m}, where m<=k and t_m-t1<=w+d". Thus we can solve by greedy by finding maximal blocks of patients where they can get a same pack of vaccines.

C: Force f is good iff f*(f+1)/2 % n = (n-x) % n. Because (f+2*n)*(f+2*n+1)/2=f*(f+1)/2+n*(2*f+2*n+1), ( f*(f+1)/2 % n ) has a period of 2*n, so we only need to check for 1<=f<=min(2*n,p).

D: Consider for each floor separately. We need to put m/4 double-rooms at some places of the floor. Let the total count of bright windows of this floor is L, and the count of "11" double-rooms is t, then the number of occupied rooms is L-t. Therefore we need to minimize and maximize t. For maximization, we need to check every maximal block of consecutive 1s, and for minimization, we need to check every maximal block without "11". Be careful that we need to adjust t into range [0, m/4].

E: If there's a solution, we need to find a simple cycle in the graph, where the distance of every node and the cycle is at most 1. I used brute DFS to find the cycle, and it passed the pretests, but I think it could get TLE on some other tests.

Update: Now my submission of E has passed system test.

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

    For problem E, i don't think you solution is correct.

    Take care of this testcase:

    7 8
    1 2 
    2 3
    3 1
    1 4
    4 5
    5 6
    6 7
    7 5
    

    The node $$$4$$$ can directs the calls only on one side. Am i missing something?

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

    for problem B ... my idea was to let the patients wait as long as possible by add arrival time with w and make it the start of first session and add d to start time and make it the end of session ...... so every patient within that time slot get vaccinated ...... here's my submission can anyone tell me where i went wrong ?

    https://mirror.codeforces.com/contest/1804/submission/197143526

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

      You shouldn't do ans+=cnt/k because you will waste some vaccines which you could open them later. In fact you need to break the loop when cnt==k.

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

A VERY intresting problem C. Thanks!

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

Problem D : The Prince Of Ad-Hocs

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

Why my problem C skipped? I write it myself.It is easy for me.May be it is too short so it easily looks similar with others code?

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

Please, for the love of God, do not call an undirected edge a direct connection in the future :D

Each direct connection between a pair of distinct servers allows bidirectional transmission of information between these two servers.

Great contest overall, btw!

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

C has shitty pretests

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

wish me luck to become specailist after rating change.

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

Why did my code fail for problem D? Did I fail to consider an edge case or was my logic simply incorrect?

My idea for calculating min : If there are two lit up windows next to each other and we haven't hit the max amount of double apartments, assume it is a double apartment. Otherwise, treat it as a single apartment. And then, once I hit the max value for single apartments I treated every next pair of windows as a double apartment, and the same thing for single apartments.

My idea for calculating max : If there are two dim windows next to each other and we haven't hit the max amount of double apartments, assume it is a double apartment. If there is one dim window and a lit up window next to each other, treat it as a double apartment. Otherwise, treat it as a single apartment. And then, once I hit the max value for single apartments I treated every next pair of windows as a double apartment, and the same thing for single apartments.

My code : https://mirror.codeforces.com/contest/1804/submission/197105009

Thanks in advance for help.

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

    Try this:

    1 12
    110001111111
    

    output:

    6 8
    

    explaination:

    |11|0|0|0|11|11|1|1|1
    
    • »
      »
      »
      20 months ago, # ^ |
      Rev. 3   Vote: I like it +1 Vote: I do not like it

      Thank you very much I understand now.

      Int overflow issue with code, should have just accepted input as a string.

      Appreciate the help.

      Edit: still getting WA on test case 3 even after fixing input method. What else is wrong? code now works for your example case.

      Edit: new code https://mirror.codeforces.com/contest/1804/submission/197135065

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

        Try this counter example:

        1 100
        0110001100110000110110111000001000010100000011011100011100110001011100101011010010010110110010000101
        

        Answer:

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

        And these:

        1 60
        101000011101110101111010011110110010001010000110111111111000
        

        Answer:

        22 34
        
        1 20
        11111100110111111110
        

        Answer:

        11 15
        
»
20 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Didn't like B, but C was cool ;)

»
20 months ago, # |
Rev. 3   Vote: I like it -10 Vote: I do not like it

Why I get wa on pretest 2 in that code in problem A:

https://mirror.codeforces.com/contest/1804/submission/197096441

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

I very much liked E, F and H!

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

This is the best contest I have ever seen, I guess. Here are my approaches:

Solution for A
Solution for B
Solution for C

I think this is a really good contest. Thanks for all the efforts. Upvoted :D

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

Nice E!And C,D are also interesting.

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

I have no idea why my C (197116314) got accepted. Pure luck I think.

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

    You'll find that the task is just find whether there's an $$$y$$$ that $$$\frac{y(y+1)}{2}+x\equiv 0\pmod n$$$.

    If n is odd,it's obvious that there's no influence to calculate with $$$y$$$ or $$$y\bmod n$$$,using $$$\frac{y(y+1)}{2}$$$ or $$$2\times(n-x)$$$ because 2 has its inverse.In that case since you find one,then it is correct and ends with f=0.So it's $$$O(n)$$$.

    If n is even,it goes a bit complex.Set y as $$$kn+b$$$,where $$$1\le b\le n$$$,then recalculate the left and you'll get $$$\frac{k}{2}n+\frac{b(b+1)}{2}+x$$$,and in the first check both part were doubled so $$$+\frac n2$$$ has no influence.Then it has only 2 situations depending on $$$k\bmod 2$$$,so f could only be $$$0$$$ or $$$1$$$ and there's a result.Also it's $$$O(n)$$$

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

Am I the only one, who thought that Question C was easier than Question B?

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

    You managed to dodge the wrath of test case 4 on problem D. Congo

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

Link:- https://mirror.codeforces.com/contest/1804/submission/197135076 my solution for B question. It's giving TLE for test case 37. I think the time complexity of above code is 2*n which is O(N) but why I am still getting TLE. Please help me out.

»
20 months ago, # |
Rev. 3   Vote: I like it -39 Vote: I do not like it

ImplementationForces, ObservationForces, LuckForces all satisfy today's contest. What is going on with CF? No need to force for contest number instead I want quality over quantity. We want quality like older contests, now it's like we r just lucky to get through a ques or not at all. Not learning much stuff from contests nowadays. Pls just decrease the contests numbers and make some pretty questions. :/ pls

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

    I wouldn't join you. Today's contest was actually impressive. If you say for A, A was greedy, for B, B was binary search, and for C, C was math. If you think that you guessed or smth else then you didn't learn bro unfortunately :)

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

      I know concepts were there, but no one can deny that older contests were fun, they were less but had good concepts, but i dont see much now. A was simple maths for most of us, B was binary search?, I did sliding window only :/, and regarding C huh, I cant comment bcz I was mad after getting to the logic there. But all have perspectives and I wish they just add some different problems.

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

        Yeah, sliding window is also one of the solutions; just to be quick and straightforward, I used binary search. I think for us, A B C don't focus on harder topics or other different topics(If I misunderstood you, sorry).

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

Can someone tell me the mistake in my logic of C ? https://mirror.codeforces.com/contest/1804/submission/197111331 Thanks in advance !!

I am checking for every cycle of n and updating the starting point after each operation. The moment a possibility arises inside p, or n goes beyond p, or a repetition in starting point arises(hence it is under O(n)), I am returning the answer. ( I know the simpler solution now, just want to understand mistake in my one)

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

    Well I couldn't understand your solution there. But I will try to explain an easier solution.

    Basically we have to go from sector x to 0. By selecting a force f the arrow moves (f*(f+1)/2)%n sectors ahead. Or it moves from x to x + (f*(f+1)/2) % n. So we need to find a particular f such that the resultant sector is 0. We can find this f by iterating over min(p,2*n) and checking for every number i whether it satisfies our condition

    (i*(i+1)/2)%n = (n-x)%n

    If the condition is satisfied we can be sure i is our answer.

    Why min(p,2*n)?

    Because the force f to be applied must be smaller than p. Also the remainders for the operation (i(i+1)/2 )%n repeats after every 2*n numbers for even n and it repeats after every n numbers for odd n. Hence if there is no number from 1 to 2*n which will satisfy our condition then there is guarantee that there will not be any number > 2*n which will satisfy the condition.

    My submission: https://mirror.codeforces.com/contest/1804/submission/197106694

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

      Can you explain how did you know that the pattern will repeat each 2 * N times

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

Fun fact: 173 submissions passed pretest and got FST(30.8% among all submissions which passed pretests) at 1804E - Routing. Maybe they didn't see $$$O(N^3*2^N)$$$ solutions could pass pretests :(.

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

Can anyone help me find out what's wrong with my code? It fails for the maximum part.

I first find all the '01' and '10'. Then I find '00' until there is no double size room remained. If after this process, we still have remain double size rooms. Then these rooms should be occuppied by '11'. It passes the visible part of pretest5.

Python Code

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

    for the maximum, let's pick the double size rooms, the only bad pick is 11 because we lose a 1, so we count how many good picks we can do:

    cnt = 0
    for (int i = 0; i + 1 < m; i++)
         if (s[i] != '1' || s[i + 1] != '1')
              i++, cnt++;
    

    then the numbers double size rooms left is max(0, m / 4 — cnt) each of these rooms will be 11 which means we will lose a 1. and to get the answer we just subtract this number from the number of ones in the string.

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

      Thank you. You are right, considering not picking '11' is enough.

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

      for your code, what would be the cnt and answer for input like 1 16 0010011111111111

      Is it right that cnt = 5 rm = max(0, 16/4 — 5) = 0 answer = 12 — 0 = 12?

      But I can get only 11: 00|10|01|11|11111111 +1 +1 +1 +8 = 11

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

    Finally, I find a failed case: 001001111111

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

PLEASE HELP ME, I dont know why my solution for C goes TLE if its o(N) only https://mirror.codeforces.com/contest/1804/submission/197134868

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

    The sum of $$$n$$$ over all test cases doesn't exceed $$$2\cdot 10^5$$$, but the sum of $$$p$$$ ($$$m$$$ in your code) can be very large.

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

      YES, but the loop is running till s which has max value 2e5. Oh you wanna say P * testcase will make it to TLE???

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

        Yes, but there are $$$10^4$$$ test cases, so the loop will run $$$2 \cdot 10^5 \cdot 10^4$$$ times in total in the worst case.

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

          I got your point, I fucked up I think so. It can easily be accepted I chose 2*n in place of 2e5.

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

How many CPU days do rating changes take? (I'm guessing they are not rolling out because of cheaters)

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

why problem A is the same problem with the same solution from another contest!!

1452A - Robot Program

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

    This happens on really easy problems quite a bit.

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

Why has my rating been decreased suddenly without any email or any error from 915?? And it's not showing rating of last two contest?? please reply

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

Just be notified that I'm being skipped for this contest due to the significantly coincides with jiangly's solutions 197093293 from mine 197126608 for problem F. Yeah the code is exactly the same to my surprise.

I suppose once figuring out the problem F, the solution is very limited: building graph with query stamp on the edge, writing a BFS lamdba and do several binary searches. These steps are independent, very standard which is easy to write the same code.

Finally, I don't think I have the ability to ask the round winner jiangly for the code sharing. Hope there will be a fair reply and judge, thanks.

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

      Lol, it's time to join Jiangly Fan Club!

  • »
    »
    20 months ago, # ^ |
    Rev. 3   Vote: I like it +55 Vote: I do not like it

    I just went through both submissions and I think they are similar. But I don't think they should be treated as plagiarization.

    Here are the reasons:

    For this problem F, there are 3 parts, graph building from input, binary search to get the ans, BFS to get the max dis.

    From submission 181795376, we can see the graph building and BFS are exactly the same,

    From submission 122792860, we can see the binary search part is exactly the same.

    So I think the similarity is just a coincidence just because sd0061 and jiangly having similar coding styles.

    Besides that, I also don't think Codeforces is doing the right thing when 2 similar codes are found, Codeforces skipped sd0061 but not jiangly. I think if such a case is found, both side should be skipped.(in this particular case, I think both of them are innocent and should not be skipped)

  • »
    »
    20 months ago, # ^ |
    Rev. 3   Vote: I like it +59 Vote: I do not like it

    Problems are similar?

    Mike: It's very common and normal.

    Solutions are similar?

    Mike: Cheater!

    P.S. As both of jiangly and tourist's coding style are very beautiful, lots of coders learn their coding style, this thing will happen again and again in the future.

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

    If we just read the author's submission history that the coding style is consistent. And I think one seemingly possible reason (apart from code logic) for sd0061's code being detected as duplicate code of jiangly's code is that both:

    1. use std:: prefix
    2. use lambda instead of global defined functions

    Basically, if two coders use mordern c++ features and have a good coding style, once the room for algorithm implementation is limited, it's quite possible that the codes reads similar. We should allow human re-evaluation for such cases, not blindly skip the submissions.

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

Rating have rolled back for this round. What is the reason???

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

    They rolled back like 5 contests yesterday and they are runnung plagiarism checks which take a pretty long time, the ratings for others graduallly came back so i guess this one will too

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

      I submitted my code once after the game, and they all passed the evaluation.

      But the game showed that I was wrong

      Because they are runnung plagiarism checks which take a pretty long time?

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

Auto comment: topic has been updated by GlebsHP (previous revision, new revision, compare).

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

Congratulations to tshirts winners! In a few weeks, you will be contacted via private messages with instructions to receive your prize.

As usual, we used the following two scripts for generating random winners, seed is the score of the winner.

get_tshirts.py
randgen.cpp
List place Contest Rank Name
1 1804 1 jiangly
2 1804 2 tourist
3 1804 3 Um_nik
4 1804 4 isaf27
5 1804 5 Ormlis
6 1804 6 dorijanlendvaj
7 1804 7 maroonrk
8 1804 8 Petr
9 1804 9 gamegame
10 1804 10 ksun48
11 1804 11 platelets
12 1804 12 yosupo
13 1804 13 A-SOUL_Bella
14 1804 14 jeroenodb
15 1804 15 tatyam
16 1804 16 998kover
17 1804 17 5ak
18 1804 18 gyh20
19 1804 19 oleh1421
20 1804 20 heno239
21 1804 21 milisav
22 1804 22 A_G
23 1804 23 jtnydv25
24 1804 24 yzc2005
25 1804 25 kshitij_sodani
26 1804 26 Maksim1744
28 1804 28 Rubikun
31 1804 31 liuhengxi
65 1804 65 elazarkoren
67 1804 67 hitonanode
71 1804 71 tokusakurai
80 1804 80 stepanov.aa
85 1804 85 Ooops_no
87 1804 87 tfg
91 1804 91 KaguyaH
94 1804 94 kevinxiehk
104 1804 104 BeyondHeaven
114 1804 114 dlalswp25
126 1804 126 Golovanov399
133 1804 133 JaeminPark
142 1804 142 TheScrasse
147 1804 147 cai_lw
148 1804 147 Leilaqwq
158 1804 158 swiftc
159 1804 159 PurpleCrayon
166 1804 166 QwQcOrZ
175 1804 175 briansu
178 1804 177 ParsaS
179 1804 179 JettyOller
181 1804 181 jonathanirvings
»
17 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Just received this.

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

Problems are good but statements are way too long