Good day!
We are glad to introduce you regular Codeforces round for Div.2 participants. Everyone can traditionally participate in it.
Problems are prepared by Kholkin Pavel (HolkinPV), Rakhov Artem (RAD) and Nikolay Kuznetsov (NALP). Also thanks to Michael Mirzayanov (MikeMirzayanov) for perfect system, Mary Belova (Delinur) for translating problems and Agapov Gerald (Gerald) and Alexander Kouprin (Alex_KPR) for their help.
We decide to tell you some secret about todays problems. To solve them, you wiil propably use sort algorithm)
Score distribution is standard: 500, 1000, 1500, 2000, 2500.
We wish you success and high rating!
UPD: The contest is over, the tutorial will be here soon.
UPD2: Thanks everyone for participation. We hope you enjoy your problems. Congratulations to the winners:
Special congratulation to Touma_Kazusa, who solves all problems of the round.
it's not a good idea to say how can we solve problems
but it's interesting :)
oh, really? is it interesting to know what is the algorithm? :D
It isn't the entire algorithm, we just know that we have to use sort in the final answer. But it's better to find oneself... It's a too big hint, and all the contestants who have seen this post will be advantaged.
Just curious to know why the site has not gone to safe mode today ...Its only 25 mins remaining and in some recent rounds the site went to safe mode some 1 hour back
Someone has published problems D (id DOR17) and E (id DOR16) on SPOJ during the contest. Lame way of cheating...
Someone has no respect for authors and steals your problems. This person doesn't know anything about copyrights. We try your best to do the contest. That's why we shouldn't comment this ugly behavior.
I have just received an email from SPOJ. The problems were removed and the user got banned.
I feel very stupid right know... what was the issue with pretest 3 of problem C?
4 k
1 1 1 2
Something like that
Of course... facepalm
So, what's the trick of duplicate numbers ?
If there no equal numbers it's ok and work — k/n and k%n
Let's look at
3
1 1 2
(1,1)(1,1)(1,1)(1,1)(1,2)(1,2)(2,1)(2,1)(2,2)
So k/n and k%n will print wrong answer —
k=5
Your answer = 1 1
Right answer = 1 2
P.S Sorry for my english :D
Thanks a lot. I made a fool of myself :(
Don't worry. If you look at the submissions you will see that a very large number of people made this mistake (including me). I think it's naturally to forget about the impact of duplicates initially.
the statement seems to emphasize the duplicate situation twice, but i just ignored it... 3ks for the explanation!
You're right. So many users were stuck in C. After 220th ranks in final standing, so many minus numbers are on C.
I know the trick, can you tell me the right solution?
Still right that first number is — a[k / n]. And second is a[(k–n·cnt) / num], where cnt – count of numbers in array that < than a[k / n] and num – count of numbers in array that = a[k / n].
It was written in russian editorial, i just translate it ( hope right =) )
what are the possible pairs for ur testcase?
(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)(1,1)(1,2)(1,2)(1,2)(2,1)(2,1)(2,1)(2,2)
it would be so interesting if we could see our final rank now ;)
Ahh
its my first time for entering the contest..
its very interesting :)
u will in love with it :)
my submittion of problem A is kinda stuck it says accepted on final test but
where is question mark on it says waiting or judging. http://mirror.codeforces.com/contest/160/submission/1296903 what's wrong with it?
it seems accept right now:)
yes it says accepted but in contest rating it says waiting or judging :(
just be patient , everything will be fine after the judging for whole contest:)
A,B,C explanations
Any idea about problem D?
I think it has something to do with Cycle Property and Cut Property. As I had never before implemented any flow/cut algorithm, I couldn't complete it in time. http://en.wikipedia.org/wiki/Minimum_spanning_tree#Cycle_property http://en.wikipedia.org/wiki/Minimum_spanning_tree#Cut_property
Yeah, solutions seem to be checking for exactly that, thanks.
Div 1 now, congratulations!
The article on Wikipedia only states the sufficient conditions for being included in every MST and in no MST. How do you prove they are actually the necessary conditions?
is segment tree should be used in problem E?
It is solvable by using binary-indexed tree (Fenwick Tree).
i should learn it ... thanks for the important hint! :)
Why is the system testing stuck on 100% from the last 10 mins.I want to check my C solution ..
Maybe it will be better to make such rounds not only for div2 but for mixed div1 and div2, because I think D and E were good enough for div1.
is there failed pretest or re-submission penalty from this round ? I saw the statement about this penalty during contest, but I think I did not receive penalty at my final score.
Can anyone explain why this submission (1304142) for C timed out? It works in O(n) time, I simply rad the array, count the occurencies of numbers using HashMap and then iterate at most n times. I see no way to fail it on timelimit... The only possibly slow operation is adding elements to map, but on other tests with maximum n, it worked in around 100ms. Where's the problem?
Well, I submited the exactly same sulution again and it failed on another test, which run in 130ms before. I don't get it, where's the pitfall? Something in HashMap?
They are antiquicksort tests. Shuffle the array after reading and get AC.
Well, it passed with Integer[] instead of int[]. I think this is the most stupid thing I ever saw on programming contest. I see no point in not letting pass the solution with the correct idea and implementation... Just because of testcase challenging in fact Arrays.sort method of Java authors, not my code. What will be next, tests concentrating on possible bugs in GCC compiler? I probably should start coding in Turing machine instructions in next round.
Actually, there are a lot of cool stories of unsuccessfull hacks/TC challenges with correct output from function that returns correct value despite having no return statement inside.
We should never believe a compiler and runtime library. C'est la vie
Yes, I fully understand this, in fact, I'm glad in some way that I have learned today about a pitfall in commonly used part of standard library. But there's a difference between non-defined behaviour of C/C++ and "abusing" a weak spot by carefully chosen input. In first case, a challenger/systemtester is in disadvantage and knows his attempt can fail. If he will succeed, a code with a bug will be identified and will gain zero points. He's aware about the risk, it's a lottery. In second case, it's about choosing a very special case that timeouts in fact correct solution. A coder who got a correct idea and implemented it will gain zero points. I see a clear difference between these cases. But, however, both of them are following rules and there's no one to blame. But it's questionable if the second one is fair. But yes, there's no "guilty", just a "victim". So the victim will write slightly angry comment after the contest and life moves on :)
It makes absolutely no sense that I failed C with an O(n log n) algorithm just bcoz I coded in Java. This gives no chance at all for Java coders. All I did was to sort and proceed like every other AC algorithm.
It seems you have the same problem that I have. The strange thing is my solution once passed test 66 in 130ms and then it didn't make it in one second. Maybe some problem with system tester?
may be it was AntiQuickSort test?
What does that mean ?
as I understood from previous posts Java Arrays.sort uses quicksort, which can be hacked with special generated test which causes Arrays.sort to do O(N^2) operations.
AFAIK, Java implements using dual pivot quick sort which is faster than normal quick sort.
Any quick sort impelementation with determinate algotrithm of choosing element for partition can be failed to O(N^2) time. Java implementation too.
It seems you are right. What I did now is to push all elements in a priority queue and then pop them all and it was AC. I never thought that the built in sort would time out, never met that idea in a contest.
More easy is to shuffle data before sorting. But i don't think simeting like this will hapen often on codeforecs. It's not very sporting behavior.
Is shuffle is determined too? If so, it's possible to antiQuickSortAfterShuffleTest
You can shuffle yourself using Random, with seed got from time.
oh, sure
AFAIK Java use mergesort not quicksort for sorting.
There are many AC Java solutions. There are even Ruby AC solutions for that problem
quicksort IS NOT N LOG N. it's o(n^2)
and o(n log n) on random test
I have a question concerning problem statement of 160D - Edges in MST. It says:
You are given a connected weighted undirected graph without any loops and multiple edges.
But in the first sample there is a loop:
1->2->3->1Is the statement wrong or am I missing something?With loops it meant 1->1
It's true, thanks!
can someone tell me one reason about why problem C time constrain is 1 second !!!!!!!!!! it's just totally nonsense , the wrong Algorithm will just fail the 2 sec time !!! my solution is O(n logn) and it failed in java but Acc in C++
THANKS !
When I saw the non-standard time limit I thought that they probably put it there to prevent anybody from attempting to solve that by brute force (i.e. creating all possible pairs, sorting them and then selecting the k-th one).
However I agree that Java coders had a significant disadvantage here because of the Anti-Quicksort tests (I got lucky with Ruby I suppose). I agree that coders should think about worst-case complexity which is O(n^2) for Quicksort but if so this should affect all implementations and not just the ones in a single language.
you couldn't create all the pairs. they could be 10^10 in number!
the O(n^2) solution will fail in both memory and time, which makes the 1 sec limit completely ridiculous.
Yes, but that does not mean that the problem isn't solvable in 1 second using Java. As mentioned in previous comments you need to shuffle the data before sorting to avoid the worst-case performance of Java's sorting algorithm.
true but this not the point,the problem is having same Algorithm that passes in one language and not on the other , and this isn't right in an Algorithm competition , specially if the difference very small.
I failed the problem due to anti-quicksort test too. But I think it was a lesson well learned.
i don't think that it's our mistake !
cmon, its just a contest.
well, you are right about that :)
This is the first time I do in codeforces environment. So I'm sorry if this is an already known issue, but in problem C, using C++, reading a long long integer from std::cin isn't really operated, while on my local machine with gcc 4.2.1 does. I was struggling against this for an hour and found that using scanf("%I64d", &longint) only solves this.
I just took a look at your submissions and realized the problem is that you declared k as int, not long long.
What a pity!The school network was broken at 23:30 and i could not finish the task...and my rating has decreased a lot. :-( TT
sorry for that :(
try to view problems and submit by your phone.
a really cool idea!
what pears do we have on this test?
1 1
and why ? all pears are ~~~~~ (1,1),(1,2),(2,1),(2,2) ~~~~~
try to read all comments before asking questions like this
there is n^2 pairs ;-) (sometimes I miss similar conditions, so I perfectly understand...)
is there anyone can tell me why i got WA on this submission? (http://mirror.codeforces.com/contest/160/submission/1299317) i tested on my computer and got a right answer. (15 lines of ‘at least one’)
Look carefully and don't be confused between your output and the answer. It must be 1 "any" + 14 "at least one".
OMG I was confused thanks!!