Добрый день!
В 29.11.2020 10:05 (Московское время) состоится Отборочный Раунд 2 олимпиады для школьников Технокубок 2021. Раунд будет длиться два часа, участникам будут предложены 6 задач. По его результатам лучшие участники (но не более 45% от общего числа участников раунда) будут приглашены на финальный этап в Москву. Для регистрации на раунд и участия перейдите по ссылке. Не забудьте заранее зарегистрироваться на раунд! Для опоздавших будет открыта дополнительная регистрация (с 10:15 до 12:05).
Зарегистрироваться на Отборочный Раунд 2 →
Соревнование открыто для всех в виде отдельных раундов для первого и второго дивизионов.
Для всех участников всех трех редакций этого соревнования будет пересчитан рейтинг.
Параллельно с Отборочным Раундом будут проведены открытые рейтинговые раунды для обоих дивизионов, в них могут принять участие все желающие.
Напомним, что согласно правилам раундов Codeforces во время соревнования ваши решения будут тестироваться только на претестах (предварительном и неполном наборе тестов), а системное тестирование состоится после окончания раунда. Обратите внимание, что претесты не покрывают все возможные случаи входных данных, поэтому тщательно тестируйте свои программы! После прохождения претестов у вас будет возможность заблокировать решение, тем самым получив привилегию искать ошибки и взламывать чужие решения, но отказавшись от возможности перепослать ваше решение при каких-либо обстоятельствах (например, даже если вы найдете ошибку или вас взломают). Со временем задачи падают в стоимости. После системного тестирования учитываются только полные решения. Подробнее про правила соревнований можно прочитать по ссылкам:
Регистрация на олимпиаду Технокубок еще открыта. Победителей и призеров олимпиады ждут значительные квоты при поступлении в престижные технические вузы России и ценные призы! Если Вы школьник 8-11 классов и пока не зарегистрировались на Технокубок, то самое время сделать это:
Зарегистрироваться на олимпиаду →
После регистрации на олимпиаду не забудьте зарегистрироваться на Отборочный Раунд!
В финал соревнования будут приглашены лучшие участники каждого из отборочных раундов (но не более 45% от общего числа участников раунда).
Авторы отборочного раунда; amethyst0, eidan, Diegogrc, bensonlzl, JettyOller, antontrygubO_o и KAN. Спасибо antontrygubO_o и 300iq за помощь в координации. Кроме того, огромное спасибо тестерам, без помощи которых этот раунд не состоялся бы: 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!
Для тех, кто впервые на Codeforces: в таблице ниже вы можете найти примеры решений на всех поддерживаемых языках:
| Группа языков | Языки программирования / компиляторы | Примеры |
|---|---|---|
| C | GNU C, GNU C11 | 10903473, 17029870 |
| C++ | GNU C++, GNU C++11, GNU C++14, GNU C++17, MS C++, etc. | 23794425, 5456501 |
| C# | Mono C#, MS C# | 3195513, 3794163 |
| D | D | 5482410, 2060057 |
| Go | Go | 7114082, 21366098 |
| Haskell | Haskell | 455333, 1668418 |
| Java | Java 8 | 25491359, 23678167 |
| JavaScript | V8 | 35963909, 35681818 |
| Kotlin | Kotlin | 25779271, 25204556 |
| OCaml | OCaml | 6157159, 1281252 |
| Pascal | Delphi, FPC, Pascal.NET | 1275798, 1259434 |
| Perl | Perl | 2519448, 1277556 |
| PHP | PHP | 413942, 35875300 |
| Python | Python 2, Python 3, PyPy2, PyPy3 | 35883730 (Py2), 36179112 (Py3) |
| Ruby | Ruby | 1837970, 1289551 |
| Rust | Rust | 25180002, 35652442 |
| Scala | Scala | 35847980, 2456025 |
Удачи!
Спасибо за участие! Поздравляем победителей:
Технокубок 2021 - Отборочный Раунд 2
Codeforces Round 687 (Div. 1, основан на Отборочном раунде 2 Технокубка 2021)
Codeforces Round 687 (Div. 2, основан на Отборочном раунде 2 Технокубка 2021)
Upd: Рейтинги пересчитаны.
UPD2: Опубликован разбор задач.
Notice the unusual start time!!!
Thanks, I might have missed this round.
Why do people even downvote this comment?)
Probably because of ratism rip
or username
Because those comments and similar ones are just filling the comment section making finding useful content takes more time.
I missed :(
I nearly missed the round today!! :/
Notice the unusual time.
please upvote me , i am getting too many downvotes !! please push me to a +ve side !!
haha every one voted u down
Why the unusual start time?
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!
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)
Happy birthday Retired_cherry ....one of the most consistent tester
Happy birthday Retired_cherry...Keep testing :-)
Happy birthday Retired_cherry.
Heppy birthday Retired_cherry and keep testing :)
I wonder why the birthday wishes being downvoted :(
Happy birthday Retired_cherry !!!
Happy birth Retired_cherry. I wish you good luck in next contests!
Happy Birthday Retired_cherry
Happy birthday my dear friend Retired_cherry.
And that's how it's done uwu
This competition is friendly for Chinese competitor! Thanks KAN!
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.
Pacific time zone people are probably celebrating, lol, better than waking up at 6am in the morning.
I'd prefer to take those rounds in 6am compared to the time when I normally need to be at work
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!
Score distribution?
Nice contest, thanks KAN and your team !!!
Goodluck to everyone ^_^
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!
As a tester, KAN amethyst0 antontrygubO_o JettyOller eidan Diegogrc bensonlzl are great problemsetters. I would highly recommend all to participate in the round.
A great time for Chinese competitors! I won't miss this round :)
Do you mean Technocup 2021?
Can the string hash to O(1) to compare the dictionary order size
What will be the difficulty level of this contest (div2) ???
Same as difficulty of other DIV2 contests.
Thanks for starting contest not in dawn.
To be honest every round is the birthday of ~50 people participating
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.
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.
In India as per New Education Policy, Programming is going to start from 6th grade.
That would be really cool then! India will go one step further! In Bangladesh, remains the same, no changes ;(
What if I had registered and won't be able to participate? Because I am not sure whether I would be able to participate?
Nothing happens, the contest will be unrated for you unless you submit a solution.
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.
When Scoring distribution will update?
Expecting for it too...
First of all, how many tasks are there...?
6, it is written in Russian announsement
What amazed me is there are only 5 tasks in D1 ... :(
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?
only testcase 1, not all sample testcases.
I'm a simple man. I see anton, I take part.
Is everyone getting Queued in their submission? If so, what is the issue?
Nope
yeah I am also having queued submissions
KAN Great contest sir... Loved it.
khó v pip thằng nào ra đề đấy
khó v pip dm
đúng vậy khó như đấm mồm người khác dm thằng ra đề
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:)
no queue very fast i got my result only 5 secs còn m lâu do m ngu :)
:( The queue is bad today
Will the contest be extended or will any other measures be taken, because the queue is pretty bad?
It better be rated :-(
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.
me too (I realized it the last 20 seconds)
ohh man, i was solvig the verion too :( (realized after reading your comment)
What is test case 9 of D Div2 / B Div1?
Upd: got 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!
How to solve D(div2)?
how to solve problem D? I just bruteforce and passed sample...
what was ur approach for D?
just enumerate the interval of len 2 3 4 ...
I guess the length won't be too large
Did anyone else face a queue in the last minutes of the round ?
What is the hack for Div1B ?
At the last moment, I was facing In queue prblem :(
How to solve div2-D?
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.
What are hack cases for div1B?
And the answer is...?
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
But how to consider all the ranges?
You only have to consider two consecutive ranges; i. e. [i, j) and [j, k)
Time for some Fs in the chat for the half of contestants... It seems insane that this was not included in the pretests.
Will the answer be -1?
It should be 2
Ok, there is a Konijntje between our answers, LoL.
what the
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
It should.
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?
It'll be considered
It passed :)
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
Don't worry, it will be judged, mine is still stuck on pretest, even after the contest is over.
Thankyou very much.
There was 5-7 mins queue in last 10 mins. Round should have been extended. :(
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)dp is not required to solve problem C its simple O(N) solution bro !!
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
I would say no. I used the same memoisation approach as yours during the contest and got wrong answer on pretest#2.
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.
is it rated KAN ?
Yes.
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.
what is the approach for Div2-C ?
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
'''
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
do not directly paste your code, use spoiler
Nice contest. Nice problems. Managed to solve 2 Good Going
Get a shirt and sufficient nutrition. Edit: The pic changed after some time.
I have to money , I am poor (crying noise intensifies)
That feeling when you solve the problem 5 minutes after the contest.
why was their so much of queue time? my 2 solns were in queue for more than 8 mins?
The problems are perfect, but around the ending the query queue is so long that I feel very nervous .
if this is the problem than it should be unrated? as i eas dont able to concentrate on further problems due to this issue.
I think it won't be unrated since it's just a small problem.
Why this solution passed in Div1B/Div2D its complexity is O(n^2). It should get TLE?
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.
I'm going to FST in B. Very sad times. Otherwise I might +100 according to the predictor....
The case for me to FST:
What's the real answer for this case?
2
How?
8^18>34^59
FST = Fail system test? right?
Yes
good problem set
f*ck B pretests
How to solve Div2 B?
Complete search
how a 10^4*10^2*10^5 passed in 1 sec ?
It is guaranteed that the sum of n over all test cases does not exceed 10^5.
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.)
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.
It seems that D1B has too weak pretests and clearly I'll fst...
upd:TEST 51 is GOD!
Any example corner case?
sorry for stupid question. But what is fst ?
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.
fail system tests
Why wasn't there additional time after such a long queue? It's so unfair. :)
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?
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!!
B was the only good task in Div1 (possibly other than E), but you managed to ruin it with disgusting pretests
How to solve div2E/div1C?
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.
.
Sure sir
yeah :(
might not will happen in future :(
No buddy, The contest should be rated. It is not a big issue.
Agreed.
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.
hopefully, servers will be better in the future :(
[deleted]
Nice contest. Problems were really good comparing to previous rounds.
Can someone explain why in div2-B O(n*100) will not give TLE given the time limit is 1 second.
$$$10 ^ 7$$$ operations under a second is cakewalk for C++.
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?
*It is guaranteed that the sum of n over all test cases does not exceed 10^5.
I see someone said: "Codeforces works fine with 100M operations for 1 secs"
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.
I am so dumb. I did not saw this line in the problem.
If this is the first time then you're not dumb. But if you repeat this again then you're.
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?
Congratulations! :)
As an alumni, it is pretty interesting to see someone from xue jun high school :)
Make It Unrated .
Why? The problems were pretty balanced, statements pretty clear
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?
Take as: 5 4 3 1 1 -2 -3 -5 -5 -9 reset -9 reset -6 -8
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.
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
I got it. Thank you very much.
You should explain your calculation "by logic" resulting in 70.
Div2D/Div1B is ruining the ratings of many. xD
Pretests were so weak for it:)))
I also FST on D. ??????
unlucky day...
From +100 to -100??
INTEGER OVERFLOW
I passed the pretest but failed in the system test for Div2B. Is there any way for me to improve code efficiency?
https://codeforces.net/contest/1457/submission/99863237
Seriously, don't use Python.
Oh please
Don't push the blame for this onto python
Python is more than enough for div2
Try submitting the same usin pypy
Could you just use brute force for div2D/div1B? My approach got 46ms on tests up to 45 but WA on it: https://codeforces.net/contest/1457/submission/99889304
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.
Wow, thank you! This is very smart!
what's with the weak pretests!!
I feel the luckiest person on Earth.
I'm luckier lol
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.
More like you're missing something about the properties of C++
C++ does not care that you accessed some who-knows-what-storing memory
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!
But it was you who wrote the FST code. Pretests should cover the basic understanding of a problem and they do.
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.
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.
Yeah I had one when I did problem setting. I'll try to find it.
In guideline:
It is here:
https://docs.google.com/document/d/e/2PACX-1vRhazTXxSdj7JEIC7dp-nOWcUFiY8bXi9lLju-k6vVMKf4IiBmweJoOAMI-ZEZxatXF08I9wMOQpMqC/pub
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.
Can anyone please tell me what is FST?
It's a special data structure that's mostly known at lower levels: Failed System Test.
Nice one
It's always good to prove the solution is exactly correct...You know that not only CF but CCF provides weak samples too
Alright, maybe I'll get those lost rating back next week
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)
This is life I guess
use #define int long long.
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
finally going to be blue ..wouldn't happen if not for FST
congrats my dude. <3
waiting for editorial
Is the following solution for Div2 D correct, or are the system tests weak? (this gets OK and passes the system tests)
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).
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
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...
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?
True, I didn't think that far, I only saw the bruteforce...
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?
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)any hint for [problem C] and thank u
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.
What was there in test case 51 of div 2 problem D? Many people got a wrong verdict on that testcase.
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 :)
Why D is O(n^3) and not TLE??? My own computer TLE
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$$$).
https://codeforces.net/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)$$$?
So it means if $$$n>64$$$ the $$$O(n^3)$$$ loop will not be executed.
Thanks, but why when $$$n=64$$$ then answer is $$$1$$$?
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$$$.
Thanks
Amazing
Got stuck on B , such an easy problem
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.
You are trying to access element s[n].
No, it was not the reason for that runtime error. I have figured out the reason.
https://codeforces.net/contest/1457/submission/99878780
Can you please help me figure out reason behind TLE? IN TC 30/33
Where's the editorial
Why dont you watch participant's code while waiting : D
From the announcement:
Have you guys seen anyone going from CM to GM in one contest ? check this
.
have you seen anyone getting this lucky before ?
.
XD XD... I would be grateful if you can show a few of them, LOL
.
Sorry but we can't believe you then, get some facts to support your statement first XD XD.
User : Jerry
Round: #372
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.
It generally takes anywhere between 2-12 hours to update, doesn't seem like it is an automatic action.
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.
Thanks guys! I really like this community, so friendly.
(
)
Can someone provide me a hint for DIV2.C??
The deleting first element is like to increase p by one so check the brute force and preprocessing.
An amazing round , I enjoyed tasks so nice and helpful.
why there is a huge gap in div1 rounds its just so annoying : (
I think the round is very good !
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.
If anyone is stuck at C , you can watch this https://youtu.be/_yErO-xE1O0
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://codeforces.net/contest/1457/submission/99900717
please, someone help me to understand problem div2/D,, why the answer is 1 when the value of n > 60??
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.
There is a feature called "spoiler". look
This is a spoiler. It's good to not spoil upsolve activity for somone, for example.
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!
Avoid announcement and editorial comments after contests if u wish to upsolve.
Why were rating changes rolled back?
yeah It's being rolled back in every contest nowadays..
why though?