Добрый день!
В воскресенье, 21-го октября в 11:05 по московскому времени состоится Отборочный Раунд 2 олимпиады для школьников Технокубок 2019. Раунд будет длиться два часа, участникам будут предложены 6 задач. По его результатам лучшие участники (но не более 45% от общего числа участников раунда) будут приглашены на финальный этап в Москву. Для регистрации на раунд и участия перейдите по ссылке. Не забудьте заранее зарегистрироваться на раунд! Для опоздавших будет открыта дополнительная регистрация (с 11:15 до 13:05).
Зарегистрироваться на Отборочный Раунд 2 →
Соревнование открыто для всех в виде отдельных раундов для первого и второго дивизионов.
Для всех участников всех трех редакций этого соревнования будет пересчитан рейтинг.
Параллельно с Отборочным Раундом будут проведены открытые рейтинговые раунды для обоих дивизионов, в них могут принять участие все желающие.
Напомним, что согласно правилам раундов Codeforces во время соревнования ваши решения будут тестироваться только на претестах (предварительном и неполном наборе тестов), а системное тестирование состоится после окончания раунда. Обратите внимание, что претесты не покрывают все возможные случаи входных данных, поэтому тщательно тестируйте свои программы! После прохождения претестов у вас будет возможность заблокировать решение, тем самым получив привилегию искать ошибки и взламывать чужие решения, но отказавшись от возможности перепослать ваше решение при каких-либо обстоятельствах (например, даже если вы найдете ошибку или вас взломают). Со временем задачи падают в стоимости. После системного тестирования учитываются только полные решения. Подробнее про правила соревнований можно прочитать по ссылкам:
Регистрация на олимпиаду Технокубок еще открыта. Победителей и призеров олимпиады ждут значительные квоты при поступлении в престижные технические вузы России и ценные призы! Если вы — школьник 8-11 классов и пока не зарегистрировались на Технокубок, то самое время сделать это:
Зарегистрироваться на олимпиаду →
После регистрации на олимпиаду не забудьте зарегистрироваться на Отборочный Раунд!
В финал соревнования будут приглашены лучшие участники каждого из отборочных раундов (но не более 45% от общего числа участников раунда).
Авторы задач — Александр Kostroma Останин, Александр Golovanov399 Голованов, Артем komendart Комендантян, Денис Denisson Шпаковский и Дарья Dashk0 Колодзей.
Для тех, кто впервые на 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 |
Удачи!
Раунд завершен, поздравляем победителей!
Технокубок 2019 - Отборочный Раунд 2
Codeforces Round 517 (Div. 1, основан на Отборочном раунде 2 Технокубка 2019)
Codeforces Round 517 (Div. 2, основан на Отборочном раунде 2 Технокубка 2019)
Опубликован разбор.
UPD: Лучшие 200 участников отборочного этапа Технокубка приглашаются в Финал олимпиады. Поздравляем победителей!
CF rounds on weekends are the most fun.
I feel the same
Perfect time for Chinese users!
..
It's not a weekend in most Arabic countries XD
it's not weekend in Iran too .
How many problems? When do we know the score distribution?
PD: Just a joke: Where is thanks to Mike and Polygon and ITMO??
Исправьте пожалуйста ошибку, сегодня же будет 2 отборочный раунд
Спасибо, исправили.
Elimination round(not CF) will be rated or no?
Rated
A really good time for Chinese users :).
very less participation :(
All who qualifies for the elimination round are not here.
now the round is delayed because of you
Sad :(
Delayed by 5min!
Before the contest 00:01 remaining
Me: Let's bring it on!
Before the contest 04:59 remaining
Me: Oh f**k.
At least 5 min
Thanks, I afraid something went wrong with my connection
delay :(
Score distribution?
I love contests at 3 am :)
I am not able to submit code, getting error "you have submitted exactly the same code before". Please someone look into this matter. I have not done any submission in that problem.
Please, check PMs
div2D was dp or bfs?
Both of them :)
I spent so much time on this problem and didn't manage to do it in the end, is there a way to compute for each
i, jthe lexicographically smallest path fromi, jton, n?I did it with dynamic programming. For each field you just need to know if you want to go right or down. So create a table
int dp[2001][2001]with 3 possible values: 0 — go down; 1 — do right; 2 — it doesn't matter (both going down and right will produce same string). We fill entries of dp fromn, nto1, 1(backward). how to fill this array? For boundary entries (i = n and j = n) it is obvious, for othersdp[i][j] = fillDp(i + 1, j, i, j + 1);Edit: arr = original array with letters
Computing path is just going with pointers in dp.
I can't actually prove it works in O(nm) but I got accepted. Here is my solution — a little more verbose: 44647952
What was pretest 15 in div2 C? :(
Something like 147694707 63714381
The sum m + n in this case should be 20562.
It works for me, and I got pretest 15 wrong. What's special about this test case?
I stress-tested my WA on pretest 15 with the solution that passed that test case to get that. I'm sorry that I don't see anything special about this test case :(.
Got 6 WA in that. But, figured it out. It was because of not using long long int.
300iq Becomes Legendary Grandmaster!!
Хайпожор
Ага
He won't dye his hair pink for a week.
How do you solve div2B?
DP by O(16n) I'm not sure it's a correct algorithm.
I did it this way, and it seems to work
Could you elaborate, please?
DFS is enough.
Sorry! I find a hack data to hack DFS. It is:
answer is:
I have hacked lots of codes using DFS to solve problem B. If we add this data for judging, a lot of codes will be hacked.
The reason why it can hack DFS is when a = 3 and b = 0, t can be 0, 1, 2, 3.
Sorry for my reckless. It seems my computer is too weak to run this data. I find that DFS is right to solve this problem. Very sorry!
Because if ti has been determined, ti + 1 will have only one value to choose. Specially, if a = 3, b = 0, t can be 0, 1, 2, 3. But if ti has been determined, we should not worry about ti + 1.
Brute force the value of tn. Given ai, bi, and ti + 1, it is easy to show that there can be at most one ti that satisfies the given constraints.
Yes, and ti equals ai + bi - ti + 1. Because x&y + x|y = x + y.
How did you get this relation?
By Binary Numbers.
x + y = x + y — x & y + x & y = x + (y — x & y) + x & y
Because any digit of x and that of (y — x & y) are different,
So x + (y — x & y) = x | y
So x + y = x | y + x & y
Wow, thanks!
Div2F / Div1D was bfs?
I finished fixing div2.D and the contest is over
Now, I hope my solution is not correct ...
Don't worry, it isn't.
Fine.
Not correct....
Lose to constructing.
How to solve div2-C , i tried bin Search but i knew it's not working good ,, any hint ?
Let
kbe the largest integer such that1 + 2 + ... + k <= a + b. Then it's always possible to construct an answer withn + m = k.thank you :D
Can you explain how?
Like before, we have
S = 1 + 2 + ... + k <= a + b. Just iterate overi = k...1and greedily subtract fromawheneveri <= a. IfS < a, then we're done, otherwise it should be easy to see that we can always get a subset of elements that sum exactly toa, in the end, so the sum of remaining items isS - a <= b.Why is it so?
It's explained in the editorial, perhaps more nicely than I can do here.
Ok thanks!
in B all a[i] and b[i] gives only two numbers except when a[i]=3 and b[i]=0 then t[i]=1 and t[i+1]=2 or t[i]=0 and t[i+1]=3 right?
I couldnt submit my last solution because I did not understand my new stupid error while debugging which is we can't write cout<<1&3; that gives an error and Idk why
when you type cout << 1&3 compiler reads << as bit shifting
man if my solution was right and i couldnt submit it because of that ... meh
edit: it's wrong anyway:P
I slept just 3 hours to take this CF, let's see how my C fares the system tests :Dd. Already had to resubmit once during the contest
How to solve it?
I use bfs for n ≤ 12. If n is greater than 12, find the last 1 appearance and modify it to make sure that at most two steps would be used to set the last 6 positions 0.
So did bfs on bitmask for n<=12 ?
Also when is answer "No" ?
When n > = 8, answer is always YES. So you can just brute and check if it's no for n < 8.
What was pretest 8 for div2D ?
How I solve Div2-C/Div2-A:
Write a greedy solution, get WA on test 15.
View submission detail and realize the checker's answer is not the same as the sample answer.
wow, very weak pretests again
Full Feedback contests are the best.
But remember that in most rated Codeforces round, you don't receive full feedback, especially when the pretests are weak :D.
I'm of the opinion that problems which are going to have very few solves anyway almost always ought to have virtually full feedback, i.e., the systests should not have anything special (new cases, etc) that the pretests don't have, especially considering that if you fail systest you get a score of 0.
It seems that div2C/div1A system tests are weak. After the contest I found a bug in my code that makes it fail : for the test
7 1it gives the following output :which is obviously wrong. And still my solution got AC. (tmw when you think that the pretests are weak but after the systests it turns out the systests are weak too xd)
Solutions should be rejudged if that's the case.
What is the answer to this case for C? LHiC's AC code gives NO.
My AC code gives
Weak tests
¯\_(ツ)_/¯Similarly, I resubmitted because my first submit uses too many operations in the case
(line breaks added for clarity)
But turns out my first submit would also have passed :/
Waiting for tutorial.
Waiting for my new rating... And of course waiting for tutorial....
Возьмут ли меня, если первые сто человек решили не меньше трех задач, 101-й решил две, а я нахожусь на 103-м месте с тремя задачами?
Здравствуйте, сколько человек берут в финальный раунд ?
The tests for div1 C seem to be so weak that some wrong codes passed.
44641451 The hack data is : 1 1 0 1 0 1 0 1 0 1 0 ...
Uhhhh that is the obvious "naive" solution that I didn't bother coding because surely it wouldn't pass right?.... but it does.
And then I didn't find a good solution during the contest :/
After more thinking I realise this solution is quite solid with a small tweak. If try it twice and take the best solution, once normally and once ignoring the first 1 (and do the first 1 manually later) then it is perhaps not possible to make a counter case.
Anyway there are like dozens of solutions and I came up with zero of them during the contest.
can someone plz tell me whats wrong with my code for Div2D?? 44650538
As I see, the problems and the score distribution in the Technocup Round and in the Div 2 version were the same. However, the scores obtained in the Technocup Round were smaller compared to the Div 2 version. For example, score 2500 is in top 40 in the Technocup, whereas in the Div 2 version, someone with 2500 is on the 200th + position. So I guess that participation in the Technocup would have helped you increase your rating more than in the Div 2 version.
Maybe the tests for Div1C are not strong enough
these solutions were hacked by my data.
44638710
44641451
44641456
data:
Update: Oh, after posting this review, I found that cuizhuyefei has already mentioned it
Well, after contest, I have found a hack data to hack DFS solution in Div2.B.
We just use a form like:
answer is:
If you use DFS to solve this, you will get Runtime Error.
If possible, please add this data to hack someone who didn't solve the question well, including me :-) . Thanks.
Sorry for my reckless. It seems my computer is too weak to run this data. I find that DFS is right to solve this problem. Very sorry!
I faced problem in B when ai =3 and bi=0 then ti and ti+1 can take 0,1,2,3 .can anyone help?
You can try to make first t( t1 ) be 0, 1, 2, 3. And the sequence will be constructed.
We can think about this:
If t1 has been determined, t2 will also be determined. Obviously, if ti has been determined, ti + 1 will be determined, too. For example, if ai = 3 and bi = 0, ti can take 0, 1, 2, 3. But don't forget that ti has been determined. ti will only has one value to choose, and it's easy to solve. Hope I can help you :-).
the rating changes is unfair. in official round if you solve just 3 problem you will get high rating changes but in Div2 round if you solve 3 problem your rating change is not as high as rating chane in official round.
I noticed that the announcement and editorial are not linked to the problems, can some admin do this? Thanks
Does anyone know if there will be a parallel open round again for the upcoming Technocup Elimination Round 3 in a few days?