HolkinPV's blog

By HolkinPV, 8 years ago, translation, ,

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.

• +80

 » 8 years ago, # |   +7 it's not a good idea to say how can we solve problems
•  » » 8 years ago, # ^ |   +4 but it's interesting :)
•  » » » 8 years ago, # ^ |   -8 oh, really? is it interesting to know what is the algorithm? :D
•  » » » » 8 years ago, # ^ |   +5 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.
•  » » » » 8 years ago, # ^ |   -6 You are always have an option, just skip reading this text if you wanna try to solve problems by yourself =)
 » 8 years ago, # |   -12 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
 » 8 years ago, # |   +36 Someone has published problems D (id DOR17) and E (id DOR16) on SPOJ during the contest. Lame way of cheating...
•  » » 8 years ago, # ^ | ← Rev. 2 →   +20 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.
•  » » 8 years ago, # ^ |   +2 I have just received an email from SPOJ. The problems were removed and the user got banned.
 » 8 years ago, # |   +1 I feel very stupid right know... what was the issue with pretest 3 of problem C?
•  » » 8 years ago, # ^ | ← Rev. 2 →   +2 4 k 1 1 1 2 Something like that
•  » » » 8 years ago, # ^ |   +1 Of course... facepalm
•  » » » 8 years ago, # ^ |   +1 So, what's the trick of duplicate numbers ?
•  » » » » 8 years ago, # ^ |   +11 If there no equal numbers it's ok and work — k/n and k%n Let's look at3 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
•  » » » » » 8 years ago, # ^ |   +1 Thanks a lot. I made a fool of myself :(
•  » » » » » » 8 years ago, # ^ | ← Rev. 2 →   +1 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.
•  » » » » » » » 8 years ago, # ^ |   0 the statement seems to emphasize the duplicate situation twice, but i just ignored it... 3ks for the explanation!
•  » » » » » » » 8 years ago, # ^ |   0 You're right. So many users were stuck in C. After 220th ranks in final standing, so many minus numbers are on C.
•  » » » » » 8 years ago, # ^ |   0 I know the trick, can you tell me the right solution?
•  » » » » » » 8 years ago, # ^ |   0 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 =) )
•  » » » » » » » 8 years ago, # ^ |   0 thanks, I understand now ~~
•  » » » 8 years ago, # ^ |   +1 what are the possible pairs for ur testcase?
•  » » » » 8 years ago, # ^ |   +2 (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)
 » 8 years ago, # |   0 it would be so interesting if we could see our final rank now ;)
 » 8 years ago, # |   0 Ahhits my first time for entering the contest..its very interesting :)
•  » » 8 years ago, # ^ |   0 u will in love with it :)
 » 8 years ago, # |   +1 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://codeforces.com/contest/160/submission/1296903 what's wrong with it?
•  » » 8 years ago, # ^ |   0 it seems accept right now:)
•  » » » 8 years ago, # ^ |   +1 yes it says accepted but in contest rating it says waiting or judging :(
•  » » » » 8 years ago, # ^ |   0 just be patient , everything will be fine after the judging for whole contest:)
•  » » » » » 8 years ago, # ^ |   0 hope so : )thank you
 » 8 years ago, # |   +5 A,B,C explanationsAny idea about problem D?
•  » » 8 years ago, # ^ |   +3 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
•  » » » 8 years ago, # ^ |   0 Yeah, solutions seem to be checking for exactly that, thanks.
•  » » » » 8 years ago, # ^ |   +3 Div 1 now, congratulations!
•  » » » 8 years ago, # ^ |   +3 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?
 » 8 years ago, # |   +1 is segment tree should be used in problem E?
•  » » 8 years ago, # ^ |   +1 It is solvable by using binary-indexed tree (Fenwick Tree).
•  » » » 8 years ago, # ^ |   0 i should learn it ... thanks for the important hint! :)
 » 8 years ago, # |   +1 Why is the system testing stuck on 100% from the last 10 mins.I want to check my C solution ..
 » 8 years ago, # |   +12 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.
 » 8 years ago, # |   0 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.
 » 8 years ago, # |   0 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?
•  » » 8 years ago, # ^ |   0 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?
•  » » » 8 years ago, # ^ |   0 They are antiquicksort tests. Shuffle the array after reading and get AC.
•  » » » » 8 years ago, # ^ |   +1 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.
•  » » » » » 8 years ago, # ^ |   0 tests concentrating on possible bugs in GCC compiler? 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
•  » » » » » » 8 years ago, # ^ |   0 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 :)
 » 8 years ago, # |   +9 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.
•  » » 8 years ago, # ^ |   0 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?
•  » » 8 years ago, # ^ |   0 may be it was AntiQuickSort test?
•  » » » 8 years ago, # ^ |   0 What does that mean ?
•  » » » » 8 years ago, # ^ |   +9 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.
•  » » » 8 years ago, # ^ |   0 AFAIK, Java implements using dual pivot quick sort which is faster than normal quick sort.
•  » » » » 8 years ago, # ^ |   0 Any quick sort impelementation with determinate algotrithm of choosing element for partition can be failed to O(N^2) time. Java implementation too.
•  » » » » » 8 years ago, # ^ |   0 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.
•  » » » » » » 8 years ago, # ^ |   +1 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.
•  » » » » » » » 8 years ago, # ^ |   0 Is shuffle is determined too? If so, it's possible to antiQuickSortAfterShuffleTest
•  » » » » » » » » 8 years ago, # ^ |   0 You can shuffle yourself using Random, with seed got from time.
•  » » » » » » » » » 8 years ago, # ^ |   0 oh, sure
•  » » » 8 years ago, # ^ |   0 I feel very sad about it. I spent one hour to figure out the following code, but couldn't until seeing AntiQuickSort.  long c = arr[0]; arr[0] = arr[(int) n - 1]; arr[(int) n - 1] = c; 
•  » » » 8 years ago, # ^ |   0 AFAIK Java use mergesort not quicksort for sorting.
•  » » 8 years ago, # ^ | ← Rev. 2 →   -6 There are many AC Java solutions. There are even Ruby AC solutions for that problem
•  » » 8 years ago, # ^ |   -6 quicksort IS NOT N LOG N. it's o(n^2)and o(n log n) on random test
 » 8 years ago, # |   0 I have a question concerning problem statement of 160D - Ребра в 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->1 Is the statement wrong or am I missing something?
•  » » 8 years ago, # ^ |   +3 With loops it meant 1->1
•  » » » 8 years ago, # ^ |   0 It's true, thanks!
 » 8 years ago, # |   0 why is my last contest rank 1034 when i get 724 place? link i think something wrong with system today
 » 8 years ago, # |   0 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 !
•  » » 8 years ago, # ^ |   +1 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.
•  » » » 8 years ago, # ^ |   +3 you couldn't create all the pairs. they could be 10^10 in number!
•  » » » 8 years ago, # ^ |   +1 the O(n^2) solution will fail in both memory and time, which makes the 1 sec limit completely ridiculous.
•  » » » » 8 years ago, # ^ |   0 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.
•  » » » » » 8 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » 8 years ago, # ^ |   0 I failed the problem due to anti-quicksort test too. But I think it was a lesson well learned.
•  » » » » » » » 8 years ago, # ^ |   0 i don't think that it's our mistake !
•  » » » » » » » » 8 years ago, # ^ |   0 cmon, its just a contest.
•  » » » » » » » » » 8 years ago, # ^ |   0 well, you are right about that :)
 » 8 years ago, # | ← Rev. 6 →   0 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.
•  » » 8 years ago, # ^ | ← Rev. 2 →   +1 I just took a look at your submissions and realized the problem is that you declared k as int, not long long.
•  » » » 8 years ago, # ^ |   0 Ah, I see. Thank you for your clarification. The problem was that k was not declared long long and reading from cin might give some internal errors at cin >> k and no more elements were read after that line.
 » 8 years ago, # |   0 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
•  » » 8 years ago, # ^ |   0 sorry for that :(
•  » » 8 years ago, # ^ |   0 try to view problems and submit by your phone.
•  » » » 8 years ago, # ^ |   0 a really cool idea!
 » 8 years ago, # | ← Rev. 2 →   0 what pears do we have on this test? 3 3  1 1 2 
•  » » 8 years ago, # ^ |   0 1 1
•  » » » 8 years ago, # ^ |   -10 and why ? all pears are ~~~~~ (1,1),(1,2),(2,1),(2,2) ~~~~~
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   +15 try to read all comments before asking questions like this
•  » » » » 8 years ago, # ^ |   0 there is n^2 pairs ;-) (sometimes I miss similar conditions, so I perfectly understand...)
 » 8 years ago, # |   0 is there anyone can tell me why i got WA on this submission? (http://codeforces.com/contest/160/submission/1299317) i tested on my computer and got a right answer. (15 lines of ‘at least one’)
•  » » 8 years ago, # ^ |   +1 Look carefully and don't be confused between your output and the answer. It must be 1 "any" + 14 "at least one".
•  » » » 8 years ago, # ^ |   0 OMG I was confused thanks!!