Hello Codeforces community!
Codeforces Round #318 (for both divisions) will take place on August, 29 at 19:30 MSK. It is the Thanks-Round devoted to Russian Code Cup. You will be given 5 problems and 2 hours to solve them. Scoring will be announced close to the round. I strongly recommend you to read all problems.
RussianCodeCup is the largest open programming competiton for Russian-speaking participants by Mail.Ru Group. Its history started in 2011. And since the first championship RCC offers great problems and generous prizes. This year finals will be held on September, 19th. Wish good luck to all the finalists! Thank you, RussianCodeCup, for your gift on the 5th anniversary of Codeforces!
I am honoured to be a problem setter for this round. I wouldn't do it alone. I want to thank Zlobober for his great help with problems preparation and MikeMirzayanov (and all people working on Codeforces and Polygon) for this awesome site. It's an amazing place to learn and compete. My big thanks to winger and AlexFetisov for their help with testing a round. And to Delinur for translating statements. As you see, not only a setter creates a round.
It's my first Codeforces round but not my first problems here. You can check out A, C and D from VK Cup 2015 — Round 2. Also you might remember some of my problems in TC rounds. I'm very happy with finally preparing a full round for Codeforces and I hope you will enjoy it. I tried my best to prepare nice and diverse problemset, you will judge it. In all problems you will have to help Limak who is quite unusual bear.
I wish you great fun and no frustrating bugs. Looking forward to seeing you!
UPD: Scoring is 500-1000- 1750 -2000-2500 in div1 and 500-1000-1500-2000- 2750 in div2. Enjoy a round!
UPD: Editorial
UPD: Contest is over. The winners:
Div1:
Div2:
- cescmentation_folch (5 problems solved!)
- fhxb520630 (5 problems solved!)
- bugCollector
- Sehnsucht
- okaduki1
And note from an author. There were some wrong solutions passing. Sorry for that. I tried my best to create strong tests but I failed a bit. Did you like this round? What do you think about problems?
Thanks for participating!
No T-shirts ?
like hunger games
T-shirts for Div2 only :P
Now all Div1 participants will create a new account :D
Oh No!
T-Shirts!
But I'm in Div.2.
求虐!
You solve a lot of users' problems in the blogs...
Wish we can solve your problems too ;)
I love Russian ,I love code and I love cup ,it's should be interesting :D
You love Russian,Code,Cup ???
But,But what about Taylor ?
I don't love him ; she is my life :D
him? she? shemale?
Maybe we should study your previous problems well, to get a whole look of the style of your problems. Maybe?
Hmm... interesting idea. Then you see some algorithms and techniques there and what does it mean? That it's likely to appear again or that I won't use something similar?
Errichto you are great coder how i can mail you ? guys please dont vote down
http://codeforces.com/usertalk?other=Errichto
Good luck to all participants (Codeforces Round # 318 — Russian Code Cup). I wish you a good mood during the contest and rankings.
translate: I need upvotes , plz :)
translate: I need upvotes , plz :)
translate: I need downvotes._.
translate : I have nothing to do
translate: I too need more upvotes please
Can you plz stop that?
Considering the previous round i think it will be better to do dynamic scoring.
Considering your downvotes I think it will be better advertisement if they do static scoring.
I think someone is getting ready to get first in this contest. to : sorry_dreamoon Be careful. You have a new mission : Antoniuk
I hoped this Contest for T-Shirts but ... TT.TT
LOL Guys you are so worried about T-shirts as if you can win them)
I wish you great fun and no [frustrating bugs]. Oh yeah we all know where this will be going.
This round takes place at the same time as the "Red de Programacion Competitiva" marathon :(
I think that I love This contest
Actually although all problem statements in qualification and elimination rounds was in Russian two Japanese coders advanced to finals (rng_58 from third place and anta from 21st) :-)
Easy one for rng_58 :)
Is the statement in Russian only?!?!
No :>
the stupid one who saw he can't translate, to have upvotes i wish you can translate this comment ************
to : sepiosky.
please translate.Maybe I'm not a good translator.
Problems will be in English? or not?
It will be normal codeforces round.
Excuse me if I am wrong, but this guy prepared for VK Cup Round 2 one easiest and two hardest problems? If he did than this is real intriging.
I had some tasks and they chose the most interesting ones, that's it.
This is usual round, guys. Statements will be both in English and in Russian.
Thank you roundwriter! Can't wait to see this round! :)
Lets hope Errichto prepares a great editorial as well as a great round for us . In the past few contests he has helped a lot of guys through his insightful comments . ALL THE BEST :)
Hopefully, it won't be another Div 0 Contest.
And don't get fooled guys. It will be like last round. In last round, there was a "PPS" stating top 20 of div 2 will get t-shirt, even though they didn't mention it before contest. I guess they are taking things another level higher. Saying no t-shirts now and then giving top contestants t-shirts later :D
Or, they won't be giving any and I am just over thinking. I won't be getting t-shirt either way...
Guys, can you please tell me how can i add my school in my profile . Thanks in advance .
Here: Your profile > Settings > Social > Organization
(If I understood your question hehe.)
'Newbie' zone.... be prepared for me.... I'm almost there... ;_;
Never care about rating, your goal is to solve as much problems as you can.
Your challenge is against the problem setters. :D
Looks like, the problem setters are winning ;_;
You are very sarcastic, may be i wish could upvote you 100 times :)
Think positively; solve one problem and its your win!
Are people happy that the problem setters are winning?
I believe that not care for you and you are my hero :))
Hey.... What about me?
You can both be his hero.
You can't lose -127 rating in one contest.
That's very reassuring ;_;
Doesn't Lose -127 rating mean gain +127 rating?
I've gained +143 , but so far, didn't lose that much.
someone should make codeforces fantasy league ,just like fantasy premier league in football ^.^ ,we can bet on favourite coders to win the round
Every one will bet on tourist and every one will win the bet :P
Tourist will bet that "he won't win" and he will intentionally lose to win the bet :)
That will be clear to all and it will be considered as cheating, :P
Wow! But, why should anyone even participate in something like this? Betting doesn't sound nice, besides, how will it help us?
sometimes people do things for fun as well
Like, hunger games?
Looks like your guess came true today :/
Bear Limak will cause us trouble...
Looks like something interesting will happen with the bolded problem scores
Why 1750 and 2750 written with bold font?
Because usually this problem costs 1500(2500 in div 2)
What is the real difference between the knowledge level of a Blue guy and a Red Guy ? ?
I think knowing more algorithms and more exposure to thousands of problems!
They read a problem, and by the time they've finished reading the problem statement, they have the solution. That's the difference.
Even we have a solution to 2-3 problems but when it comes to 4-5th problems ,atleast I do not have any knowledge about the paradigms! Obviously they are better than me but Even I solve every problem related to the scope I have! Same is with everyone !
I feel like there is something more than that :P
Because I have been coding since one year and yet blue :P
They can visualize problems better. They are insightful , and can code bug-free in their first attempt .
Bug-free on the first attempt... I wish.
Don't forget to mention: Even a green coder can solve Div2/A immediately after reading. The real difference is the complexity of the problem between that a red coder and a blue coder can code immediately. :D
And I guess that comes through exposure to algorithms and problems..
Practice and lot of practice!!
Yes, I think practising improve the level of your immediately solving ability. :)
Ohhh, nice div1 registrants list ..
Where rooms?
There is guy who is printing "YES" or "NO" (in capital) in Bear and Poker . I tried to hack his solution and it gave me unsuccessful hacking attempt.Why? Its written in problem we have to print like this: "Yes" or "No".
?
"yes" and "no "
are usually case insensitive
I think Codeforces treats "Yes" and "YES" same and vice versa for "NO".I read it somewhere in comments sometime ago .
It's not that Codeforces treats them similarly. Round writers are advised (I think they are) to use the checker which is case-insensitive unless they have strong reasons to have case-sensitive output. And most of the times this checker is being used indeed so (mostly) it doesn't make sense to hack such solutions. It should have been clear today that hacking "YES" <-> "Yes" doesn't make any sense since participant's solution passed pretests which would never happen in case of case-sensitive checker.
There might be some lee-way. The fact that the solution passed the pretests should have made it clear that your hack wasn't going to work though.
I guess you should be awarded for designing the first anti-tourist contest ever! at least till now!
The first? Are you serious?
Previous record was 24, now it is 168 :)
and when he was ~20, rating decrease was about ~130.
Of course he's serious, did you look at your own link? Notice how tourist's worst performance ever is 24th and he came 168th this round?
Yes, but I think AliB's comment was posted before tourist fail D, maybe I'm wrong. Anyway, you're right.
not able to hack
Забавный сегодня день...
Отравился, проспал до 6 вечера.
18:00 — 20:00 — решил 5 задач на Тимусе.
20:00 — 01:00 — решил 6 задач в тренировке.
01:00 — 02:00 — решил 5 задач на Тимусе.
02:30 — 03:50 — решил 5 задач во втором дивизионе (первым и впервые решил Е) и занял первое место до системных тестов.
10 часов подряд решаю задачи...
UPD: Эх, E упала...
UPD2: Идея была верная, но оказывается надо было сразу обработать "соплю" из подряд идущих вершин, а не ждать когда БФС не с той стороны по ней пойдёт.
Ты съел что-то не то и мутировал, теперь ты супермозг
dreamoon_love_AA hacked my A. Feel so honored!
He hacked me once. I was angry.
Its better then getting WA at the end of the contest. dreamoon gave you one more chance. I think you should be grateful to him.
You're right. Sorry Dreamoon. :)
You mean sorry_dreamoon? :D
I knew someone will say this. No, i mean, i apologize, to Dreamoon. ;)
The problems are so nice, thanks for the contest!
I liked the problemset, but I've no idea how to solve Div1 D or E. Anyone want to share approaches?
I really hate when someones solution has overflow but when you try to hack it , it passes your test but is wrong and should give overflow in this test.
UPD : 12760657 it didn't pass the full tests.
Also some guy fooled me with
#define Int long long, lol.You shouldn't be fooled if you know that
Intis notintI wonder if this is a common thing. I always use "typedef long long Int" but I've never seen someone else do it, at least from the competitors in my country :P
Was this contest easy or my skills have improved ?
Couldn't hack (or fail) because of lags at the end :( Div1 A-C look quite easy compared to other rounds. Though I failed to implement C..
This is the first time I solved A,B,C and had half an hour left. Thanks for that!
D (div-1B) was super easy too. I've implemented seg. tree, but when I looked at the other solutions, I realized how stupid I was =)
Just curious. What's your seg tree logic? Please share. :)
For example if
aequals to{2, 1, 2, 1, 2}thenbandcwill be:Now let's build 2 segment trees using
bandcto find minimum.It's easy to prove that:
And the result will be
max(ans[i]).P. S. Yeah, I know, it's overkill ^_^
Overkill or not, if it passes, its worth a try :)
Actually, I don't see how your min(...) is so obvious. It took me hours to understand the problem setter's solution.
edit: Instead of
for (int i = 0; i < n; i++) c[i] = a[i] + n — 1 — i;
why not just
for (int i = 0; i < n; i++) c[i] = a[i] — i;
?
And, min(...., tree(c,0,i-1) + i ,....).
Check it again. Anyway Congrats.
Yeah, my B failed :( . The pretests passed, and now I will debug it.
Am I wrong or there were no -50 points if you submit a solution that fails on a pretest from problem's sample tests in previous rounds?
Not all sample tests in general; only test#1 doesn't count.
Thanks!
I pressed submit when there are still 20 seconds left but didn't submit my code successfully....... So sad T_T
Same here. I tried to submit my code when there were still 15 seconds left, but the submission page didn't load. I just checked that my code was correct.
And that code get AC....
Edit: It' problem E T_T
The problem set was commendable for me, especially the idea of problem C. Cheers!
C was easier than B , don't you think?
I was talking about div 1.
I was a bit late submitting div1 A because I didn't believe that it's that easy(specially after div1 A of previous round) and I must be understanding it wrong or missing something , anyone had the same situation?
I had similar situation with div2 A but the constraints were too low and I got through.
Yes. I questioned myself for 1 min.
My first thought was that it was made this way intentionally — after all those complains which we saw several days ago: "People can't solve A and they ignore contest, their rating doesn't change — and I am losing rating with solved A".
Good guess.
Lol no, A's are almost always trivial x_0.
I was trying something like dfs to detect 3 member cycles for Div2-B and finally the flat O(n^3) got AC Suffered 3 WA and around 1.5 hours :(.
n^3 AC?
So is this the first time tourist gets a three digit rank?
I did beat tourist with 6 points!
Tourist doesn't always win every CF round.
But I have only done competitive programming for 9 months, let me be happy :(
I've been coding much longer than that, and I am still green. You are a legend by my parameters :)
I said it's the first time he got a 3 digit rank.
Please read the question er... comment carefully.
I commented on JonStraat's comment :)
Haha
Sorry, my bad!
You should be careful now, who knows what tourist does with those who beat him...
lol
Probability of that you can beat tourist in next round is very low
It wouldn't be special if the chance were high.
Well, he gave 167 people a contest to remember.
Thank you tourist!
Can anyone please tell why my submission is giving runtime error? It is working fine on my local ide.
Submission link : http://codeforces.com/contest/574/submission/12757848
You did this :
you allocated a vector of size N*M instead of N*N.
Thanks. But i still don't understand why this case is working on ideone :- https://ideone.com/JTSkfy
Overflowing is unpredictable.
I was so glad by fast solving Div1A (3 minutes), but in result couldn't solve Div1B, though it is not much harder than Div1A:D
But really nice problems. Thanks!
What a contest? Tourist gets 3 digit rank, Petr only with 2 correct submissions until 1hr 45min. Kudos to the problem setter. PS: My personal opinion on the problem set is that it was very good. Since C was easy nobody would have ditched contest as a result of not solving any of them.
Some O(qn) solutions passed Div1 D, and one O(n2) solution passed Div1 E. I think more tight time limits for those problems are necessary.
In D we didn't see any O(nq) with low constant factor and we wanted
to pass (some solution with bitmasks).
For E we had a O(n2) solution with many tricks to speed it up and it was still far from AC.
Two big mistakes :/
Thank you for the fun problems.
That was a wonderful round. Fast Editorial and nice problem set.
Can problem B div.1 solve by divide and conquer too?
I was thinking the same. Since the structure can be split on the shortest tower, given its height is less than its distance from the boundary, it looks like a D&Q problem.
http://codeforces.com/contest/573/submission/12750074
Задача A. Мишка и покер ***** В задаче сказано что нужно выводить Yes, участник выводит "YES" на чем я его хотел взломать Получил неудачный взлом. Пожалуйста уточняйте в условии что может существовать не один формат вывода.
Это вообще нормально, и где это указано?
Ну претесты у него же как-то прошли? :)
А если бы у него где то вывод был "Yes" а где то "YES" и я в надежде на то что в пре-тестах нет такого случая решил его взломать... :)
у меня тоже так,хорошо что так зделали а то кто-то пишет правильный код и только "YES" на "Yes" перепутал и получает wa.
А разве на контестах за WA на первые претесты снимают баллы?
На раундах codeforces при непрохождении первого теста из условия и ошибки компиляции попытка игнорируется.
Вроде бы только при непрохождении первого теста, не?
Прошу прощения, вы правы.
Первый раз такое вижу... Но можно было догадаться о результате взлома раз уж человек смог претесты пройти.
I hope rating update is as fast as system test and editorial
maybe problemset was good but there is a big differece between a — b,c and d — e div 1.
Hi,
Div2 B
can anyone tell me what's wrong with this solution? http://codeforces.com/contest/574/submission/12750750
Edit: one of my friends told me the problem... Using set.lower_bound() to search can lead to set.end() as the result which when I compare to a number can lead to false result. http://codeforces.com/contest/574/submission/12769046
I didn't like having to help a bear politician cheat in div 2 Problem A.
Could someone explain this code? http://codeforces.com/contest/573/submission/12760770
I don't think that's something our mortal minds can comprehend.
I guess he really is a machine like his username says.
It's clearly a brute-force, but seems to be incredibly sped up. The first trick is alignment of the variables in memory (some variables are told to be aligned to 16-byte blocks) — it probably helps cache do its work more efficiently (less cache misses and so on).
The magic part (inner loop) uses SSE (set of processor instructions which allows many operations to be done at once; why do 100 000 32-bit additions/shifts/comparisons when we can use 128-bit SSE registers to do only 25 000 operations?). You can probably decode what it does here. I guess one can write a simple brute-force and then "encode it" in terms of SSE.
Still, a question to the author: have you worked for a CPU/GPU manufacturer?
Is there a similar way to exploit SSE in Codeforces for other languages (I'm particularly interested in Java)?
How much faster would C++ be compared to other languages for this problem?
In my opinion, in Java SSE intrinsics make no sense (Java source code is compiled to Java bytecode which is then run by Java Virtual Machine; you have no access to JVM code, so you cannot optimize it by hand — for example using SSE code).
I have no idea how other languages compare to C/C++. However, the fact is that many of them may lack support for the intrinsics and thus we won't be able to control the power of SSE.
Actually alignment is required for SSE instructions to work.
Thank you for your explanation. In addition, I think those techniques are not needed if our submission runs on 64-bit systems.
I have not worked for a processor manufacturer, but I have a bit of experience of performance tuning on CPUs and GPUs.
Did author suppose that local optimization should pass in E?
Sry, ignore that comment.
Did author suppose that O(nq) should pass in D?
:)
those restriction seem to show that.
We didn't see any O(nq) solutions with low constant factor. All of them were far from AC. And we wanted some
(which also had big memory complexity) to pass. It turned out to be a bad decision.
I didn't.
It seems that the test data of E is really weak and should be fixed.
This obviously wrong solution of HYPERHYPERHYPERCUBELOVER passed 41 out of 42 tests, and the 42nd test is so small that it could be solved in O(2NN). (maybe it was added during the contest..?) He got accepted with the same solution with some minor modifications.
You can find more obviously wrong solutions which got accepted after the contest..
One specific example from HYPERHYPERHYPERCUBELOVER:
This solution from Marcin_smu gets wrong answer for this test:
The optimal answer is obviously - 1 × 1 + 3 × 2 = 5, but it prints
3.This simple test could have been made even using a random generator!
Marcin_smu, are you proud of your victory :D?
It's not my fault :) You should ask Errichto, whether he is proud of his tests.
;_;
Do you plan to add more tests for our practicing purpose? :)
It's possible so I do plan to do it.
I hate to wait for rate; but it's late and it's my fate.
you like hate?
It seems that in problem C there are no tests with maximal degree 3 and answer NO: 12766417
But such test exists and is quite simple.
for example
will i go with rank 108 div1?
1689 not 1700 :(((((((((((((((((((((((( ;_; OH NO
Finally red!
I know that feeling :)
High five!
And at the same time a better rank than tourist , enjoy the moment :)
So you joined quite recently and have become very good quite fast, could you give some background on yourself, like what age you are and so on? You obviously practice a ton, have so many solved problems having joined only 9 months ago. Anyway it is pretty inspiring to me what a lot of practice in a short amount of time can do.
I'm old, I started when I was working on my masters thesis in maths since I realized that I weren't really qualified for any jobs and I didn't want to do research. But at least it shows that it is never too late to start programming!
Две пачки Лимака автору контеста
Why the problemset and the gym are still blocked?
UPD working now.
Really nice problemset! Natural and short (but yet original) problems which were really fun to solve or interesting to know the solution :) Thumbs up!
screencast of the first AC in the contest (1:23, problem A)
dear god..
Why not more? Can you upload the whole contest?
I think, a subscriber's screencast will be more interesting =)
And here it is.
Looking at amount of testing you did — you seems to be pretty confident about your solutions :)
... no luck, just skill. (c)
Btw, I've trained that skill during some of my streams =P
Сheater! :)
What about
return cout << "No", 0;?Wonderful!
Master again.
После раунда статусы у всех отправленных решений изменились на "Попытка игнорирована". Что это может означать?
Может это из-за того, что ты пытался считерить? :)
Вот эти решения кажутся похожими: 12750277 12751825
Вряд ли это из за задачи B, потому что мое решение тоже похоже на эти два =)
Хм, и правда похожи. Shit happens :(
In future (t-shirt giving) contests, we could state that there will be t-shirts for div2 after the contest, in that way, there won't be div 1 people here, and div 2 guys can also have a chance to win t-shirts.
Мне кажется что это хитроумный план tourist-а, залажать на контесте. Что бы все снова начали о нем говорить, а то теперь когда он выигрывает никто не удивляется(он же Гена).
I tried to hack a solution of the problem C. It showed invalid input. Can someone help? Link: http://codeforces.com/contest/574/hacks/164504/test
You print endl before the last number, instead of after it...
For example, if n was 5, your code would produce:
Oh thanks! But I tried using endl in the end also and still got Invalid input. Can you show me the code, how it should be?