Hi there!
Codeforces round #394 for the second division will take place at the time of Tuesday, 31 January 17:35 MSK. Participants from the first division can compete out of competition. Contestants will have 2 hours and 6 problems to solve.
- Problems were developed by me (Vladislav Vishnevki) and Denis Anischenko (altruist).
- Alexey Vistyazh (netman) helped us as a contest coordinator.
- Aliaksandr Drapko (sdryapko) and Alena Yaros were reading the statements carefully.
- Vlad Khala (haposiwe) tested the round.
- Olya Yakovchik drew amazing illustrations for the problems.
- Yuri Shilyaev (hloya_ygrt) translated editorials and round announcement for you.
- And of course the round couldn't happen without (MikeMirzayanov), the author of platform polygon and codeforces, and also author of the idea to one of our problems.
Thanks everyone listed for the contribution you made to the contest preparation!
The main character of the legends is tiger Dasha, which loves to solve puzzles and make origami figures.
Good luck everyone! :)
UPD Round will consist of 6 problems.
UPD 500-1000-1500-2000-2500-3000
UPD Contest finished. It was decided to make round unrated, because codeforces is unstable now. I am really sad about that :( I hope everyone found a problem he liked. Editorial will be posted soon.
UPD Top 10 participants from second division: 1. DefinitelyNotGreenGrape
2. udwztb804
3. Inhibitor
4. Border_Collie
5. HanwhaEagles
6. Vergara
7. zelta
8. GGOSinon
9. P_Nyagolov
10. tonykky
Top 10 participants from first division: 1. eddy1021
2. Myungwoo
3. dreamoon_love_AA
4. natsugiri
5. Shik
Congratulations to the winners!
UPD Editorial.
Will be easy contest to all of you, i feel
I am having my exams... but still eager to participate in the contest... Hoping for a positive rating change.
LOL
Tiger__the national animal of both Bangladesh & India. It lives mainly in Sundarban Mangrove Forest.
Too many Indians here to upvote you. Good game.
Not only Indians .. Bangladeshi too :)
And The Sundarbans ( Mangrove Forest ) is mainly in Bangladesh
It's time for me to change the color again :P
Let me introduce myself to you all:
My name is Donald John Trump the 45th's president of the great USA, but mostly famous as the father of Ivanka Trump in the past period I conquered the whole USA through the elections, and I raised a campaign called "Let's make America great again!!!" So now, i am planing to conquer the whole world, but it's you top rated American coders who I seek there help, the likes of:
scott_wu, ecnerwala, waterfalls, DemiGuo, winger, cgy4ever, zxqfl, lawrenceli, pacu, msg555 and others....
You should help me conquer Russia, and as a start with your help for your beloved elected President you will send me your Accepted codes in tomorrow's round, just to help me finish first in the round, and end those stupid pair of Russians tourist and Petr and that crazy china town boy who changes his handle every year jqdai0815, to end there dominance on the top standings...
Top American coders send me your codes or I will send my FBI agents, to kick your asses away from the USA borders...
God Bless you, God bless America, and Let's make America great again!!!
PS#1:
PS#2: I hope you liked my new hair style...
Your post is a bit too long to be funny :P
"You're all Russians to me, the blacks, the Jews, those blue, tree-hugging queers in the Avatar."
I'm a Russian spy, lol
In the email, it is mentioned that there would be 6 questions. Please confirm? I see above its five.
Round will consist of 6 problems.
I like six problem contests, it cause reasonable deviding scores as usual. Thanks.
As a Div. 2 contestant, I want to thank you for preparing the contest for us.
And since it's a Div. 2 contest and there will be a lot of competitors from both divisions, I want to kindly ask the Codeforces team to make sure we will have an acceptable queue and a responsive Codeforces. Thank you.
Nostradamus !
Very cute tiger, I like it. Where is it from or it was made by you just for the contest?
UPD: Oh, sorry, I usually miss the part which thanks people :))
Olya Yakovchik drew amazing illustrations for the problems.
#FurryDomination
To all Acmers, Last warning, if you don't send me your codes, then I won't let you travel to my country for the World Finals, I will be there alone to win the first place...
God Bless you, God bless America, and Let's make America great again!!!
At this rate you'll be able to get the worst Contribution in CF.
what is the score distribution?
Good luck lads !
Good luck!
Good luck amigos!
Hoping to learn something new regardless of a rating change. Good luck to all, and a big thank you to the contest setters for making CodeForces awesome
Site very slow
I don't think it's a good idea to make this round unrated...
It's such a pity that this contest of all faced technical issues. I really loved the problem set of the contest, and the difficulty level of questions was well balanced.
Thank you Codeforces!
I am happy to see this nice and cute picture for the first time :D
it's rng_58 profile photo :"D
It's a shame this round became unrated, though the problems A-E were all on the easier side.
I don't think the standings not working is a good reason for the contest to be unrated, it shouldn't affect a lot if anything.
I agree. Everything was fine but the standings. It didn't offer an unfair advantage. Therefore, it was a bad call to make it unrated.
Kinda feel like this was a waste of time.
Rooms were closed , so people who wanted to hack , didn't have a chance to !
Are you sure? My solution was hacked by someone.
Yes, it stopped working after about an hour and half from the start of the contest .So , you could have been hacked during the first hour and half
Aside from the standings, hacking was also influenced.
Also, while it probably depends on the person, in my case I do check the standings quite often. I happen to be a slow coder. So I'm tactical of which problems to solve (I won't have time to code all of them) and which problems to hack, etc. The standings serve as great reference to what problems can be approached quickly (not necessarily easily) and which problems may have easy to hack cases.
me passing problem E's pretest.
I think this error is not the first time. I think this site need to move to a cloud server like Amazon.
The first time I ever solve 5 problems during contest and it's unrated... FML
mine was 4 .
The same with me, bro. Five. Now I hope all of them will fail systests, otherwise — I want to kill myself
My internet traffic limit off, so I was pay going to paynet, solve 4 problems, surprise contest is unrated...
Yay my C didn't pass, I can now sleep at night
++++ XD
I'm thankful to this round that finally I found my long-lost twin)
If you're my twin then sorry but you'll never reach purple :D
Haha,cool joke.
tfw tyou don't know what your score is
Unrated when I solved 4 problems :(
I have the same situation(
It Was Interesting And Exciting,But hated problem B Explanation :/ took me 45 mins to start understanding, overall it was nice
Thanks
it is so painful that this round is unrated.
I am really sorry for you. Compared to what we see recently, your problems were so amazing :))
Edit: In my opinion, if what I wrote is correct, then E was way too easy for E. On the other hand, F is a very beautiful problem. I think I can solve it but the time wasn't enough for me. Can anyone tell me if I am right? My idea is to find some random picture which gives us a minimum distance. And if I find it, then there is surely some special photo which gives the same minimum distance. :)
Sorry, it was a kind of magic for me. We didn't touch the code around of standings about years. And today it started to throw exception in unexpected place. Additionally I'm out of Saratov now and it was impossible to fix it during the contest. For sure, I'll find the reason!
There were 2 problems here by my ideas and it is an additional reason for me to be sad today.
So, what about next contest?
When we can see standings?
should we wait for system testing?
А будет ли системное тестирование?
How to solve E? I started with root at origin and then going 1e16 far for level 1 in 4 directions, 1e16 / 2 far for level 2 and so on. There was a bug in my implementation, so I don't know if it's correct or not.
Really great problems though, thanks for the contest!
Yes, that's the main idea.
Man, it is nice to know that I got the idea right at least :D
I think I can start from random node (let's it'll be the first) and then my first step would be 2^28, the second 2^27 and so on, can't I? Even if my tree grows only in one side it will fit the requirements.
it's correct
I guess we should start from the origin first going
2^n
in four directions, and for each new level on the tree we should divide that value by 2.with 1e16 + 1e16/2 + 1e16/4 + ... + 1e16/2^(n-1) you will get integer overflow.
Thank you Codeforces!
very good contest i loved the problems . i wish it was rated !
This creature is going to be my nightmare for the next couple of days !
And Mike's too!
Isn't that rng_58's profile picture?
first time solved 3 problems, and unrated((((
It was a really interesting problem set actually , it's a bummer that it was unrated , although i don't see what does the standings page have to do with the rate.... thank you for this round but i hope it's rated
I wonder if the reason for the system error was the abnormal amount of hacks... did total hack counter overflow? :)
On another note: thanks to creators for the interesting problem set with nice difficulty distribution.
Constraints for problem A is pretty interesting .. my solution got hacked within 30 seconds of submission.
what is it btw ?
testcase for hacking is a=0,b=0
Problems were little bit easier as compare to other regular contest. But I think there was no problem in submitting answers and dashboard. Technical problem was only in room and standing page, So I think it is not a good decision to make this contest UNRATED.
Not being able to make hacks can be a big roleplayer in the outcome of the contest.
In addition, the site was even slower than usual today. I saw 502 — Bad Gateway many times too.
Can anyone tell me what was hacking test for problem A? As I understand the statement if the difference of those two numbers is at most 1, then there exists such segment.
0 0
Oh I see. Real edge case hidden in problem statement -_- Thanks for your response.
0 0 is the hacking case since the constraints mentioned l,r>=1
0 0, it seems. Since 1 <= l <= r, this is impossible
My first codeforce round ever is very memorable....
thanks mike
He has explained, that it was an unexpected error. Don't be sad, if you did so good this contest you can do next one as well. Good Luck
That feeling, when you were in top 10 and then notification tells you that the round won't be rated.
Ahah... But top 1)
Oh my god 141 successful HACKS only in top 10 !!! i don't see where the problem was with the round ... i think it should be rated.
no hacks! Just rock!
WHENEVER PROBLEMSET IS VERY NICE,WHY CODEFORCES DO CONTEST UNRATED?
SHIT! SHIT! SHIT!
i would pass out if my E get accepted !
same here bro :/
The odd thing is that the disabled standings somehow affects everyone, and the round is made unrated. Opening standings does not make you think faster or code faster. Does not make that much sense for me, I think.
The issue is say somebody locked a problem to hack. Now they can't hack, and say they find problem with their solution. Now they are very disadvantaged, because they have none of the benefits of locking problem, and all of the downside, by no fault of their own.
I must disagree. ~10 minutes before contest end, I successfully hacked a solution of a person in my room. So hacks weren't affected(standings couldn't be opened though)
You must tell me your ways, I must know, how could you hack a solution when the room standings were unable to be opened? Or are you staying that you were able to open your room standings, as I tried many times and was not?
Yes, I was able to open it. Maybe it's because you are Div.1, who knows? And looking at the hacks there have been some at 19:33, so it has been possible to do hacks during the (almost) whole time.
You know, some people could hack ≠ everyone could hack.
That's what I am talking about
I think hacking was the problem because room page wasn't working too. but I still think make this round unrated was not a good idea
Is it rated?
Sorry to interrupt, but don't ask if ...
can someone please tell me how to hack others solution? What i did was, locked my solution, then i didnt know what to do next. help please :(
you can enter your room then click on other contestants' solutions in your room and then click hack. Then a window for writing your tricky testcase will appear.
First you have to lock your solution.
unfortunaly, you are right
good problemsets :) I'm sad to hear that it's unrated, is it really because of the scoreboards?
Ok. Let's vote: Click
I read "Should CF Round #394 be rated?" and voted Yes. Oops D:
I hope Mike will see your comment...
MikeMirzayanov
Post blog!
I think the contest can't be rated again cuz there were many people like me gave up after the announcement :)
Problemset was very good! It's unfortunate that the round is unrated!
Can someone explain how to solve B?
If the sorted arrays are the same, the answer if yes.
Then let's move any player 1 step back. Subtract 1 from all the values in smb's array (remember that
0-1=L-1
). Check again. Shift again, check again, etc.Do it until you make a full circle of shift. Total complexity is O(L*N) or O(L*N*log N) depending on how do you handle sorting.
There is no need to handle sorting. They will always be sorted
My solution doesn't need to shift. 24304207
determine the space between all the barriers for Kefa and Sasha! Keep them in two vectors. Then compare one vector with another by rotating the elements of one vector!
Create an array of the distances between each adjacent obstacle in the array input. There will be two such arrays. The basic idea is that these two arrays should be a cyclic permutation of each other for the track to be same, and this can be easily checked by checking if Array B is present as a contiguous array in Array A appended to Array A.
If two tracks are identical , then the difference between every two consecutive barriers are the same. You calculate the difference between every two consecutive barriers and than you must find out if they can be covered in such a way that the differences are the same.
Thanks to all of you.
Assume that 1st person starts from 1. and then mark which points he visits ..
And then for the second person .. Check all starting points and find which points 2nd one visits.. if you find any solution where they both visits same points then print "YES", otherwise "NO"
Can be done in O(n) and it's super easy in python.
First find the lengths of all the intervals anti clockwise. This can easily be done by taking differences between consecutive numbers. interval1 = 2nd element — 1st element and so on..
After that append the first interval as L+1st element-last element
Make 2 such interval lists for both the arrays.
Now join both the interval lists to make a string.
Now you have 2 strings s1 and s2. If s1 and s2 can be found by rotating each other then it's the same track. To find how to do this refer to this awesome thread http://stackoverflow.com/questions/2553522/interview-question-check-if-one-string-is-a-rotation-of-other-string
My Python solution http://codeforces.net/contest/761/submission/24306742
You can make a string which represents places with and without obstacles. First make a string of length L:
',' x L
. Second change,
to e.g.o
in appropriate places. Make this procedure for both runners, got 2 strings. Finally instead of rotating first string, you multicat it by 2 (e.g.',oo' x 2 ==> ',oo,oo'
), and search if shorter string is found in longer one. Solution with Perl regex — 24394802Codeforces really needs to scale up to handle more users.
Yea sad, I ended up having to start the contest 3-5 mins late as the main contest page wasn't loading..
Will the next contest be held? :P
We wish you health,codeforces!!
ugh..
What does standings have to do with problems. Can someone explain why this round is unrated????
In a contest with plenty of hacks (such as this one) not having access to ROOM can change the outcome of the contest quite a bit.
I think it will be better for Codeforces to have some external servers like from Amazon or Microsoft (cloud). (Use it when it is needed) We had 8k registered users for this contest, probably, the problem is because of underperformance of current servers.
I think it will be better for Codeforces to have some external servers like from Amazon or Microsoft (cloud). (Use it when it is needed) We had 8k registered users for this contest, probably, the problem is because of underperformance of current servers.
Is the part of the code which records scores broken too? If not, why make this round unrated? Not being able to see standings is not a major problem.
Yes, that's true, our scores are shown in the room standings
I think there is problems with the room too, which influence the hacking as well.
I knew that round is unrated for me so I didn't worry a lot :)
Problemset was interesting, I spent two great hours !
Maybe better score distribution would be :
500 - 1250 - 1250 - 1750 - 2000 - 3000
P.S. I have no idea how did 350 coders solve fifth, for me it was pretty hard, not as usual fifth, but also it is not so easy :)
C > D in my opinion
I just used simple dfs to solve problem E
Yeah I have used dfs too ( I failed final system testing, I do not reason, I will see). But also you need some constructive algo to put points on good distance, I do not say it is hard, but I spend 1 hour to solve it :)
EDIT: I forgot one pair of brackets :(
WTF ?! why unrated ? I spent 2 Hrs of my time for Nothing ! :D
How so? What is more important — your rating or the competing experience you gained? Rating will go up and down, but the experience stays. And even if you value rating more, the 2 hours was well spent even for the experience.
You know ! I need more rate ! Experience is an important but I need some rate :) I was able to do many thing at that time ! Right ?
Do you really want anything else in 2 hours instead of solving these great problems :/
Told you, am here to conquer codeforces and Russia...
I just want to leave this comment by yeputons, 4 years ago:
WHY THE HELL?
Good problems, great social platform, but still going down during rounds. What's the problem? Slow code? You're programmers, optimize it! You cannot, because you need 'readable' code? Damn it, the website doesn't work during rounds, who cares about program's code if it doesn't work?
Too much users? Set limit of participants, like TopCoder do. At least rounds will be reasonably rated.
Not enough servers? VK offered you, not even once. If your code is good, it should be easy to scale on 10 servers.
Please, stop being prideful and make Codeforces a stable system!
Easy to say, tough to do! Well, I do agree with your points, but i think MikeMirzayanov and his team is putting a lot of efforts in making this platform better! And BTW it's still BETA! :)
I think codeforces should be made opensource.
I agree, here's a lot of great programmers who are able to make a good contribution to the platform.
I must notice that that particular comment was written in a rage and is pretty emotional and non-respectful, which I'm sorry for.
I'd like to advise future commenters to refrain from using that as a reference.
I think you want to advise to refrain from using that as reference.
Fixed, thank you.
lets play never have i ever !
never have i ever became this happy to see my solution failed !
How to solve C?
You can use Dynamic Programming with N*M*64 Time complexity
Or just bruteforce.
DP -> http://ideone.com/PaBMNW
For each string calculate the minimum distance to each kind of character. Store each distance in an array. For example, if the ith string is "a8*", then the arrays will be like:
dist_letter[i] = 0;
dist_number[i] = 1;
dist_special_char[i] = 1;
After that, we can iterate through all the combinations between the indexes of the arrays and get the min possible answer. (0, 1, 2), (0, 1, 3), (0, 2, 1), etc
You can calculate that with recursion or simply 3 for's.
Here's my code: http://codeforces.net/contest/761/submission/24320657 (failed it in contest because I was trying to acess an invalid position of the array lol gg)
Typed '$' instead of '&' and still passed pretests for problem C :(
Edit: Just submitted by correcting it and I am happy to see that it was not the only bug :)
Solved 4 questions for first time. Contest become unrated. :(
Div1 guys now feel satisfaction :)
Hints for problem E?
Hint: The all edges' length can be formed of 2^n like 1, 2, 4, 8,..., 2^32,...
Depth-first search the tree with arbitrary root, let the length of edge at depth d be 230 - d.
How to solve F?
I think round was unrated because:
Standings are unaviable even for codeforces admins -> They can't calculate new rating(it is based on your position in the ranklist) -> Round is unrated
Now it's working, and they can recalculate rating. Link: http://codeforces.net/contest/761/standings
Click
There was access to the room, wasn't it? Codeforces lagged sometimes, but it's as usual. Let's make all of contests unrated because of Codeforces lags.
I couldn't access the room during most of the contest.
Can anybody explain why my code is giving WA on test56 in c++11 while giving "accepted" in c++14 ? http://codeforces.net/contest/761/submission/24300137
You probably just got lucky with C++14. In
if(v1[x]==v2[j])k++;
, sometimes j becomes >= v2.size() in your code. (for i=1 in test 56) resulting in undefined behavior.PS: This code gives "NO" on both C++14 and C++11 on my local compiler after adding
j%=n
. PPS: AcceptedAfter every contest, I hate myself for not being able to solve the problems.
After reading the editorials, I hate myself even more for not being able to solve such easy problems -_-
fml
There was one more issue.People in my room were able to hack even after their solution was hacked.
That is intended behavior.
No, I meant that this user hacked other users and then his solution got hacked even after that how he could he was able to hack more people.Is it intended?
As far as I know, you can hack, if you could lock your submission even if you were hacked.
Yes, this is the intended behaviour
That screenshot is of my hacking. Notice, that I managed to get payback mere 13 seconds after getting hacked myself :) That was a coincidence though.
My biggest issue is, if almost all of the comments are saying to make it rated, why wouldn't they make it rated?
This would be unfair, because they announced that the round is unrated halfway trough the contest.
When 25 minutes were left. I think it's still ok
Let's make this round rated again! :D
Solved three problems for the first time. Contest becomes unrated. FML
This time lots of Hacks :p !!!
SOLUTION TO PROBLEM F
I just've got it ACed. In short words:
O(n2k) time and memory (hence the unusual ML), where k = 26, the alphabet.
Separated, each of these problems is easy enough to solve. That is about 100 lines of different array tricks, just code it carefully.
please tell me hoe to solve A
Consider the thing that a and b can both be 0 at the same time.And there is not any 1<=l<=r which satisfies the condition. My solution got hacked because of this. :(
Yeah me too. I was so frustruated when i got hacked. Took me ages to find out.
I guess D can also be solved using binary search here is my solution.
Yes, i also solved using binary search but little different from yours http://codeforces.net/contest/761/submission/24327048
It can be solved by greedy too :24329320
Can you explain the idea of your codes? Thanks!
first you should notice that compressed C shows the position of the Ci after sorting array C.
so the one Ci who is bigger than all other Ci s number 1 in compressed C.
let Pi be the position of number i in compressed C;
so C[p[1]] should be the biggest .thus b[p[1]] should be small as possible .
so b[p[1]]=L(cause it's smallest );
also you now that c[p[i]]>c[p[i+1]]
so c[p[i+1]]<=c[p[i]]-1
now we know that b[p[i+1]]>=a[p[i+1]]-c[p[i+1]].
we greedily take the smallest possible for b[p[i+1]]
(if a[p[i+1]]-c[p[i+1]]<l b[p[i+1]]=l)
(or if a[p[i+1]]-c[p[i+1]]>r there is no possible number for b[p[i+1]];
so we do it with all i and get the array b (sorry for bad English);
I got it ! Thank you very much ! :)
Greedy for D.
I have applied brute force approach in problem C. I am shocked to see that it passed within the time limit. Can anyone tell me why is it not getting TLE? Link to my solution. http://codeforces.net/contest/761/submission/24319247
Why getting TLE ? whats wrong with it ?! n & m <= 50
The new year I will become more powerful.
Why isn't there any editorial of this contest?
Editorial?
Can anyone figure out what is wrong in my code for problem C. Is is giving wrong answer on test case #5 http://codeforces.net/contest/761/submission/24333316
You have 2 bugs:
1) '0' — also number.
else if(c[i][j] >= '1' && c[i][j] <= '9')
->else if(c[i][j] >= '0' && c[i][j] <= '9')
2) Some characters may not be in line. For these lines you must make big value in
temp
.int p1 = n+1,p2 = n+1,p3 = n+1;
->int p1 = 10000,p2 = 10000,p3 = 10000;
Okay i got it right but I have one more doubt when I change p1, p2 & p3 to INT_MAX it gives me wrong answer. Why is it so?
You add
temp[j][0] + temp[i][1] + temp[k][2]
. If temp equal to INT_MAX, then you have overflowThank you so much
When we will get Editorial...
Problems in the round very good.
Can someone explain how to solve F?
In order to quickly compute the difference between a picture and a group of pictures at a certain pixel, we can precompute the sum of pixels in different cases (LT or GT the pixel), thus getting rid of the absolute value function. If we "stack" all the k pictures together (which each of the pixels carry k color values), then this action could be used between any pictures and the whole set of picture. (Note that we don't care if the picture being compared is also in the set, why?)
But comparing pixel by pixel is rather slow, to improve this, note that if an area is a uniform color, you could treat that area as an pixel to compare over the area on the set of pictures. For the remaining area which has arbitary values, as they are the same for all pictures if not affected by the paint action, so we could precompute the value of the difference between the original picture and all other pictures. Then, to compute the difference between a editted picture and all other picture, just replace the precomputed difference of the editted area with the value computed by the comparison method mentioned above.
2D Prefix sum is sufficient for storing and retrieving the values. Here's my rather ugly code: 24339537
Thanks:)
linkhttp://codeforces.net/blog/entry/50107?#comment-340677_
Please could someone help me to better understand the hacking procedure?
I thought that only solutions of people who locked their problem could be hacked. I did not locked my problems but my solution was hacked. Is this behaviour intended or is it a bug?
Thanks.
Only people * who locked their problem * may hack, but they may hack any solution.
And id somebody is hacked before they locked the problem, they may submit again.
Thank you! Would there be additional penalties if I submitted a right solution after the hack?
This question is about the "penalty for being hacked" doubt in the example below:
First case:
Second case:
No difference from resubmitting yourself
btw, you didn't mention penalty for time of submission. It's here in both cases
The this the round the was the good. (should have written it right after the end)