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:

1) hechuan

2) TroyI118

3) Bekzhan.Kassenov

4) ahmed_aly

5) lxgsbqylbk

O(no_of_users !) :P.

swap(standings[0], standings[find(standings.begin(), standings.end(), {insert your username here}) — standings.begin()]);

Today is the first day of the new solar year! Happy new year to Iranians!

If you tell your congratulations twice — you will get twice more "+")))

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

I think, it will be a interesting round!!! So... Happy Hackings & Have Fun...

Why it'll be a interesting round?

Happy new year to Iranians and have a nice time

nice info, i will prepare next permutation code which i found some time ago in java :P

You may take a look at the first comment here which have a next permutation code in C++ :P

If this round like round 171 doesn't have editorial please tell me to solve all the problems ;)

I have just relised that HolkinPV always make Div.2 Contest, Why don't he try to make some Div.1 contest?

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)

Hope to be an interesting round... Good luck for solving the problems and good luck at hacking ;)

Farmer john was lucky for me, and I want that this contest will be lucky for me :D

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?

..::Happy New Year::.. عید بچه های گل ایرانی مبارک more about Nowrouz: http://en.wikipedia.org/wiki/Norouz

3003 registered....

its 3000+ and a palindrome number

palindrom

Nice contest, but I don't usually like problems where user machine does matter upon the solution.

What do you mean?

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.

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 hoursAt 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.

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.

someone explain the solution of problem E please ;)

good problems! thanks :)

To be sincere, they are not good

How to solve D?

Isn't contest unfair to those not having high speed computers? as-if-anyone-cares

Also: "g++ -Ofast D.cpp"

http://oeis.org/A006717

The number of distinct

permutationsof b for eachpermutationa is same so ans=fact[n]*kpermutationsof b when a=1,2,3..n; and a+b is somethingpermutationHi, 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.

See what happens if pivot element is always maximal element in the subarray.

A rare one , most of the passed pretests guaranteed passing the systests...

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!

Sadly... C# implementation of quick sort isn't perfect :( My solution for C problem failed.

There's a well known story how Petr once got TLE because of that :)

I don't know about that story. Maybe I should choose another programming language for algorithmic contests...

Or you can just shuffle the array before sorting it.

done :) thanks

Hi all, a simple question here. For Problem A test case 3, input (3 2), why is (1 3 2) not an acceptable output?

Since there is only one number, which satisfies p > p + 1

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

No wonder...thanks!

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?

in the first test, 5 2

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?

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.

respect to the guy/gal who submitted this!

http://www.codeforces.com/contest/285/submission/3375139

answered a D problem in ONE LINE!!

WOW!

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 doesn`t?

http://codeforces.com/contest/285/submission/3376354 http://codeforces.com/contest/285/submission/3376365

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.

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.

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.

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)).

Because for sorting arrays of primitive types it uses quick sort, for others classes — merge sort.

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.

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)

Why so many minuses? I am right. http://codeforces.com/contest/285/submission/3377006

It is your code, but with random shuffle.

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.

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 don`t knw

WOW! you are too fast! tnx :)

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 :)