Codeforces round #305 is gonna take place soon and I'm the writer.
After my previous contest that many people think it was a hard contest, I prepared an easy contest to cheer you up!
I want to thank Haghani for testing this round, Zlobober for help me prepare this round and his great advises, Delinur for translating problem statements into Russian, mruxim and Yasser Ahmadi Phoulady (Rasta) for their advises and ideas, HosseinYousefi for helping me choose legends and graphics and MikeMirzayanov for great Codeforces and Polygon platform and guys from Physics Olympiad that kept disturbing me while preparing this round.
This is my second official round and I hope you enjoy it.
The main character of this round is gonna be Mike (I didn't say MikeMirzayanov :D).
Also you'll meet Xaniar and Abol.
I wish you all Successful hacks and Accepted solutions and high ratings.
Scoring will be posted soon.
GL & HF!
UPD: Scoring is:
- Div.2: 500-1000-1750-2000-2750
- Div.1: 750-1000-1750-1750-2500
UPD2: Due to technical reasons we moved the round by 5 minutes.
UPD3: Contest has just ended. You can find the editorial here.
UPD4: System testing is done.
Congratulations to the winners, specially dreamoon_love_AA that got to his goal !
Div.1 winners:
Div.2 winners:
See you in the next rounds.
Was looking forward to this :D
huury up programmers! register! just 4700 person??
We Want ratings!!!!
UPD: We Want DIV2 Ratings! also we have final exams tomorrow(today!)!
UPD2: disappointed from RATINGS! it's 1:30 passed and nothing happened :|
I'm also waiting for rating instead of sleep. UPD: rating changed.
First time to rank good, ratings delayed... FML
Finally dreamoon_love_AA got first place in Div1!
No body read the end so I commented here :/
The first round was awesome ;)
which round was it :D ?
Codeforces Round #299
I see new person in the first place on contribution list!
Your problems are great! I couldn't participate (I was in school), but next contest I won't miss.
I have only one suggestion : please make final test cases stronger...
I like your problems pretty much.Hope to see more interesting problems :)
In my idea A and B should be solved by at least 1000 people(easy), But C,D and E should be harder. Not like the recent div2 contests that more than 1000 people solved A,B,C,D! :D
It is interesting that the author thinks about the complexity of the tasks
Does this round involve CoffeeMix? :D
Why isn't the post on main page?
he fell from the first place on the "Contibution list". "Let's prepare a new round to go first again", he says! :D
It's great to see that there is always a unique sentence in your blog!
The last one was thanking yourself! This time is about the guys from Physics Olympiad!
Your last round was Amazing :D wish this one be better ;)
Div.1 ,long time no see!
good job (Y)
I think it will be a very interesting contest. Because the author of this contest PrinceOfPersia. I think there are a lot of hacks. ('_')
Sorry for my poor english.
Your problems are great, they only need a little more concentration :D
In last round you came up,
anyway gl
Opps :/ ,My bad.
I was confused between PrinceOfPersia's round and this guy fcspartakm's rounds >_<
and good luck to u 2 :D
Wow, this round has Div.1, great!The time gap between Div.1 contests is so long, hope Div.1 contests will be more frequently.
Ehm, there were many div1 (some div1 only, even) rounds before. Don't expect an even distribution of contests.
Just hope Div.1 contests will be more mush.
sorry for the comment... my friend troll me.
please ...
I can't stop looking at those adorable characters.
Your last Round had one problem with weak test cases as i mentioned here
I wish this one be better
"Yasser Ahmadi Phoulady" what a legend ! :D
He is our (Me and PrinceOfPersia) teacher. Show a little respect.
is legend in your dictionary an abuse ??
your comment sounded like an abuse
It's Persian's Magic :D
It's farsi not persian learn your countries language
You Can Check Persian In Translate.google.com And FUS :)
they should call farsi, farsi not persian !!!
I don't understand why you keep insisting that it should be farsi not persian. Actually the name "Farsi" started to being common because the Arabs couldn't spell "P". So the word "Persian" is more likely to be the original one. : )
sorry the time i sent that comment i was a child !! now i've grown up!! :D
Yasser Ahmadi Phoulady Rasta Actually. Rasta is part of his name not Nike name or something else.
His first name (in passport) is Yasser, but everyone calls him Rasta (Rasta is not part of his name).
it would be more legendary if it was! :-"
i dunno if what you said is good or bad but i assumed that it was bad and downvoted you
You Have Big Problems In Understanding "LEGEND"
yes i have big problems thus i downvoted you
I Dont Give A Fuck About It :)))
you did that's why you placed a comment here :))
i upvoted this because i think you didn't mean anything bad but i dunno about neverless
You upvote or downvote is just related to your self. Don't spam please. :-"
i downvoted this xDDDD
:|
I really waited this round.
Why did you give me minus? Did I do something wrong?
Can someone tell me what did I do wrong?
wrong: you wait for round. correct: round waits for you.
Thanks!
Cheer up, but not too easy :D
A contest from a 3rd highest contributed user of Codeforces and also a red coder in a year !!! Eagerly waiting to compete the round and hope I will stay in division — 1 after this round .
this account Athee registered 16 min ago, trying to down codeforces ?
how?
I prepared an easy contest to cheer you up!Then why Div 2 C and E have more points than usual? I don't have a problem with harder problems, but your actions should follow your words.
Scoring is related to other contest problems, not other contests problems.
does it mean that this div2C/div1A is harder than 299's div2C/div1A ??
contest synchronization with Persepolis football match ):
Have a look here. There seem to be a lot of missing-a-match-for-a-contest stories there.
Next contest will be on Champion's League time
+1
Good luck all!
Why delayed?
laggs
To get the participant numbers in both divisions to be nice and round!
Delaying the rounds is really really annoying!
better than start coding late because of delays onsite :D
There are 3 times more Div 2 registered contestants than there are Div 1
1600 and 4800. Wow 6400 in total
1600 Registrants in Div1 and 4800 in Div2. Is there any limit or is it just a lucky round?
Now I know what easy means :-"
Порадовала фраза из условия задачи С:
"Максим — босс Майка" :)
Div1 — D
Though I still found it very amazing that Swistakk was able to submit D 2 mins after he submitted C. Did you use same approach as my URL or some even more magical approach? :D
I added extra points so all the rows and columns have an even number, then did an Euler tour. It's more-or-less equivalent to your approach.
NOOOOOOOOO!!!! I didn't change MAXN when copying ;___;. I would have been 5th and my life would be complete, because finally I would be in Petr's blog ;_;.
Of course time of 2 mins can be only reached by copying and I copied code from here: http://ki.staszic.waw.pl/task.php?name=ogrod This task is present on that site, because it was inspired by exactly that IMO problem. By the way, it can be clearly seen that my coding style significantly changed since time when I coded it (in February 2011 :P).
UPD: It's very funny, I changed this and I got WA on 38th test. I assumed (4 years ago :P) that resulting graph will be connected. It seems that copying such old codes is risky decision :P.
You already were on Petr's blog, right?
But not on pictures with standings :P.
In the middle of the contest, I saw that your solution will fail because of
MAXNand I made a decision to put maxtest in the pretest in all problems in the future. I feel really stupid, this task is a kind of task that it's ridicules if maxtest is not in the pretests. Sorry !Ah, yes, you're lucky that you said that before I have thought about complaining about that :D. But my solution will fail either way :P.
Thing which makes me wonder is why Zlobober didn't take care of presence of maxtests in tests? He should be well aware of need of them.
Why? That was good contest, not as too easy as last two:)
What did happen here?
nothing special!
*What happened here ?
How to do DIV2C/DIV1A?
Much hard, so math... couldn't solve anything :( Who found it easy?
Last minute connection problems ==> So frustrating!
How can solutions of complexity O(q*n*m) work for the given constraints in div. 2 B . I tried to hack 4 solutions of this complexity and all were unsuccessful :/
same here
Same doubt. I tried once and it was unsuccessful, so I did not try again. But I am baffled.
I thought that maybe the programming language used was the issue.. so i tried to hack solutions of slower languages ..
And all of them failed the system tests ..
Why is there a restriction on size of input file to hack solution's. I could not hack a solution for TLE, it say's max size of input file should be 256 kb.
same issue . ultimately the user got tled :/
Use Test Case generator in such cases. Write your code whose output will be the input which you want to give.
This would have done it?
yes. Or better still use this:
for(int i=0;i<500;i++){for(int j=0;j<499;j++){printf("0 ");}printf("0\n");}`` So that you don't give any extra whitepsace in the input.
E is really well known problem.
Apparently D too(not too well known though): http://www.cs.cornell.edu/~asdas/imo/imo/isoln/isoln866.html
It is Eulerian path, it should be well known.
D also is well known
It is, but I haven't seen problems with this idea for a while, so I would say D is OK.
yea, 15 ACs.
Couldn't submit solution because of lags in the end.
It was the same here
Successful hacking attempt at 2015-05-26 21:34:55 (hack ID 155718)! 5 seconds before contest ends!
Thanks Mike for delaying the contest... got 100 more than I deserved!!
... but 100 is all I get! T_T
The system crashed in the last minute here, Does anybody got the same problem?
Problem B Div 2 : O(N * M * Q) solution can pass ?
O(Q * M) will pass
Could you please tell how many instructions can be executed in judge PC within 1 sec?
No
There solution O(NM+ Q(N+M)) if I'm right
so i hacked this solution using this caes and failed, why ?
PrinceOfPersia can u review this case please !!
First time that I submit a problem for 26 times! ᕕ( ᐛ )ᕗ
[Definitely will fail in system tests ⊙﹏⊙]
It was userful today :-)
What was solution for C? I knew this and still couldn't solve it.
Just taking sum of mu[i] * num[i] when a number is added/removed. I spent the majority of time searching for mobius function in your answers on Quora because I had forgotten the name of the function :P
No, it wasn't. In this comment we are dealing with average value of that number, not worst case one.
I bet at least 100 A's will fail (including mine).
Lol, out of 530 only 156 survived the systests :)
I had a really hard time getting the coordinates for problem B of division 2 right. Probably becuase I initially solved looking for the maximum consecutive bears in both rows and columns. After this my brain melted because I started confusing x and y coordinates.
Your contests are always full of hacks! I think dynamic scoring would be better for them!
Thanks! :)
Today's Special .. Div1 Registered 1600 Div2 Registered 4800 Div2/Div1=3 and Div2%div1=0
I fed up with my Div1-C. Guys can some one point out mistake I made in my submission?
UPD. Stupid mistake. Just need to change from
to
and everything is fine. :(
5 sec , just 5 more second , I could have submitted D :( :( . I clicked the submit button and the contest was over. Hoping like hell that my soln be wrong else :'( :'(
it was WA anyway ! why sad ?!
Less AC's for A than for C. Dynamic scoring would have been good today.
difficulty: B<C<A<D<E
I don't agree.C was harder and if it had been full-feedback, you would see it.It had smaller number of AC codes just because of the particular cases.
nice problems,quick editorial,quick system testing,i can say that his rounds are the bests!!
Congratulations to dreamoon_love_AA for winning his first Codeforces round!
Div1 A was a very nice problem
About 950 submitted but only 156 got AC (in Div 1)
This was a nice contest. I was only able to solve DIV2 A and B though.
dreamoon_love_AA did it xD
What's the matter with div1 A ???
16 1 8 2 0 0 8 0 8
hack test. answer = 3
Two months have gone, and I still don't know how to find an Eulerian circuit. (I failed on problem C in round 296 and problem D in this round) :(
It is too simple :)
http://codeforces.com/contest/429/problem/E
Try this problem :P. It's very similr to today's one, though I have never understood how it should be done ;_;.
Yes, I can alway come up with solutions to this kind of problems, but can't accept them in the contest.
In srm 617, I spent too much time on the hard problem, and had no time to code the medium problem. (PieOrDolphin, which is quite similar to this problem. I used an approach with higher time complexity, and can't copy its code.)
In round 296, I copied the code from Internet, while the time complexity is O(nm), and I did't know. I failed the system test.
In this round, I copied the code from accepted solution in round 296. But I made a mistake in dealing with odd cycles.
I think I should practice more and add a correct and efficient code into my code template. :)
"Odd cycles" in this problem :D?
I understand that your problem is getting them properly coded and accepted, but either way, I think that best way to improve is to practice on similar problems :P.
I knew my C for div2 would fail after submitting. But I didn't have a better idea.
It is actually fun to see yourself in top 100 (80th precisely) even during contest. :P
What's up with DIV2 C ? Only 12 Correct submission.
Actually 10 during contest time.
I prepared an easy contest to cheer you up!dreamoon_love_AA's Dream come true Today :P
I see to Div.2 results and think that dynamic scoring would be more interesting here. People who solved C would have more points.
jqdai0815 get the 3rd place. Is there any wrong with winner announcement?
Today I was wrong on reading and trying to solve problem C before problem B because I got the idea but failed to prove it.
Looks like solving A and B in minimal time would have got me in top 100 instead of ~900.
BTW really nice round, problem C and D was really good. But I think in problem B , Solution having execution time O(n*m*Q) should not passed because it would have been similar to A then.
I tried to hack a submission like this, but unsuccessful :|
What is the hack test?
I felt very stupid when more than a hundred people solved Div1 D and I couldn't, but then came system tests...
I felt the same with Div 2 C. More than 600+ submissions, but then came the system tests...
I think A should be at least 1750 points beacuse there is fewer people to solve A than C. (Div 1)
If the pretest of div1A can be stronger, I think more people can solve it...
I thought pretest 6 is very strong... I thought I can get Accepted if I passed pretest 6 However when I hack others with test (test 74) I found I get Wrong Answer too. How sad. And I Wrong Answer on Test 71 in final test. Not Failed in my Hack Test :(
Второй раунд этого автора. div2 до топ100 решает время решения А и Б. Ибо С у всех падает.
Wasted lots of time on A, and don't have time to write solution for E. What a sad story!
It is a good way for me to give up div1A and try to solve B,C first...
I can't agree more. T_T
I hate my coding skills. :( . Please downvote me and then find me and kill me. I don't want to go through this again :'( .
problem D: http://www.spoj.com/problems/HCHAINS/.
although I somehow got TLE today..
Your Euler circuit is O(nm), for example
triangles with common vertex 1. On such test you run O(m) cycle O(n) times. It is really common bug.
To get O(n + m) you need to keep pointer to first edge that was not checked yet in current vertex.
Cool, tnx. I just copy pasted model solution from spoj problem. That also means we had bad test data there.
I think your first round was easier :)
I see rumman_sust in 4th place at div2. But he is not listed as winner.
thank you for so easy div 1 contest (mostly for problem A)
Now dreamoon_love_AA says: Sorry qwerty787788 :D
Did qwerty787788 admit that he is sorry_dreamoon
I don't think so, but the evidence is clear -> Who sorry_dreamoon really is
Dreamoon says sorry_sorry_dreamoon
Now this is shocking. I tried to hack Div2 B but could not even though solutions had O(N*M*Q) complexity. But then they failed system tests. Someone please explain this
please don't prepare any more ("easy") contests
It is unusually contest!
11305842 Accepted. This is Impossible!
Well, this round wasn't that hard. Yeah, Div1-A was a problem that I will hate a long time after this round because I somehow got WA after a couple of non-passing-pretests submission because of 2-3 forgotten lines (that I knew they should be there).
However, problem B in Div1 was easy, I regret reading it only after 45 minutes just because I wasn't sure that I will solve it and I would have lost my time and actually I lost my time but on problem A :(
DIV2 B, how this solution passed the system test with (Q*N*M)?? Please someone explain 11295339
Yes
I made a test case for DIV2B of n=500 m=500 q=5000 to hack this guy (You can see his DIV2B got tle'd) but i got maximum input limit exceeded . How could this be avoided
When hacking, you can submit input generator code instead of input file to avoid such problems
I think you can upload the case generator instead of copy and paste.
Cool Problem Div1.A/Div2.C! A lot of failed attempts :-) Get TL :-(
I am getting TLE on div1E.Is there any better complexity? Mine si (Q + N) log(number_of_letters)
кер
How long does it take usually for ratings to be updated?
in two hours after systests or faster
thanks.
it looks PrinceOfPersia changes ratings by his own.His contests' rating changes take toOoOo long
Why??? Why my raiting become 1700??? So close to Div.2 (
Never thought that DIV2 B can pass O(q*m) solution.How many instructions codeforce judging system allow to execute in 1 sec?
q*m is not much at all — just 2.5 * 10^6 iterations. Even my python solution passed it (mine is actually O(q*(m + n)), which is twice more). Keep in mind that python is like 30 times slower that c++/C#/java.
q*m*n would be more questionable — its 1.25 * 10^9 iterations.
First I tried a O(N*M + QlogN) using two different Segment Trees, but it got wa4, I changed it for O (N*M + Q* (M + logN)) which ACCEPTED. After the contest I fixed the bug on my first attempt and sent it, got AC, but with a slower time than the one AC in contest. Limits should be greater, so no slow solution could pass
how to solve Div 2 Problem D? Is it possible to solve it in O(n) or O(nlogn) is the optimal solution?
Optimal solution is O(n).
can you please tell me how to approach the solution in both these complexities
Don't you have a union find that makes it technically O(nloglogn) or O(n\alpha(n)) ?
My solution for Div2 problem D failed at testcase 51 , can someone tell me what is this testcase?
You can see it Here : http://codeforces.com/submissions/ravi416
because of large input line, i am unable to see complete testcase. Can you help?
utsav_deep answered your question!
the test cases are trimmed.
the input format is: n=100000; each array element is either 1 or 2
expected output is: array of 100000 elements in which all elements are 1, except first element which is 2.
your output: array of 100000 elements in which 1st 16 elements are 2, rest of the elements are 1
Thanks a lot guys !!! got my stupid mistake.
Div1 D was very nice! I like this problem very much:) Thank you!
All's fine, but where are the ratings for Div2?
Can anyone tell me How this soln got accepted:--
http://codeforces.com/contest/548/submission/11297296
Its O (n*m*q) i.e. 10^9 .....How this runs in 2 sec...
I tried to hack this sol using full constraints but this gives me unsuccessful hacking attempt....
Same experience as yours. I have unsuccessful hack on 11285479, but someone else have successful hack on that using full constraints :(
I hope that division 2 ratings will be published in this century ;-)
No rating update for Div2?
Eeeerrmmmmm.... no)
PrinceOfPersia are you sleeping? :D Please update the rating so that i can sleep -_-
HAHAHA, update was done, but your difference equals exactly 0 :DD
Congratulations to the real winners!
Real Div.2 winners:
norge
rumman_sust
I_Love_Hanh_Trinh
SmallBoy
raihatneloy
What was the problem in the official one??
fake accounts
I think it's very unlikely that someone capable of winning Div2 would compete there with a fake account while there is also a Div1 contest.
I guess Div 2. was unrated :|-_-|:
1700:D
Now I can go to bed)
Please for the love of the gods !!! Rate us now !!!
i hope we see you really soon
Div 2 forever. :')
Sorry, the rating update delay was the result of our with MikeMirzayanov investigation. It is now updated.
what investigation?
Stay tuned and you'll see :-)
I hacked div2 B, making use of the fact that O(n*m*q) will fail, any reason for unsuccessful hacking attempt?
Complexity was O(q*(n+m)) in most solutions.
Was it shown already? Or when will it be shown?
IN problem B my submission shows wrong answer in test 4 which is Test: #4, time: 15 ms., memory: 0 KB, exit code: 0, checker exit code: 1, verdict: WRONG_ANSWER Input 5 5 30 0 1 1 1 0 1 1 0 1 1 0 1 1 1 1 0 0 1 1 0 0 0 0 0 0 3 2 2 2 2 2 4 3 1 4 3 2 4 1 2 4 1 4 2 1 5 2 4 1 4 1 5 1 2 4 2 4 4 4 1 2 3 1 4 5 1 2 2 3 1 1 5 1 3 4 1 1 5 4 1 5 5 4 2 2 Output 4 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 4 4 4 4 4 4 Answer 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 4 3 3 4 4 4 Checker Log wrong answer 1st numbers differ — expected: '3', found: '4'
Here you can see that after the 1st query the maximum no. of 1 is 4 in 2nd row ,hence the answer should be 4 not 3....please clarify
original matrix in this test case is
01110 11011 01111 00110 00000
after first query (3,2), it will become
01110 11011 00111 00110 00000
hence, 3rd row has highest number of consecutive 1's, that is 3. so answer for first query is 3 and not 4.
if that contest is easy, how will be the hardest one?
Actually, today I was thinking about preparing a really hard contest >:)
I think people forget that you are preparing these contests voluntarily and start demanding and complain rudely instead of asking nicely and being grateful that you are taking your own time to prepare them.
I really enjoyed the editorial, I learned a lot from it.
When can you post editorials? Thanks in advance.
Here the Editorial http://codeforces.com/blog/entry/18126
thanks a lot :)
Is it normal to receive more than 200 points of rating if you've solved 0 problems? Results of sheisactually14 seems strange... Can someone explain how this can be?
Something seems off, when I put my mouse on top of the vertex representing the user's participation in the contest it say rank:177. However when we click the vertex it says rank is 631.
Btw, lots of people are making fun of statement that this contest was supposed to be easy. Looking at number of accepted A's — that is in fact funny. But looking at the scoreboard from around ~1:30 we can say that it in fact was true. There were people (note plural) which got all 5 tasks accepted on pretests before 1:15. I got 4 of them in 0:41, cubelover was even faster (0:39) even though he didn't copy D as me. That is a very rare case. C, D and E were all easy or well known to more experienced coders (though I'm a sucker when it comes to strings, so E was neither easy nor well known to me). Of course getting tasks on pretests is not equivalent to getting them, but very often means getting right solution with minor bugs, if any — so it is also a good base to judge whether tasks are easy/hard.
PrinceOfPersia, I think that your problems are nice, but this problemset was not properly balanced. Problem A was for the second time very hard for A (even swapping A and B wouldn't change that), but D and E should be more demanding. And talking about hardest problems I will advise to make them more complicated from coming up with solution point of view, because both of your E's were pretty standard for people well acknowledged with needed data structures, main difficulty was put on implementing them, I think. (Note that it is my opinion, I do not claim it to be only objective one :P).