HolkinPV's blog

Codeforces Round #175 (Div. 2)
By HolkinPV, 12 years ago, translation, In English

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) BekzhanKassenov
4) ahmed_aly
5) lxgsbqylbk

  • Vote: I like it
  • +89
  • Vote: I do not like it

Comments Comments (66)
| Write comment?
»
12 years ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it 
while(standings[0]!={insert your username here})
{
	next_permutation(standings.begin(),standings.end());
}
→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    O(no_of_users !) :P.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it +34 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

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

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    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

    → Reply
»
12 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Happy new year to Iranians and have a nice time

→ Reply
»
12 years ago, # |
  Vote: I like it -14 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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)

    → Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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?

→ Reply
»
12 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

3003 registered....

→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What do you mean?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like 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 hours

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +4 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
            ← Rev. 2   Vote: I like it -6 Vote: I do not like it

            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.

            → Reply
»
12 years ago, # |
  Vote: I like it +7 Vote: I do not like it

someone explain the solution of problem E please ;)

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

good problems! thanks :)

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, A person in my room has a TLE solution because his/her quicksort is binary cut: http://mirror.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.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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!

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        Or you can just shuffle the array before sorting it.

        → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No wonder...thanks!

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        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?

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it +11 Vote: I do not like it

respect to the guy/gal who submitted this!

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

answered a D problem in ONE LINE!!

→ Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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://mirror.codeforces.com/contest/285/submission/3376354 http://mirror.codeforces.com/contest/285/submission/3376365

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it -8 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 5   Vote: I like it +6 Vote: I do not like it

      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.

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      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

      → Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

WOW! you are too fast! tnx :)

→ Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply