By KAN, 2 months ago, translation, In English

Hi all!

This weekend, at Nov/29/2020 10:05 (Moscow time) we will hold Codeforces Round 687. It is based on problems of Technocup 2021 Elimination Round 2 that will be held at the same time.

Technocup is a major olympiad for Russian-speaking high-school students, so if you fall into this category, please register at Technocup 2021 website and take part in the Elimination Round.

Div. 1 and Div.2 editions are open and rated for everyone. Register and enjoy the contests!

The problems authors are; amethyst0, eidan, Diegogrc, bensonlzl, Maripium, antontrygubO_o, and KAN. Thanks to antontrygubO_o and 300iq for their help in coordination. Also huge thanks to testers for their invaluable help: Golovanov399, rkm62, golions, dantrag, _cherry_, gigabuffoon, Andres_Alumets, firiexp, growup974, Nero, GGMU, K0u1e, Bench0310, dorijanlendvaj, Um_nik, thenymphsofdelphi, Merkurev, kokokostya, wucstdio, smile_boi, abhishhh1!

Have fun!

Thank you for participation! We hope you enjoyed the problems. Congratulations to winners!

Technocup 2021 - Elimination Round 2

  1. Kirill22
  2. fastmath
  3. VEGAnn
  4. alexxela12345
  5. solver777

Codeforces Round #687 (Div. 1, based on Technocup 2021 Elimination Round 2)

  1. ecnerwala
  2. ainta
  3. conflict
  4. al13n
  5. kort0n

Codeforces Round #687 (Div. 2, based on Technocup 2021 Elimination Round 2)

  1. gang_leader
  2. iLoveIOI
  3. Linqi05
  4. xaohu
  5. detect

Upd: Rating updates published.

UPD2: The editorial is published.

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

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

Notice the unusual start time!!!

»
2 months ago, # |
  Vote: I like it -44 Vote: I do not like it

Notice the unusual time.

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

Best of luck everyone.

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

please upvote me , i am getting too many downvotes !! please push me to a +ve side !!

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

push me to zero please!!!!!

»
2 months ago, # |
  Vote: I like it -59 Vote: I do not like it

Why the unusual start time?

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

    It is based on problems of Technocup 2021 Elimination Round 2 that will be held at the same time. So, it must be at the same time!

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

Today is my Birthday and I enjoyed testing this amazing round on my birthday. Problems are very very interesting. (May I get my gift now, you know what I want)

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

This competition is friendly for Chinese competitor! Thanks KAN!

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

    Yes, it's not only an unusual time but also a good time for us (Chinese), we needn't stay up until midnight. But unluckily I have no time to participate it.

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

Pacific time zone people are probably celebrating, lol, better than waking up at 6am in the morning.

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

    I'd prefer to take those rounds in 6am compared to the time when I normally need to be at work

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

So many red coders as authors N testers, Well I'm a little scared!!

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

I'm sorry to hear that. I will miss the contest. I will not at home tomorrow afternoon because I have to participate in a competition in my school. (-_-!)

Have fun and good luck!

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

Score distribution?

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

»
2 months ago, # |
  Vote: I like it -48 Vote: I do not like it

Is this rated??

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

Nice contest, thanks KAN and your team !!!

Goodluck to everyone ^_^

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

As a tester, doing it for the first time, I have to say that preparing a round seems like an enormous amount of work by the problemsetters and coordinator. Much more work than I imagined. Huge respect for everyone who makes rounds happen, even when something goes not as planned!

»
2 months ago, # |
  Vote: I like it -7 Vote: I do not like it

A great time for Chinese competitors! I won't miss this round :)

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

... please register at Technocup 2022 website and take part in the Elimination Round.

Do you mean Technocup 2021?

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

    Will i be rated ,if i register on that site . Also i am able to register in div2 and official , both contests.

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

In the techno cup round 1 my rating decreased sharply I hope to get my rating back in round 2 .

»
2 months ago, # |
  Vote: I like it -11 Vote: I do not like it

I just want to say good luck to everyone

»
2 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Can the string hash to O(1) to compare the dictionary order size

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

What will be the difficulty level of this contest (div2) ???

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

Thanks for starting contest not in dawn.

»
2 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Today is my birthday

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

To be honest every round is the birthday of ~50 people participating

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

Russian students are very lucky. They get introduced to programing at a very early age! As for us, country like Bangladesh India Pakistan, we rarely get to know what is programing before university! Hope one day it will be changed! Good luck everyone.

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

    In China, kids now get introduced to programing usually in middle school and sometimes in Grade 4 or 5. I really got a shock that Russian kids starts programing so early... Maybe we should learn something from it.

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

    In India as per New Education Policy, Programming is going to start from 6th grade.

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

      That would be really cool then! India will go one step further! In Bangladesh, remains the same, no changes ;(

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

What if I had registered and won't be able to participate? Because I am not sure whether I would be able to participate?

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

    Nothing happens, the contest will be unrated for you unless you submit a solution.

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

    Your rating will be unchanged

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

    You don't need to worry about it because your rating will change if and only if you participate in a contest and submit your solutions during the contest.

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

When Scoring distribution will update?

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

First of all, how many tasks are there...?

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

    6, it is written in Russian announsement

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

    What amazed me is there are only 5 tasks in D1 ... :(

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

just a simple question regarding contests : once I submitted solution and got WA on pretest 1 and still I didn't get any penalty!! Is it true to say that if I fail on the sample test cases then no penalty will be there?

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

I'm a simple man. I see anton, I take part.

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

Not able to solve even a single problem RIP.

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

Is everyone getting Queued in their submission? If so, what is the issue?

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

KAN Great contest sir... Loved it.

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

khó v pip dm

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

    đúng vậy khó như đấm mồm người khác dm thằng ra đề

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

This queue is a joke... spending ~3-5 minutes just to see if your submission is wrong isn't fun when you're really on the edge to solve a problem. EDIT: now more than 5 minutes:)

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

    no queue very fast i got my result only 5 secs còn m lâu do m ngu :)

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

:( The queue is bad today

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

6 minutes in queue and I think this contest is going to be unrated..this is so frustrating

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

Will the contest be extended or will any other measures be taken, because the queue is pretty bad?

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

I was solving wrong C, thought that you could remove any element :(. Realized it in the last 10 minutes. But I think i managed to get correct answer.

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

    me too (I realized it the last 20 seconds)

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

    ohh man, i was solvig the verion too :( (realized after reading your comment)

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

is it rated now?

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

What is test case 9 of D Div2 / B Div1?

Upd: got it.

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

there was a queue of around 5 minutes in end and the round wasnot extended this waas the only problem I faced with this round!

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

How to solve D(div2)?

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

how to solve problem D? I just bruteforce and passed sample...

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

good questions!^^

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

Did anyone else face a queue in the last minutes of the round ?

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

What is the hack for Div1B ?

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

At the last moment, I was facing In queue prblem :(

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

How to solve div2-D?

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

    u have already solved it so u tell us how u solved it ?

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

    If n > 60, answer = 1; else Run brute force. I did in O(n^3) brute.

    For the first condition, by Pigeonhole principle, there will be atleast 1 bit which is the most-significant-bit for 3 consecutive numbers. Choose the later 2 numbers from them and perform operation on them, their xor-sum will be less than the earlier number from them. So the answer will be just 1 move.

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

What are hack cases for div1B?

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +30 Vote: I do not like it
    4
    5 11 19 30
    
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      And the answer is...?

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

        It should be 2 since 5⊕11 = 14 > 13 = 19⊕30

        Some code only considers only single range for xor, which fails to answer these cases since 5⊕11⊕19 = 29 < 30 and 5 < 6 = 11⊕19⊕30

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

          But how to consider all the ranges?

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

            You only have to consider two consecutive ranges; i. e. [i, j) and [j, k)

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

      Time for some Fs in the chat for the half of contestants... It seems insane that this was not included in the pretests.

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

      Will the answer be -1?

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

      will system test must contain this type of test sir ???? then a lots of people failed !!

      UPD: Then sir can you please mention the author or mike sir if they must look into this test :(
      conflict

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

I submitted C in last 2nd minute but the judgement didn't came in contest. If it gets passed. Will it be considered in rankings or not?

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

Hey, I submitted the solution of problem C 5 minutes before the contest was going to get over, but it remained in the queue till the contest ended. Will my solution be judged? plz help

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

    Yes it will . Even if you submit in last second it counts .

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

    Don't worry, it will be judged, mine is still stuck on pretest, even after the contest is over.

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

hey i am new at recursion..so i was trying to solve problem c in div 2(Bouncing Ball).i was using this recursion-> ll aa( ll i) { if (i >= n)return 0; if (s[i] == '0') { return min(y + aa( i + 1), x + aa( i + k)); } else return aa( i + k); } it passed me the given test case but i got TLE in pretest 2.i know i have to use dp or some other approach to imporve time . but i was thinking is my recursive approach is right or wrong .can some one help me if it is wrong what would be the recursion? any kind of help is appreciated. (sorry for bad english)

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

    dp is not required to solve problem C its simple O(N) solution bro !!

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

      yeah i saw the solution it can be solved in o(n) with single loop..but i am asking if my recursive approach is correct or not

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

        I would say no. I used the same memoisation approach as yours during the contest and got wrong answer on pretest#2.

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

Regarding the queue: unfortunately during the last 5 minutes of the contest the queue was around 5 minutes due to huge number of submissions. I understand this is not very convenient, but we decided not to modify the length of the contest due to the following reasons:

  • This delay is not that large considering the total contest time.

  • Extension of the contest can bring a longer queue anyway.

Sorry for inconvenience, we hope for your understanding.

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

    is it rated KAN ?

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

    But I messaged you the same 15 minutes before the round ended I hoped you will understand that queue is going to increase more thus extension was the only way to resolve at least some queue. And the queue at ending time is nail biting in div2 when you are getting wrong answer due to vector length overbound runtime error and it is indicated as WA. I think action is needed to remove last 15 minute queues for further rounds.

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

what is the approach for Div2-C ?

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

    DP. I think..

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

    One of the solution is as follow : let us iterate over all possible values for the index where p will hit, i.e. if we don't remove anything from start and we have 0-based indexing, then we will hit on p-1, if we remove 1 from starting we will start at p, if we remove 2, then at p+1 and so on.

    So, if I know the starting point, what I would like to know is, going forward at interval of k, how many 0s, we will be hitting. This part can actually be stored first.

    So, pseudo code

    initialize an array of size k to 0, a[k]
    res = n*x; // if we have all 0s and we change all of them to 1, worst case
    m = 0, 
    for i = n-1 to p-1
      if s[i]=='0'
        a[m%k]++;
    
      // let us try to put p at current index 
      cost = (i+1-p)*y + a[m%k]*x;
      res = min(res,cost)
      m++;
    print res
    
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      '''

      3 10 3 2 0101010101 2 2 5 4 1 00000 2 10 11 2 3 10110011000 4 3

      '''

      n=int(input()) for i in range(0,n): o=input().rstrip().split(' ') p=input().rstrip() s=input().rstrip().split(' ') x=list(p) L=[] Q=[] W=[] S=[] D=[] for j in range(int(o[1])-1,len(x)): if j not in L: L.append(j) Q.append(j) S = 0; for k in range(j,len(x),int(o[2])): L.append(k) if x[k]=='0': S+=1; W.append(S) # print(Q,W) mini = 10000000000000; for j in range(0,len(W)): A=Q[j]+1-int(o[1]) T=int(s[1])*A; T+=(int(s[0])*W[j]) mini = min(mini,T) print(mini)

      my O(N) solution

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

Nice contest. Nice problems. Managed to solve 2 Good Going

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

    Get a shirt and sufficient nutrition. Edit: The pic changed after some time.

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

That feeling when you solve the problem 5 minutes after the contest.

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

why was their so much of queue time? my 2 solns were in queue for more than 8 mins?

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

    The problems are perfect, but around the ending the query queue is so long that I feel very nervous .

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

      if this is the problem than it should be unrated? as i eas dont able to concentrate on further problems due to this issue.

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

        I think it won't be unrated since it's just a small problem.

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

Why this solution passed in Div1B/Div2D its complexity is O(n^2). It should get TLE?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it
    for(int i=3;i<=n;++i)
    {
    	if((a[i]^a[i-1])<a[i-2])
    	{
    		puts("1");
    		return 0;
    	}
    }
    

    This block will return answer if there are atleast 3 numbers with same most significant bits.

    So, for each most significant bit, there can be atmost 2 numbers. For $$$a_i \leq 10^9$$$, there are at most 30 bits, so $$$N \leq 60$$$ holds.

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

I'm going to FST in B. Very sad times. Otherwise I might +100 according to the predictor....

The case for me to FST:

4
8 18 34 59
»
2 months ago, # |
  Vote: I like it -18 Vote: I do not like it

Editorail link?

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

good problem set

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

f*ck B pretests

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

Hi, Can anyone explain B I got stuck there

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

How to solve Div2 B?

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

After how much time I can submit my solution to a problem after the contest ends? It is showing "contest is over" and I dont see problems in problemset section. Anybody have any idea? Please

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

How to solve D? (Edit : I was thinking of prefix and suffix xors, and I see some people talking about it in the thread. But I was not able to prove it. So didn't code.)

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

    I think the idea is to create a prefix xor array $$$p$$$ and now we need for each $$$i$$$

    $$$p[j] > v[i+1] \oplus p[i] \ j < i$$$.

    So you need the $$$min(i-j)$$$ over all $$$i,j$$$. And update the answer doing the same on the reversed array.

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

It seems that D1B has too weak pretests and clearly I'll fst...

upd:TEST 51 is GOD!

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

    Any example corner case?

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

    sorry for stupid question. But what is fst ?

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

      Failed System Tests.That means your code passed pretest(maybe very weak)and failed in a extra test made by other person because your solution is not correct.

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

      fail system tests

»
2 months ago, # |
  Vote: I like it -18 Vote: I do not like it

Make It Unrated .

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

Why wasn't there additional time after such a long queue? It's so unfair. :)

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

Did anyone else face a queue in the last minutes of the round ?... My solution was in queue even when the contest was over... !!

Is it fair?

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

    Same here I also faced the same problem in the last 15 minutes!! The solution I submit was in queue for a very long time!!

»
2 months ago, # |
  Vote: I like it -82 Vote: I do not like it

B was the only good task in Div1 (possibly other than E), but you managed to ruin it with disgusting pretests

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

How to solve div2E/div1C?

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

Can D be solved with trie?

using prefix and suffix we can insert them into different tries, and then with each index we check using dp on the trie of the suffix: the minimum index which makes the current xor smaller than v[index-1], and we do the opposite for the prefix.

is there anything wrong with this idea?

i saw many people solved it in an easier way but i think this solution might be interesting.

»
2 months ago, # |
  Vote: I like it +17 Vote: I do not like it
Even Contest is Over But In Queue
»
2 months ago, # |
Rev. 2   Vote: I like it -18 Vote: I do not like it

.

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

    No buddy, The contest should be rated. It is not a big issue.

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

    In A div 1 they fixed the statement by eliminating a possible case. I had 3 WA's in A div1. That is not why I will say that it is made unrated. Improve your skills and don't cry.

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

[deleted]

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

.

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

System testing still pending for all?

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

Nice contest. Problems were really good comparing to previous rounds.

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

Can someone explain why in div2-B O(n*100) will not give TLE given the time limit is 1 second.

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

    $$$10 ^ 7$$$ operations under a second is cakewalk for C++.

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

      But there are 10^4 test cases also. The total time complexity should have been O(t*n*100) which will be 10^11. Is there something which I have misunderstood regarding the time complexity?

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

        *It is guaranteed that the sum of n over all test cases does not exceed 10^5.

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 4   Vote: I like it -13 Vote: I do not like it

      But 10^4 for every testcase does not count ?Then it will be 10^11.

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

    I see someone said: "Codeforces works fine with 100M operations for 1 secs"

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

    As sum of n over all testcases does not exceed 10^5 hence O(10^5 * 100) = O(10^7) which easily runs in 1 second.

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

      I am so dumb. I did not saw this line in the problem.

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

        If this is the first time then you're not dumb. But if you repeat this again then you're.

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

      But 10^4 for every testcase does not count ?Then it will be 10^11.

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

    n is 10^5 so O(n*100) = O(10^5 * 10^2) = O(10^7) Usually TLE occurs when no of operations are more than 10^8. Hence, No TLE will occur

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

      But 10^4 for every testcase does not count ?Then it will be 10^11.

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

        "It is guaranteed that the sum of n over all test cases does not exceed 10^5". Read this statement carefully.

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

Thanks KAN for the time that friendly for Chinese OIers.
I hope I would not FST and become CM!
update:I got an FST on div2 D ...... But it seems that I can still become CM?

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

    Congratulations! :)

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

    As an alumni, it is pretty interesting to see someone from xue jun high school :)

»
2 months ago, # |
  Vote: I like it -16 Vote: I do not like it

Make It Unrated .

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

    Why? The problems were pretty balanced, statements pretty clear

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

for DIV 2, Last problem, NEW GAME PLUS! I found some issue with the third pretest,

13 2

3 1 4 1 5 -9 -2 -6 -5 -3 -5 -8 -9

the answer I calculated by logic is 70, yet the output given is 71,

can anyone please explain this pretest?

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

    Take as: 5 4 3 1 1 -2 -3 -5 -5 -9 reset -9 reset -6 -8

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you kindly explain this test case more clearly? How could you reset -6 -8?

      In my opinion, the order of bosses should be 5 4 3 1 1 -2 -3 -5 -5 -6 -8 -9 -9. Then, we will reset before we meet the "bold" bosses.

      I know that it will be inconvenient for you to read the problem again. I would really appreciate it if you could help me.

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

        No problem, actually if we regard it as three arrays:
        [5 4 3 1 1 -2 -3 -5 -5 -9], [-9], [-6 -8]
        You can see that the last element of eary array (the bold ones) is not counted into the sum. So we would like to place the smallest ones at end of each array

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

    You should explain your calculation "by logic" resulting in 70.

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

Div2D/Div1B is ruining the ratings of many. xD

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

I also FST on D. ??????

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

I passed the pretest but failed in the system test for Div2B. Is there any way for me to improve code efficiency?

https://codeforces.com/contest/1457/submission/99863237

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

Could you just use brute force for div2D/div1B? My approach got 46ms on tests up to 45 but WA on it: https://codeforces.com/contest/1457/submission/99889304

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

    For $$$N$$$ $$$\leq$$$ $$$60$$$, brute force. Otherwise, you can find a set of atleast three consecutive elements with same highest set bit. Choose the last two elements, the xor of which will be less than the first element. So, just one operation required in this case.

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

what's with the weak pretests!!

»
2 months ago, # |
  Vote: I like it +53 Vote: I do not like it
Before system tests
After system tests

I feel the luckiest person on Earth.

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

    I'm luckier lol

    Before system test: +0
    After system test (eventhough I FSTd div2D/div1B) : +21
    
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

WHy this submission is WA Instead of RUntime error. If some index is out of vector size why I got WA . the same submission when I increased length of the vector passed easily. AM I missing something with properties of vector.

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

    More like you're missing something about the properties of C++
    C++ does not care that you accessed some who-knows-what-storing memory

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

Very WEAK Pretests!!!

FROM +100 TO -100, for an obvious mistake and an INTEGER OVERFLOW issue.

Though it is me that wrote the FST code, how can pretests be SO WEAK? I AM ANGRY!

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

    But it was you who wrote the FST code. Pretests should cover the basic understanding of a problem and they do.

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

      I believe according to codeforces problem setting guidelines, pretests should also be STRONG and make mistakes like INTEGER OVERFLOW fail. Covering the basic understanding of a problem is the main job for examples, not pretests.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        according to codeforces problem setting guidelines

        Are these guidelines publicly available? Knowing what to expect during a round would be beneficial to participants as well, even if they don't prepare any problems themselves — but I didn't manage to quickly find any post on that.

        It seems like the expectations changed a lot over the last several years: 5+ years ago integer overflow not being covered by pretests would've been totally OK, and nowadays most of contestants see it as something utterly wrong and unfair.

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

      https://docs.google.com/document/d/e/2PACX-1vRhazTXxSdj7JEIC7dp-nOWcUFiY8bXi9lLju-k6vVMKf4IiBmweJoOAMI-ZEZxatXF08I9wMOQpMqC/pub

      According to this file:

      IF YOU ARE TO PREPARE A ROUND ON CODEFORCES, THESE ADVICES ARE RULES. FOLLOW THEM AS CLOSE AS YOU CAN.

      • In general, pretests should include: a test with maximum size of input (e.g. maximum n), a test against integer overflow, a few random small tests. All corner cases that are easy to miss. If you deliberately don’t include some corner case, talk to the coordinator about this.
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can anyone please tell me what is FST?

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

        It's a special data structure that's mostly known at lower levels: Failed System Test.

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

    It's always good to prove the solution is exactly correct...You know that not only CF but CCF provides weak samples too

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

      Alright, maybe I'll get those lost rating back next week

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

        I FSTed two times by a) allocating incorrect array size and b) reading the input wrong and somehow passing pretests (1-indexed instead of 0-indexed)

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

    use #define int long long.

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

Finally going to be violet It seems
Most likely this wouldn't happen without mass-FSTs, so I waited for them, and they came to me. So sweet :3

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

waiting for editorial

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

Is the following solution for Div2 D correct, or are the system tests weak? (this gets OK and passes the system tests)

#include <vector>
#include <cmath>
#include <iostream>
#include <cstdio>
#include <climits>

int main()
{
	int n; std::cin >> n;
	std::vector<int> seq(n);
	for(int& x : seq)
		scanf("%d", &x);
	int ans = INT_MAX;
	for(int i = 0; i < n-1; i++)
	{
		int lxor = 0;
		for(int left = 0; i - left >= 0 && left <= 32; left++)
		{
			lxor ^= seq[i-left];
			int rxor = 0;
			for(int right = 0; i + right + 1 < n && right <= 32; right++)
			{
				rxor ^= seq[i+right+1];
				if(lxor > rxor) ans = std::min(ans, left+right);
			}
		}
	}
	printf("%d\n", ans == INT_MAX ? -1 : ans);
}

The code iterates over the location of the potential decreasing pair of elements, and tries applying the XOR gun at most 32 times at both endpoints of the pair (and if the XORs are decreasing, updates the answer).

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

    Yeah, it is correct I think
    Range of length 66 is guaranteed to contain at least one triplet with the same most significant bit. And if you have such a triplet, you can solve the task for one move

    And if the answer is bigger than 1, you basically do bruteforce

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

    First of all, in order to keep the comment section readable, please don't post whole code here...

    Yes, this solution is correct, although it may sound weird in the beginning. For this, suppose there are 3 integers in the array with the same leading bit. Because the array is sorted, if there are three, then there are three consecutive. Then by xoring the second and the third, the resulting number will have this bit off, and thus will be smaller than the first number (of the three we looked at). Thus if the answer can only be bigger than one if $$$n \leq 2 \cdot log(max(a))$$$, which in this case gives $$$n < 60$$$. But in this case, your code bruteforces all the possible ranges, and will find the best groups.

    EDIT: As mango_lassi pointed out, I don't really see why it's correct if the bruteforce only checks sets with size up to 32...

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

      Shouldn't the loops go up to 60 for the code to brute-force all possible ranges? What if, there was somehow a case where, say, $$$n = 41$$$ and you need to xor the first 40 to make them larger than the 41st number?

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

        True, I didn't think that far, I only saw the bruteforce...

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

        I wonder what is the actual worst case here? Skimming through the system tests, it looks like 29 is the largest answer?

        Can somebody show how to get more strict upper bound of log instead of 2*log?

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

          Let's say we have one number for each most significant bit

          And now we add one more for one of the bits

          So we have a pair (A, B)

          Now look at A^B

          If it doesn't create an answer immediately, it joins the neighboring bit on the left

          So if we count numbers by the most sign bit and we have something like
          [1,1,1,2,1,1,1,2]
          It is already enough to create a decreasing sequence
          [1,1,1,2,1,1,2] -> [1,1,1,2,1,2] -> [1,1,1,2,2] -> [1,1,1,3] (log + 2) numbers seems enough to gurantee the existence of the triplet with the same sign bit.
          And there will be no more than log operations before we stop

          So it seems it is rounddown(log n)

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

any hint for [problem C] and thank u

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

    The deleting first element is like to increase p by one so check the brute force and preprocessing you need check if you're p increase by c so you need x*c time and the number of elements such as equals to 0 and placed at the one of p+c, p+c+k, p+c+2k, ... positions product by y.

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

      i'm new to dp, but why are we going backwards.

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

What was there in test case 51 of div 2 problem D? Many people got a wrong verdict on that testcase.

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

    11 22 71 92 -> People were trying all subarrays but did not consider this case Most of them got -1 in it but here we can do

    11^22-> 29

    71^92-> 27

    This will give ans 2 :)

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

Why D is O(n^3) and not TLE??? My own computer TLE

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

    Are you sure the solution you viewed is $$$O(n^3)$$$ ? For that if you check whether the answer is $$$1$$$, the time complexity will become $$$O(n+\log^3 n)$$$ (Update: It is wrong... but $$$n\leq 100$$$ is always held if the answer is greater than $$$1$$$).

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

      https://codeforces.com/contest/1457/submission/99860413 rep(l,1,n-1)rep(r,l+1,n)rep(k,l,r-1) Is this not $$$O(n^3)$$$?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        rep(i,1,32)if(c[i]>2){
        		puts("1");return 0;
        	}
        

        So it means if $$$n>64$$$ the $$$O(n^3)$$$ loop will not be executed.

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

          Thanks, but why when $$$n=64$$$ then answer is $$$1$$$?

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

            if $$$n>64$$$ there must be $$$a_i,a_{i+1},a_{i+2}$$$ with same highest binary bit. Then you can xor $$$a_{i+1},a_{i+2}$$$ and the answer is less than $$$a_i$$$.

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

Got stuck on B , such an easy problem

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

Can anyone tell me why my solution 99882642 is giving Runtime error on pretest 3. I have checked it by giving the input present in pretest 3, and it is giving correct answer.

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

    You are trying to access element s[n].

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

      No, it was not the reason for that runtime error. I have figured out the reason.

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

https://codeforces.com/contest/1457/submission/99878780

Can you please help me figure out reason behind TLE? IN TC 30/33

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

Where's the editorial

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

    Why dont you watch participant's code while waiting : D

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

    From the announcement:

    We will publish winners, editorial and rating updates today a bit later than usual.

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

Have you guys seen anyone going from CM to GM in one contest ? check this

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

Hi, it's my first contest, will I get any rating for it? If yes when? I solved 1 problem so I have some points.

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

    It generally takes anywhere between 2-12 hours to update, doesn't seem like it is an automatic action.

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

    Yeah , just wait for the ratings to get updated, it takes a few hours to atmost half a day(in worst case).

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

    Yes if you submit at least one solution (it doesn't matter be accepted or not) . So usually 3-8 hours after contest the final ratings will be announced.

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

      Thanks guys! I really like this community, so friendly.

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

(images.jpg)

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

Can someone provide me a hint for DIV2.C??