### HolkinPV's blog

By HolkinPV, 10 years ago, translation,

Good day, friends)

Welcome to regular Codeforces round #175 for Div.2 participants. Traditionally Div.1 participants can take part out of the competition.

The problems were again prepared by the group of authors: Pavel Kholkin (HolkinPV), Artem Rakhov (RAD), Fefer Ivan (Fefer_Ivan) and Gerald Agapov (Gerald). Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for Codeforces and Polygon systems and Mary Belova (Delinur) for translating the problems.

Score distribution is published in advance) today it is standard: 500, 1000, 1500, 2000, 2500.

We open the little secret of this competition, in all today's problems you find permutations)

We wish everyone good luck, successful hacks, high rating and good mood)

UPD1: the contest is over, hope you enjoy it)

UPD2: the tutorial is already published here)

UPD3: congratulations to winners:

• +89

 » 10 years ago, # | ← Rev. 2 →   +20 while(standings[0]!={insert your username here}) { next_permutation(standings.begin(),standings.end()); }
•  » » 10 years ago, # ^ |   +8 O(no_of_users !) :P.
•  » » 10 years ago, # ^ |   +1 swap(standings[0], standings[find(standings.begin(), standings.end(), {insert your username here}) — standings.begin()]);
 » 10 years ago, # |   +34 Today is the first day of the new solar year! Happy new year to Iranians!
•  » » 10 years ago, # ^ |   -8 If you tell your congratulations twice — you will get twice more "+")))
•  » » 10 years ago, # ^ |   -6 dadash njuri k nemishe ! Man be hame ye Iranian saale no ro tabrik migam va aarezuye saali khosh ba rating haye bala baraye hame daram ;) injuri baiad begi payam haye vatanio ina nafahman, hamegi her her beshun bekhandim :P
 » 10 years ago, # |   -6 I think, it will be a interesting round!!! So... Happy Hackings & Have Fun...
•  » » 10 years ago, # ^ |   0 Why it'll be a interesting round?
 » 10 years ago, # |   +4 Happy new year to Iranians and have a nice time
 » 10 years ago, # |   -14 nice info, i will prepare next permutation code which i found some time ago in java :P
•  » » 10 years ago, # ^ |   -7 You may take a look at the first comment here which have a next permutation code in C++ :P
 » 10 years ago, # |   0 If this round like round 171 doesn't have editorial please tell me to solve all the problems ;)
 » 10 years ago, # |   +8 I have just relised that HolkinPV always make Div.2 Contest, Why don't he try to make some Div.1 contest?
•  » » 10 years ago, # ^ |   +13 Actually I prepare two div1 rounds long time ago) and also not only by my self. Now I take part in the group of authors and we prepare div2 rounds for participants. Maybe we prepare div1 contest) wait) and enjoy our problems)
 » 10 years ago, # |   +5 Hope to be an interesting round... Good luck for solving the problems and good luck at hacking ;)
 » 10 years ago, # |   +7 Farmer john was lucky for me, and I want that this contest will be lucky for me :D
 » 10 years ago, # |   +5 Regarding next round, 176, why is it so early on Saturday? Can you move it on Sunday at normal time 7:30 pm as before please?
 » 10 years ago, # |   +7 ..::Happy New Year::.. عید بچه های گل ایرانی مبارک more about Nowrouz: http://en.wikipedia.org/wiki/Norouz
 » 10 years ago, # |   +2 3003 registered....
•  » » 10 years ago, # ^ |   +2 its 3000+ and a palindrome number
•  » » 10 years ago, # ^ |   0 palindrom
 » 10 years ago, # |   +5 Nice contest, but I don't usually like problems where user machine does matter upon the solution.
•  » » 10 years ago, # ^ |   0 What do you mean?
•  » » » 10 years ago, # ^ |   0 It's not that hard to come up with a brute-force solution on problem D which wouldn't run in time on the real competition, unless you've a nice machine so you can pre-calculate all the results in your own micro and just print it.
•  » » » » 10 years ago, # ^ | ← Rev. 2 →   0 I've tried to think about one brute force but all of them needs more than 2 hours.Edit: seems many contestants got brute force that runs in a less than 2 hours
•  » » » » » 10 years ago, # ^ |   +4 At least you have to use a not-so-naive brute force to solve it. My solution can run up to N = 14 and it takes 10s for N = 15.
•  » » » » » » 10 years ago, # ^ | ← Rev. 2 →   -6 My brute force solution took about 10min for N = 15. That's why I'm willing to buy a Core2Quad Processor, I'd have done this problem a lot faster.
 » 10 years ago, # |   +7 someone explain the solution of problem E please ;)
 » 10 years ago, # |   0 good problems! thanks :)
•  » » 10 years ago, # ^ |   +17 To be sincere, they are not good
 » 10 years ago, # |   0 How to solve D?
•  » » 10 years ago, # ^ |   +94
•  » » » 10 years ago, # ^ |   -16 Isn't contest unfair to those not having high speed computers? as-if-anyone-cares
•  » » » 10 years ago, # ^ |   0 Also: "g++ -Ofast D.cpp"
•  » » 10 years ago, # ^ |   +3
•  » » 10 years ago, # ^ | ← Rev. 7 →   0 The number of distinct permutations of b for each permutation a is same so ans=fact[n]*k where k is number of distinct permutations of b when a=1,2,3..n; and a+b is something permutation
 » 10 years ago, # |   0 Hi, A person in my room has a TLE solution because his/her quicksort is binary cut: http://codeforces.com/contest/285/submission/3369236. All time in contest I can't make the test that kill his/her bug. Can anyone show me how to make the test to kill that quicksort code? Thanks.
•  » » 10 years ago, # ^ |   +3 See what happens if pivot element is always maximal element in the subarray.
 » 10 years ago, # |   +3 A rare one , most of the passed pretests guaranteed passing the systests...
 » 10 years ago, # | ← Rev. 2 →   0 I think the number of the tests for D could be more.... 16 was to small, It's possible to get an array and save the answer for each test! EDIT: I saw the editorial! It seems that the solution is making an array!! Interesting! I haven't seen a problem like this!
 » 10 years ago, # | ← Rev. 2 →   0 Sadly... C# implementation of quick sort isn't perfect :( My solution for C problem failed.
•  » » 10 years ago, # ^ |   +6 There's a well known story how Petr once got TLE because of that :)
•  » » » 10 years ago, # ^ | ← Rev. 2 →   +3 I don't know about that story. Maybe I should choose another programming language for algorithmic contests...
•  » » » » 10 years ago, # ^ |   +4 Or you can just shuffle the array before sorting it.
•  » » » » » 10 years ago, # ^ |   0 done :) thanks
 » 10 years ago, # |   0 Hi all, a simple question here. For Problem A test case 3, input (3 2), why is (1 3 2) not an acceptable output?
•  » » 10 years ago, # ^ |   0 Since there is only one number, which satisfies p > p + 1
•  » » 10 years ago, # ^ |   0 I think we misread the problem in the same way :( At first I thought we just need pk>pk+1 It's not until 1 hour later where I understood that the coeff is referring to the number of such k where the above statement is true. Felt so stupid haha
•  » » » 10 years ago, # ^ |   0 No wonder...thanks!
•  » » » 10 years ago, # ^ |   0 I didn't get it. I thought we need to make sure that Pk is greater than P_(k+1).is that not the case?
•  » » » » 10 years ago, # ^ | ← Rev. 3 →   0 in the first test, 5 2 1 5 2 4 3 Pk = P2 = 5 (second position in the array)P_(k+1) = P3 = 2 (third position in the array)so that's why that's the correct output. But shouldn't 5 4 3 2 1 also be correct?
•  » » » » » 10 years ago, # ^ |   0 So it's not just me and "ssi7415" haha. No, we all misread the problem. What is required that the number of such k is equal to 2. NOT that there is only one such k, and that k=2.So, for 1 5 2 4 3, there are 2 such k's where pk>pk+1. That is, 5>2 and 4>3.
 » 10 years ago, # | ← Rev. 3 →   +11 respect to the guy/gal who submitted this!http://www.codeforces.com/contest/285/submission/3375139answered a D problem in ONE LINE!!
•  » » 10 years ago, # ^ |   +6 WOW!
 » 10 years ago, # |   +8 so i got TLE for #175 div2 C. But most solutions where similar & passed written in C++. so i tried to write it in C++ after the contest, it passed fast (500ms). furthermore, when i chose Java 7 it TLE at test 8, java 6 TLE at test 7. finally i changed long to Long, then it passed (1312ms)???so why long TLE, and Long doesnt?
•  » » 10 years ago, # ^ | ← Rev. 2 →   +4 in other words in java, why is Integer[]a faster than int[]a, or Long[]a is faster than long[]a? does this mean Integer a is faster than int a?in terms of performance.
•  » » » 10 years ago, # ^ | ← Rev. 2 →   -8 UDP: Sorry, I misunderstood the comment.Because Long and Integers are objects, but long and int are primitive types. So every time you add one Long to another Long, they are converted to primitive types, then they are added and then they are converted back. But if you use long directly, they are just added. So this is why long is faster then Long.
•  » » » 10 years ago, # ^ | ← Rev. 5 →   +6 Primitive types such as int and long are sorted by qsort, which in worst case may work in O(n^2) time. But Long and Integer aren't primitive types, they're objects. And objects in java are sorted by mergesort, which always works in (nlogn) time. That's all magic.
•  » » » 10 years ago, # ^ | ← Rev. 3 →   0 aircube has already answered. I'll just add a link to a discussion on stackoverflow.com. The problem is that quicksort has a runtime of O(n log(n)) on average, but the worst-case runtime is O(n^2). Mergesort has a worst-case runtime of O(n log(n)).
•  » » 10 years ago, # ^ |   +8 Because for sorting arrays of primitive types it uses quick sort, for others classes — merge sort.
•  » » 10 years ago, # ^ |   0 IMHO, in first case java converts basic type(long) into object (Long) of every element and makes sort after that. and converts backward. I think so.P.S. Sorry for my english.
•  » » 10 years ago, # ^ |   0 Also you can just randomShuffle array before sorting. (It seems that there are a special array, on which java quick sort works for O(N^2), but merge sort does not)
•  » » » 10 years ago, # ^ | ← Rev. 2 →   +3 Why so many minuses? I am right. http://codeforces.com/contest/285/submission/3377006It is your code, but with random shuffle.
•  » » 10 years ago, # ^ |   0 No idea. But mostly your code is slow because you're using Scanner to read 10^5 numbers. You can browse solutions of high-rated Java coders and use their I/O code.
•  » » » 10 years ago, # ^ |   +2 yeah using tokenizer made it about 500ms faster. but like aircube & Resurgent pointed out. it is the sorting that TLE. i just tried my merge sort instead of Arrays.sort() and it passed with about the same time as using Integer[] did. proving that Resurgent & aircube had a point there.one less thing i dont knw
 » 10 years ago, # |   +5 WOW! you are too fast! tnx :)
 » 10 years ago, # |   +3 The first time I solved 4 out of 5. The problem D was a little bit tricky for me, but finally I managed to solve it :)
 » 2 years ago, # |   0 Can anybody simulate the 1st or 2nd test case of problem B? I don't get it.