Codeforces Round 687 (Div. 1, Div. 2) and Technocup 2021 — Elimination Round 2
By KAN, 4 years 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, JettyOller, 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, kalki411, golions, dantrag, Retired_cherry, gigabuffoon, Andres_Alumets, firi., coderz189, 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. Konijntje
  4. al13n
  5. kort0n

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

  1. Sharpness
  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

Comments Comments (271)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +81 Vote: I do not like it

Notice the unusual start time!!!

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

Notice the unusual time.

→ Reply
»
4 years 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 !!

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

    haha every one voted u down

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

Why the unusual start time?

→ Reply
  • »
    »
    4 years 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!

    → Reply
»
4 years 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)

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

This competition is friendly for Chinese competitor! Thanks KAN!

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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

    → Reply
»
4 years 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!

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

Score distribution?

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

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

Nice contest, thanks KAN and your team !!!

Goodluck to everyone ^_^

→ Reply
»
4 years 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!

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

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

→ Reply
»
4 years 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?

→ Reply
»
4 years 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

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

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

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

Thanks for starting contest not in dawn.

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

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

→ Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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.

    → Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years 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 ;(

      → Reply
»
4 years 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?

→ Reply
  • »
    »
    4 years 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.

    → Reply
  • »
    »
    4 years 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.

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

When Scoring distribution will update?

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

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

→ Reply
»
4 years 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?

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

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

→ Reply
»
4 years 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?

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

KAN Great contest sir... Loved it.

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

khó v pip dm

→ Reply
»
4 years 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:)

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

:( The queue is bad today

→ Reply
»
4 years 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?

→ Reply
»
4 years 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.

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

    me too (I realized it the last 20 seconds)

    → Reply
  • »
    »
    4 years 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)

    → Reply
»
4 years 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.

→ Reply
»
4 years 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!

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

How to solve D(div2)?

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

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

→ Reply
»
4 years 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 ?

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

What is the hack for Div1B ?

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

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

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

How to solve div2-D?

→ Reply
  • »
    »
    4 years 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.

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

What are hack cases for div1B?

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

      And the answer is...?

      → Reply
      • »
        »
        »
        »
        4 years 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

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

          But how to consider all the ranges?

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years 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)

            → Reply
    • »
      »
      »
      4 years 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.

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

      Will the answer be -1?

      → Reply
    • »
      »
      »
      4 years 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 :(
      Konijntje

      → Reply
»
4 years 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?

→ Reply
»
4 years 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

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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)

→ Reply
  • »
    »
    4 years 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 !!

    → Reply
    • »
      »
      »
      4 years 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

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
»
4 years 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.

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

    is it rated KAN ?

    → Reply
  • »
    »
    4 years 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.

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

what is the approach for Div2-C ?

→ Reply
  • »
    »
    4 years 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
    → Reply
    • »
      »
      »
      4 years 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

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

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

→ Reply
  • »
    »
    4 years 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.

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

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

→ Reply
»
4 years 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?

→ Reply
  • »
    »
    4 years 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 .

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
»
4 years 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?

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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
→ Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

good problem set

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

f*ck B pretests

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

How to solve Div2 B?

→ Reply
»
4 years 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.)

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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!

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

    Any example corner case?

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

    sorry for stupid question. But what is fst ?

    → Reply
    • »
      »
      »
      4 years 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.

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

      fail system tests

      → Reply
»
4 years 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. :)

→ Reply
»
4 years 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?

→ Reply
  • »
    »
    4 years 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!!

    → Reply
»
4 years 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

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

How to solve div2E/div1C?

→ Reply
»
4 years 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.

→ Reply
»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it
Even Contest is Over But In Queue
→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it -18 Vote: I do not like it

might not will happen in future :(

→ Reply
  • »
    »
    4 years 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.

    → Reply
  • »
    »
    4 years 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.

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

    hopefully, servers will be better in the future :(

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

[deleted]

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

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

→ Reply
»
4 years 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.

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

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

    → Reply
    • »
      »
      »
      4 years 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?

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
  • »
    »
    4 years 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"

    → Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
»
4 years 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?

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

Make It Unrated .

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

    Why? The problems were pretty balanced, statements pretty clear

    → Reply
»
4 years 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?

→ Reply
  • »
    »
    4 years 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

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
      • »
        »
        »
        »
        4 years 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

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

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

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

Div2D/Div1B is ruining the ratings of many. xD

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

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

→ Reply
»
4 years 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://mirror.codeforces.com/contest/1457/submission/99863237

→ Reply
»
4 years 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://mirror.codeforces.com/contest/1457/submission/99889304

→ Reply
  • »
    »
    4 years 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.

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

what's with the weak pretests!!

→ Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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
    → Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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

    → Reply
»
4 years 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!

→ Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
    • »
      »
      »
      4 years 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.
      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can anyone please tell me what is FST?

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
  • »
    »
    4 years 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

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

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

      → Reply
      • »
        »
        »
        »
        4 years 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)

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

    use #define int long long.

    → Reply
»
4 years 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

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

waiting for editorial

→ Reply
»
4 years 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).

→ Reply
  • »
    »
    4 years 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

    → Reply
  • »
    »
    4 years 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...

    → Reply
    • »
      »
      »
      4 years 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?

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

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

        → Reply
      • »
        »
        »
        »
        4 years 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?

        → Reply
        • »
          »
          »
          »
          »
          4 years 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)

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

any hint for [problem C] and thank u

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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 :)

    → Reply
»
4 years 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

→ Reply
  • »
    »
    4 years 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$$$).

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

Got stuck on B , such an easy problem

→ Reply
»
4 years 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.

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

    You are trying to access element s[n].

    → Reply
    • »
      »
      »
      4 years 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.

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

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

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

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

Where's the editorial

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

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

    → Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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

→ Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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.

    → Reply
  • »
    »
    4 years 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.

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

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

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

(images.jpg)

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

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

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

    The deleting first element is like to increase p by one so check the brute force and preprocessing.

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

An amazing round , I enjoyed tasks so nice and helpful.

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

why there is a huge gap in div1 rounds its just so annoying : (

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

Any comments about div1D? I like the idea, although at least in my $$$O(N)$$$ solution, it's very easy to make a small mistake in implementation even when you know what to do. My solution is DP with states "if the clone just took $$$i$$$, where can I be?" and "if I just took $$$i$$$, where can the clone be?"; it turns out that in the second case, the set of possible positions is a range around $$$X_i$$$, which forces the set of positions in the first case to be at most a union of two ranges.

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

If anyone is stuck at C , you can watch this https://youtu.be/_yErO-xE1O0

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

I used dictionary tree to passed the div2 D, I can guarantee its correctness, but I can't guarantee its time complexity,can anyone hack my solutions? https://mirror.codeforces.com/contest/1457/submission/99900717

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

please, someone help me to understand problem div2/D,, why the answer is 1 when the value of n > 60??

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

    Consider elements of the same highest bit. Some examples are [2(10), 3(11)] and [4(100),5(101),6(110),7(111)] and so on. 1e9 has has 30 bits so there are 30 different such groups.

    Now consider if a group has 3 elements from the given array, for example [4,5,7]. Since their highest bit is the same, if i xor any 2 of the value, the highest bit becomes 0 and the resulting number belongs to a lower group. if i xor 5 and 7, 101^111 gives 2(10) which is less than 4. So basically is theres 3 numbers in a group the strategy is to xor the last 2 in the group and we're done. So each group can have at max 2 numbers and hence we get 30*2=60.

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

    There is a feature called "spoiler". look

    spoiler

    Please remember this. It's crucial that you understand this feature. I didn't want to know that " answer is 1 when the value of n > 60", cause I wanted to try and upsolve this problem!

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

      Avoid announcement and editorial comments after contests if u wish to upsolve.

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

Why were rating changes rolled back?

→ Reply