Добрый день!
В воскресенье, 18-го ноября в 19:05 по московскому времени состоится Отборочный Раунд 3 олимпиады для школьников Технокубок 2019. Раунд будет длиться два часа, участникам будут предложены 6 задач. По его результатам лучшие участники (но не более 45% от общего числа участников раунда) будут приглашены на финальный этап в Москву. Для регистрации на раунд и участия перейдите по ссылке. Не забудьте заранее зарегистрироваться на раунд! Для опоздавших будет открыта дополнительная регистрация (с 19:15 до 21:05).
Зарегистрироваться на Отборочный Раунд 3 →
Соревнование открыто для всех в виде отдельных раундов для первого и второго дивизионов.
Для всех участников всех трех редакций этого соревнования будет пересчитан рейтинг.
Параллельно с Отборочным Раундом будут проведены открытые рейтинговые раунды для обоих дивизионов, в них могут принять участие все желающие.
Напомним, что согласно правилам раундов Codeforces во время соревнования ваши решения будут тестироваться только на претестах (предварительном и неполном наборе тестов), а системное тестирование состоится после окончания раунда. Обратите внимание, что претесты не покрывают все возможные случаи входных данных, поэтому тщательно тестируйте свои программы! После прохождения претестов у вас будет возможность заблокировать решение, тем самым получив привилегию искать ошибки и взламывать чужие решения, но отказавшись от возможности перепослать ваше решение при каких-либо обстоятельствах (например, даже если вы найдете ошибку или вас взломают). Со временем задачи падают в стоимости. После системного тестирования учитываются только полные решения. Подробнее про правила соревнований можно прочитать по ссылкам:
Регистрация на олимпиаду Технокубок еще открыта. Победителей и призеров олимпиады ждут значительные квоты при поступлении в престижные технические вузы России и ценные призы! Если вы — школьник 8-11 классов и пока не зарегистрировались на Технокубок, то самое время сделать это:
Зарегистрироваться на олимпиаду →
После регистрации на олимпиаду не забудьте зарегистрироваться на Отборочный Раунд!
В финал соревнования будут приглашены лучшие участники каждого из отборочных раундов (но не более 45% от общего числа участников раунда).
Задачи придумывали и готовили: Александр Golovanov399 Голованов, Евгений WHITE2302 Белых, Александра demon1999 Дроздова, Арсений craborac Кириллов, Иван ifsmirnov Смирнов, Артем komendart Комендантян, Роман Roms Глазов, Дарья Dashk0 Колодзей и я.
Большое спасибо за тестирование Григорию vintage_Vlad_Makeev Резникову, Ильдару 300iq Гайнуллину, Илье irkstepanov Степанову, Андрею AndreySergunin Сергунину.
Для тех, кто впервые на 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 - Отборочный Раунд 3
Codeforces Round 522 (Div. 1, основан на Отборочном раунде 3 Технокубка 2019)
Codeforces Round 522 (Div. 2, основан на Отборочном раунде 3 Технокубка 2019)
Спасибо за участие!
Опубликован разбор.
Clashing with CodeChef Cookoff. :( Too bad none of them can be rescheduled.
Feeling sorry for codechef :P
I moved to codechef after codeforces crashed. Bad day for codeforces
Feeling glad I choose cook off this time :P
And now I wish I had given the cookoff instead. Bad luck :(
It doesn't seem open for everyone currently. Div.1 and Div.2 versions says "Registration is private" too.
(Fixed now)
Чем отличается Div1 от Div2 ?
Div2 — рейтинг участников до 1899 включительно. Div1 — рейтинг участников от 1900 и более.
Please update c language compiler, it doesn't work for some questions
Please reschedule clashing with cook-off!!
As always we enjoy the short statments but, what about amount of problems or score distributions? Thanks!!
How many hour it will take?
It is scheduled for 2 hours.
Does anyone know where can i search for a specified category and see different problems on that category starting from easy to hard ?
https://a2oj.com/
You can see different categories where problems of each category ordered by difficulty and the website the problem belongs to.
You can also take a look on the ladder page for general problems also ordered by difficulty.
You can add tag to search section at "Problemset" and sort the problems by difficulty (the orange symbol).
Will there be any interactive problems?
OMFG IS IT RATED?
not sure if you're joking or you can't read english
zOMG WTF is it rated please i want to know so i know if i can know to participate or no! :( ty
THATS EXACTELY QWHAT I ASKEDFM THE HOST BUT HE NO RESPONDE!!!!
WHATEFK what WE DO????
Looks like you're the one who has brain damage.
african kid look at you fucking rating before comment! noob!
excuse me but that's racist :).
I just have one doubt, I am almost sure that, codeforces admins are fully aware of the fact, that CodeChef is having contest on sunday at 9:30 pm from more than 2 years continuously,
why in the world, CODEFORCES HAS CONTEST EXACTLY AT THE SAME TIME !!!!!! :P :P :P
is it rated man
You have brain damage man
I hope I will be candidate master today and shahidul_brur will gain +100.
Who else couldn't access this site for the last 30 min? Is there any way I can report this?
It was like 10 minutes...
Maybe it was shorter, you're right, I mean it felt like 30 minutes to me :p
Yes, codeforces was unavailable. KAN, will the round be rated?
Yes
ok, is it still rated after the second server error (and you don't give any extra time for us)?
i can't even submit my C
should be unrated dude
But my rating.....
Hm, now when more serious problems came we have to declare the round unrated.
Why not considering rated for submissions before server issues? Everything seemed okay before 90 minutes of contest.
Due to the second crash (cca 10 mins after first one), I recomend stopping the competition in it — then rating will be moreless fair, as people had time to send their solutions during previous crash and there is almost no advantage for people who had the problems opened offline.
Unrated Pls! I can't read the statements/submit/hack for an hour!
Ok! Now I can't read the statements/submit/hack for 80 mins! Farewell! Expert nervend!
What about people who left contest? More than 20 minutes of downtime in 120 min contest is enough to lose interest. should be unrated IMO.
IMO, they should change the ratings only to those who would get a raise.
Solved G but can't submit. When CF back it's over... Even this comment took time...
Btw, will 3nlog23n pass G (Chattering, Div1. D)? Update: TLE :( Updated to 3nlog3n at query stage and worked.
In fact, It could be passed it you try to shorten the time[submission:45958962]
Yes, and can even shorten more by relation
.
Found a typo in my code 1min before the end of contest, opening (already loaded) problem page in browser, click "Submit" tab and see "502 Bad Gateway". Perfect!
The site was down even during the extended time. Not able to submit question D. Is it still going to be rated?
With constant "502 Bad Gateway" this round was quite unpleasant for me.
502 Bad Gateway...
the 30 minutes extension did nothing because the site was down during the whole 30 minutes anyway
Is it going to be extended again? The site was down at least for the last 5 minutes of the first extension period and it was impossible to submit during that time.
In my case, it was down for a while, then it came back for a few seconds with the message "The round is extended for 20 minutes.", after a few second later, it's gone again, and came back after the ending of contest.
Awesome, isn't it?
Oh, my fu**ing God ! This contest and up-time is absolute sh*t.
I spent 15 minutes trying to submit in the last of the second hour AND COULDN'T EVEN OPEN ANY PAGE during additional 20 minutes.
What was the point to add them if it's still COMPLETELY UNACCESSIBLE ???
It would be disrespectful for the community to make them pay with the rating for CF server issues. Feel free to comment if you agree it should be unrated
Calm down. It’s only virtual points. Nobody is disrespecting anybody.
Писал технокубок в 2017 году, третий тур, половину времени кодефорсес лежал
Пишу в 2018, снова третий тур, не успел отправить задачу так как последние минут 10 сайт лежал.
Каждый раз как в первый раз...
Website was down even during the extended time, for the last 30 minutes or so. Please it should not be rated.
You're unrated anyway what's the big deal for you?
With constant "_502 Bad Gateway_" this round was quite unpleasant for me.
I have solved the problem C but I can't submit it in last 20 minutes
same problem man,
No for first and yes for second question :V
Bad connection round... I've solved problem D, but Codeforces was unavailible. :(
Guys, let’s not downvote the post. It’s not the problemsetters’ fault that the servers were down.
You just reminded me to downvote the post.
ɯoɔ˙sǝɔɹoɟǝpoɔ
That moment when you realize the two mangolian accounts had a point in asking if it's rated
Is it rated? Codeforces had 502 for a long time!
респект за отсылку к Гражданской Обороне!
Hа неведомой поляне тает одуванчик, а в оскаленном сердце зреет невыносимая лёгкость бытия. невыносимая лёгкость бытия. невыносимая лёгкость бытия.
ООООООО МОЯ ОБОРОНА
Не факт что именно к ней. Есть еще роман, который называется также.
SUCH A SHAME
The round should 70% be unrated from the first server issue. The second one, ironically fell right into the extended time, just further confirmed the validity of that decision.
I even can not submit in extra time. It's unfair if this contest is rated.
How about judging until certain time (e.g. before the site went down, or at least without the extended contest timeline?) Since the contest went pretty smooth in the first 90 minutes. We can disregard the next 30 minutes which was down most of the time anyway.
Phucc dis shiet nigguh
I feel so bad for missing the special case in B where the input contains only two different values. Spent 60min on that while I could have easily done D in less :(
OH MY GOD THAT WAS IT?!?!?!?!?!?!?!?!?!
Xablau Fatal.
unrated...
Is this contest rated ?? :D ??
I have been delayed and do not know when codeforces website working again. So bad
Guys, sorry, it was unexpected dos-attack (
I believe on codeforces always.
Are they ever expected?
That's OK,but I realy don't want it rated.
Lol, what kind of an asshole doses Codeforces?
Ok, my suspicion is that tourist was afraid of losing first place in overall ranking to Radewoosh, so that was his last resort.
What did you say?
That tourist shot himself in a foot xD
OK, MY SUSPICION IS THAT TOURIST WAS AFRAID OF LOSING FIRST PLACE IN OVERALL RANKING TO RADEWOOSH, SO THAT WAS HIS LAST RESORT.
It's like the dumbest way to waste electricity
Someone who wasn't able to solve nothingg but the first problem in 90 mins :D
EDIT: I should refresh the page before replying — it showed me "a moment ago", because I spent 5 mins reading the others.
What reason for attacking codeforces?? For fun, or is it another CP site)))0)0)?
Why not just deploy the site on some well-known third-party platform such as AWS or something similar? These platforms are run by big companies and, as such, have very good stability, handle traffic better, plus a lot of security features (including DOS mitigation).
What is the reason for not doing this? I honestly can't remember the last day in which codeforces wasn't broken for at least a few minutes. It doesn't have to be like that... I get there is a cost-component to using these services, but as far as I know it's not significant and it would really improve the user experience.
So basically, if you want to have high rating, you should just DOS attack the site unless you do well on the first hour and a half or so. That way you never lose rating!
You forgot about failing systests,
That's what the time machine is for.
Errichto, is that you?
(p.s. He'd have an incredible rank drop this time.:)
contest will be rated or not
My best performance during a round so far. Probably would've gotten at least a +300 rating increase. Too bad there were server problems. It probably sucked for others. Oh well. That's just our luck, we gotta move on.
Since you did so much better than your current rating, surely you will earn a good rating increase next contest :)
It doesn't work this way :)
I'm just trying to be positive okay :|
DELETED
Two previous rounds were also organised by 3 rounds at once (official, div.1 and div.2), but CF was stable.
But sum of number of participants is nearly same as in div1+2 round...
I think that it should be rated for people that are going to get some positive rating. They wasted their time participating and it will be unfair not to reward them somehow.
Serious, unrated for all :((
I mean I agree because I did great on this round, but doing great once wouldn't really change much. You can have 1 great round and not compete for a year and your rating would be "high", but it wouldn't really matter because it wouldn't represent your real skill.
Sadly, the main problem is that it's not the first time it happens.
Yeah, that sucks. I rarely have time to participate in actual contests so when there are server problems during that time it's like a slap to the face.
So round 485 had the same issues and was rated and this one won't be. What's the logic of choosing if rounds are rated or not?
MikeMirzayanov KAN
Please do rated, please!
talk about my luck the day i solved four problem site went down,and contest unrated
How unlucky am I? Returned to Codeforces after 13 months to solve a rated round and possibly became violet, quite succeeded — currently 119th before system testing (even when I had to wait for 15 mins to send prob. D), and it was all a waste of time :-(
EDIT: Murpy's law really holds — all Accepted, final rank 88th.
I feel so sad that I stay up late in China, only to find the contest unrated.
I have a college quiz tomorrow, I still found time to give contest only to find it unrated
Upgrade your damn servers. This is like the 100th time this shit happens. It's bloody irritating for people with negative rating if it remained rated, and EVEN MORE FUCKING IRRITATING for people with positive rating when it's unrated. I am seriously starting to hate CF, it's my favourite and I don't want to hate it, but this, this is absolute shit.
Yeah, for the longest time I thought CF rented servers dynamically from AWS or some other cloud provider. I heard that was what registration was for.
Then the ITMO move post came around and I realized it's still basically running on a bunch of PCs in a garage.
In that case, what's even the point of registration, if your compute power is constant...
(Although in this particular instance I believe it can be forgiven because it was apparently an attack.)
what do you mean by attack?
Странно же делать раунд нерейтинговым только потому что последние минут 15-20 сайт лежал
А разве последние 15-20 минут не было основное время для посылок по задаче D? Судя по комментам, не я один не успел отослать решение на задачу D.
laugh on my luck the day i solved 4 problems ,site went down and contest became unrated,why today????
make it rated ! at least for the guys with rating raise or something like this !
because they have do good and get rating in the contest is the prize for them !
agree with you please make it rated!!!!!!!!!!!!!!!
that's impossible, for someone rise other need to down.
Почему бы не сделать кнопку для всех участников "сделать для меня раунд нерейтинговым, так как я пострадал из-за технических проблем", и давать её использовать в подобных случаях. Конечно да, некоторые пользователи могут начать её абузить в случае если просто плохо порешали раунд (не из-за технических проблем) чтобы избежать падение рейтинга, но зато честные участники не будут страдать из-за этого.
Ты из себя чеснтого не строй.
Как же это верно
Даже вот более детальная реализация:
во время раунда или сразу после жюри (авторы раунда, координатор, бог cf) могут решить, что раунд следует сделать нерейтинговым
если это произошло, то в течение N-о количества времени после окончания участникам нужно будет решить считать ли раунд для них рейтинговым (надо только понять что сделать в приоритете по умолчанию (а еще лучше сделать настройку в профиле что выбирать по умолчанию в подобных ситуациях))
только после окончания N-о количества времени начинается системное тестирование (чтобы участники не могли делать свой выбор на основании упавших задач)
после этого у всех участников происходит пересчет рейтинга так, как будто бы раунд был рейтинговый, но изменяться рейтинг будет лишь у тех кто выставил у себя раунд рейтинговым
Thx for servers, nice job
Автор ты чуч.
Нужно найти определенный компромисс о рейтинговости контеста, поскольку было потрачено время, все были в равных условиях падения сервера
То есть получить полностью незачтенную задачу вместо 5 очков штрафа — это честно? Для пары людей, один из которых решил задачу на минуту раньше и успел отправить до падения серверов
Am I the only person who think that task A was a little bit difficult for 500 points?
Yes.
The actual problem wasn't difficult, but the statement was definitely a bit too long and confusing.
C < A for me.
Why can't codeforces use services like "cloudflare DOS protection" ?
Else, they should have some system for rating in such contests. (and provide problems statements in a dropbox/drive)
Cloudflare costs money.
I think codeforces is sponsered by telegram.
There’s a free tier.
Again, That's what happens when you forget to thank MikeMirzayanov
I am glad that I switched to Codechef. And also my bro Mr. shahidul_brur was supposed to get -88. So, I am glad for him too that he is still blue.
is Div2E like this:
If number of distinct elements <= 2 then answer = n
Else, First compute dp[i][j] denoting number of ways to form a subset of sum i, using exactly j elements.
Now, put each element in map cnt. And for each key, iterate over the number of times to pick that element, and check if dp[key * times][times] == ncr(cnt[key], times) then take max of all such times for every key.
How do you compute the dp table? I got stuck at that part
dp[i][j][k], where i is the starting from item i, j is the weight left, and k is the items left to pick. dp[i][j][k] = dp[i + 1][j][k] + dp[i + 1][j — w][k — 1] the second term is only if you can pick item[i]
I did like this
That's my solution. But the dp should be dp[i][j][k], where i is the starting from item i, the other two are as you said. I couldn'y submit so I am still not sure if it is AC.
After you compute using dp[i][j][k], you just require dp[i][n][k].
dp[n][sum_weights][num_items]
my dp definition was:
dp[i][j][k] = number of ways to form a subset of sum i, using first j elements, and picking exactly k elements
Aha, mine is starting from item i, j is the weight left, and k is the items left to pick.
Just a confusion, sorry.
If the number of distinct elements is 2, then we need to make sure that their sums are different first.
It's not required since, in case of two distinct elements a1 and a2 with freq c1 and c2, just query with sum = a1*c1, total=c1, Now you identified c1 elements. The rest elements are c2. or you can do vice versa.
for n = 6 with the following a_i:
2 2 2 3 3
just query for total weight = 6, and number of elements = 3, then you know the remaining weights are 3,3.
Or, you can query for total weight = 6, and number of elements = 2, then you know the remaining weights are 2, 2.
so, we identified all elements using 1 query.
Oh sorry, my bad :'D
dp[i][j] could be the maximum and minimum value you used to form a subset of sum i, using exactly j elements. Now if max == min, it's a good one, and update your answer. I think is easier that way. And you avoid possible overflow issues. EDIT: AC code
I have thought in this problem like you, but can't the value of dp (and also value of ncr(cnt[key], times)) be very huge? it can be something like ncr(80, 40) which will overflow.
I thought of taking the DP and nCr values mod large prime number to minimize the probability of collision.
I thought of this too but I wasn't sure about the probability of collision as I haven't used this technique much.
Just got accepted using MOD 1e9+7
http://codeforces.me/contest/1079/submission/45941195
mohamedeltair, my observation was correct. Momentum's solution without MOD.
You can ensure 0 probability of collision by keeping values modulo multiple co-prime numbers. I used 2^64, 10^9+7 and 10^9+9 here and was able to squeeze within TL using O3 optimisation level. This is enough since their LCM > 2^100 > C(n,r). Thanks to CRT, there will be no collision.
Instead of using 2 primes in the order of 109 you can just use one large prime of the order 1018 since the modulo is performed for addition operation only (no multiplication).
Right. That submission was during contest and I didn't remember there is no multiplication, so I just used 2 primes of 10^9 order. Using one prime will certainly speed it up. Thanks!
Some cells in dp table will surely overflow, but some will not, but our answer will be among the unoverflowed cells. If you observe carefully, you know that ncr value will always be less than or equal to the dp value. And for each key in map, we are iterating times in descending order, i.e from cnt[key] to 1, as soon as we met the condition, we break. The dp value where we break should not be that large imo because for large number of picked items, number of ways will also small. Not sure though.
Can you provide any case where it might go overflow?
If you are iterating on times in descending order I am not really sure that it will overflow, but I have no proof that it won't.
Just got accepted. it didn't overflow.
http://codeforces.me/contest/1079/submission/45942726
I solved it by counting too, but if the count of anything is more than 2, I set it to 2.
I tried this approach at first but my dp was working on the original elements (take the element at position i or leave it) so it didn't work. Your dp is working in a different way (take i elements from value v where i ranges from 0 to count of v), this considers i elements from value v one time only in contrast with the first dp which considers the i elements nCi times. Well done!
Best codeforces round ever, i totally didn't want to submit problems. What i really wanted was to waste 2.5 hours of my time. Should have chosen cookoff...
Why didn't you want to solve the problems? I think the tasks were nice (except div.2 A).
I solved 5, but i just didn't feel like submiting. I'd rather waste 2.5 hours and not be able to connect to codeforces for most of the contest.
Why don't you make contest rated only for those participants who hove positive rating change? I believe that's what CSAcademy did once(ore more) when it was some technical issues during the contest.
Rating inflation.
Anybody cares?
Yes.
Lol, why care too much about the rank? Codeforces rank can't help you get a job, to get money, to help your family and your future. Be realistic guys, spend less time on cf, go sleep early instead, get a healthy life and prepare for your future. They are more important than b***** cf color.
Actually, codeforces rank CAN help you get a job — it is quite common to append these things into CV if you are good enough.
Look like kids on Codeforces are butt hurt. at least 55 idiot users just press downvote instead of reading. I said nothing wrong here! you can't just spend all day doing codeforces, then put your handle into your cv! you have to train many other skills to get the job, not only problem solving. I gave you a healthy advice, you ignore and press downvote! okay you shit head kiddo just stay with your cf dream
Bruh, first time seeing you so enraged throughout the times.
Still, I fully agreed with your points. It's not that Codeforces rating doesn't matter. The problem is that people cared "too much about the rank", causing them to lose consciousness of the surroundings, the issues that makes the round unrated (c'mon, even Mike don't ever want such to happen, and that being said, could you ever expect a DDOS?), and the better designs behind the system.
Many Codeforces users are weird. Instead of improving the speed to comprehend and solve problems, they chose to increase their speeds on blindly judging people's opinions. Just increasing speed, the other aspects, no improvement, if not neglecting them.
thank you bro. i just want to point out that cf rank doesn't matter much. When i see my opinion getting unreasonable downvotes, i feel uncomfortable, so some of my reply may be off topic. Again, don't bother too much about this cf rank. Whining about missing a rating change, or wasted efforts for unrated round seem really stupid, because as i said, this rank doesn't have much meaning for your life.
at least for high school student like me, training in CF give me more opportunity to compete in IOI (and help me to perform better to). which will help me to get a better university for better job
OK, maybe slightly more on topic, how do you solve A?
Div. 1 I hope? dp[i][j], where i is the current number, and j is the finger for that number. Check dp[i-1][0], dp[i-1][1] and etc. Also we need to have dp1[i][j], where we put the number of previous finger. It is important to make output.
It is the one with the manhattan streets and the diagonal street
I don't know. I have a solution, but I'm not sure is it right.
We will do binsearch to calculate, what is the most optimal point on the diagonal street to go from the point A. Then just binsearch what distance we will cover on diagonal street. Here is the answer. Don't forget to calculate a case, where we shouldn't use the diagonal street.
Find intersections line ax + by + c = 0 with lines x = x1, x = x2, y = y1, y = y2. It's easy.
If shortest way is on diagonal then you can split path in three pieces: A-diagonal, diagonal, diagonal-B. A-diagonal ends at either first or third point. diagonal-B starts with either second or forth point. So you can loop over two points and find minimum path.
P.S. Nevermind. I'm failed)
P.P.S. Now I'm glad that round is unrated))
P.P.P.S. evermind about my first 'Nevermind'. It was just stupid overflow. My solution is correct.
It isn`t much of a surprise. Every time I do good in a contest, issues like these arise..
The best CP platform in the world should be stable and safe from attacks etc. Such a disappointment.
I don't know, many want it rated, many dont. But the the round must be fair. Many struggle with poor connection, solve problems and get their good rankings but they dont get anymore rating, it does not worth their effort. So I think people with positive rating should be awarded
Or at least count rating gains/losses at 0.5 times the original change.
If you reward just the people with positive ratings, you contribute to rating inflation.
Plus, ratings on codeforces are calculated comparatively. You might get more points than you deserve because you placed better than another contestant who WOULD have placed better than you IF there were no connection problems.
That is why "make is rated for people with positive ratings" will never work on codeforces (within the current system).
P.S: the problem wasn't "poor connection". There was no connection at all. The service was denied.
Хорошо, что раунд не рейтинговый и будет 4. Но надеюсь лагов на 4 раунде не будет. Хотя я не против 5 раунда )
Может, я не в теме, но где написано, что будет четвертый?
пришло оповещение от кф. Зайди в соревнования и в 3 раунд там про это написано в оповещениях
Спасибо, буду знать (хотя я и так уже со 2-ого тура прошел)
Lol, n=1 is really absent from pretests in D xD. Fortunately I got this one right, but this alone should be a sufficient reason to declare that an unrated round :P.
EDIT: Ah, I didn't manage to send my D in time anyway even though I got it right well before an end of extended round xD
If my solving is failed on a test with a huge data(10000 numbers), is there any possibility to see the whole input, not only cutted part of it?
No
Problem C. Playing Piano
This code got accepted , but this is a wrong code
http://codeforces.me/contest/1079/submission/45940667
Case n=1 not handled, like this case
input
1 50
expected output : any number from 1 to 5. my output : 50.
KAN can you check this ?
Does D2C have a greedy solution?
What do you mean by greedy? In one pass? Of course
Er no, that's not what greedy means. Greedy means choosing the locally optimal solution to subproblems every time. That probably won't work here since the subproblems are overlapping (locally optimal != globally optimal), and even if greedy did work the DP solution is much simpler.
It is a little bit complicated for me, but i guess the simpliest solution just follow the direction adding or substructing 1, and every time when direction is changing change previous number to 1(or if not possible to 2) in case of increasing and to 5(or to 4) if decreasing... and thats it...And of course you can not know what is the next number so you can not make choose optimal solution before it. (sorry if i didnt get, i dont have strong mathematical background)
Wow, I didn't think of that! You're right, that is a greedy solution.
Sorry,I don't understand what "(or if not possible to 2)" means,I just change previous number to 1 but got wronganswer.Just like 8 5 4 3 3 4 5 6 7
It seems that Div2E has weak cases. I sent my solution assuming that the maximum sum is 5300 (It should be 100*100) and got AC. Code
Test on C task: 1 1 hack my code, but i got ac, add this test.
How to solve D?
My solution (slowest in time comparing to other solutions): triple the array to get rid of the rotation, build log-step trees tr[i] where each tree will answer the span [l, r] of cells x..y after 2^i seconds. After the trees are ready, calculate results from cell n+1 to n*2:
at cell n+1, do a binary search for the minimum time (min 1 max n) so that span length is not less than n; in each check, use the trees to expand the range in log(n).
for remain cells, as the different between adj cells cannot larger than 1, we can check for result in last-1,last,last+1.
In problem B why is this case incorrect (the difference of * is at most 1)
Test 87
Participants Answer
5 17
aoNtJAeHshvQrvwRg
ZHkrdxwyaaHOIsyEM
xtRNkM*ifYfRoRbam
pjmPoUVpN**JvSvEy
aQjEvGcRAJJS*PORp
Jury Answer
5 17
aoNtJAeHshvQrvwRg
ZHkrdxw*yaaHOIsyE
MxtRN*kMifYfRoRba
mpjmPoUVpN*JvSvEy
aQjEvGcRAJJSPO*Rp
the pairwise difference of any pairs not just consecutive rows must be at most 1
btw using 'i.e.' in the statement to give an example is confusing and wrong
thanks so much got it
You can't write two * side by side in a row. that's why you got wa
sure you can as long as the difference between rows is at most 1
Why are you downvoting this post? I can't understand codeforces community voting behaviour.
I read the problems, and they are good. I know that the round is unrated, but is not the fault of the setter.
This post was published after technical issues last year. MikeMirzayanov can repeat it
About Codeforces Round 445 and Technocup 2018 — Elimination Round 3
Huh, it was Technocup — Elimination round 3, too? This looks to be more than a coincidence — but why would someone want to ruin this Russian competition?
Hello, could anybody help to find how to download full input data of the test #23 of "C. Playing Piano" problem? It's 100000 elements, truncated in the rendered html.
You can't download full input data for testcases.
But I can tell you that your constructive algorithm approach is too complicated (and probably won't work always), try DP instead.No, it works, fixed a bug, got AC in submission #45944625 it's O(N), no DP necessary for this problem
My mistake, I guess this is why I didn't get the problem during the contest :|
If you want to find where is fault in your algorythm check is it that test by checking first 100 symbols of input, then when you find that in some position answer is -1, instead of output -1 output 10 numbers before...Hope you got idea
well... I don't see the reason why codeforces doesn't allow downloading tests after the context is over. It would be so much easier instead of following such hacky dumps. The bad story is that my algorithm depended on both forward and backward scans over all numbers, so in my case 10 additional numbers would not help much. Thank you anyway
Everytime vintage_Vlad_Makeev handle mentioned, I see color changed. Such a legend. This is consistent rating change here.
When will the editorial be published?
6 hours passed, no editorial. Maybe 504 bad gateway...
Вот интересно, задача Е — это отсылка к роману или к песне Летова?
In the div2D . i forgot to think that either a=0 or b=0 ,but i got AC i think it shoudle be RE,because sometimes the denominator is 0
How are we supposed to find out whether or not we are invited to the final?
On techocup site, where you have registered for this olympiad
Thanks
How to Solve Div2-D?
If !a or !b, the result must be the Manhattan's distance between A and B. Else, let res be Manhattan's distance between A and B, the result is min(res, dis(A, PA) + dis(PA, PB) + dis(PB, B)), with dis(A, B) is the distance between point A and B, PA = {points stay in the avenue that have the same x or y with point A}, the same goes to PB.
how to find the points in PA/PB i tried Binary Search on the equation. my implementation doesn't work...
if you want to use the line ,you should go to the line directly .Therefore, PA is the intersection of A along the direction of the parallel coordinate axis with a given line. So PB is.PA and PB both have two possibilities.
go to the line directly but how to find the points to go on to the line..
like if given point is A(x,y) and B(s,t) my choice is go to (x+p,y),(s,t+i)/(x,y+p')(s+i',y) how to find these points...
There is no need to use binary search, just replace the value x and y respectively of points A, B in the equation.
ax + by + c = 0.
So, you get points {x1, -(c + x1 * a ) / y } and so on.
Replace A's x or y to Avenue's equation and you get another y/x, that's how you get PA! Yay math is so easy!
EDIT: You can check my submission here if my explanation is still unclear: 45935987
Thanks a lot.. Silly me.. I wasn't thinking straight ..
So,where is the tutorial as the problem is too difficult for me ?
How to solve Div2 Problem C ??
Here is the most naive solution:
First, understand whether it is possible to create such a sequence b or not. Loop through a and if you find 6 or more consecutive increasing or decreasing monotonically numbers, output "-1". If you find 5 consecutive increasing or decreasing monotonically numbers and the one preceding all these 5 or the one that follows these 5 is equal to his neighbor from this subsequence, output "-1". Otherwise, there exists such a sequence b.
Going from i=0 to i=n-1, for each a[i] compute b[i] depending on how this a[i] compares with a[i-1] and a[i+1], trying to put the greatest possible numbers at the beginning of each decreasing subsequence of a, the smallest possible numbers at the beginning of each increasing subsequence of a, and the middle numbers, such that 2 or 3, in each constant subsequence (you should alternate 2, 3, and 4 in order to save 1 and 5 for the previous 2 cases).
Thanks for your efforts. But can someone explain DP solution for this problem?
Let dp[i][j] be true if you can reach position i of the array with final finger j and false otherwise. Also dp[1][j] is true for all fingers j. Then, you can see that if dp[i-1][f] is true for some valid finger f (f is a valid finger if the rules allow you to move from f to j in position i), then dp[i][j] is true. It is possible to play the entire array if some dp[n][j] is true for some j. Reconstructing the solution is quite trivial.
Problem B was really nice
catch with test 4.
Editorial ?
Problem Div1A/Div2D "Barcelonian distance" is very similar to the problem of the Spanish Informatics Olympiad 2018: "Barcelona distance"