zemen's blog

By zemen, history, 8 years ago, In English

Week of code https://www.hackerrank.com/w19 is starting soon 15 February 16:00 UTC.

Monday to Friday Every day 1 challenge will go live.(Easy to Hard)
Score decreases by 10% at the end of every 24 hours.
Your submissions will run on hidden test cases at the end of every 24 hours.
time of each challenge will be counted since open, it allows you to start late.

Contest is rated and top 10 get T shirts.

GL & HF

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

| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any help with the last one? I observed that 2 permutations are possible for even, but I couldn't get the other part of the editorial.

»
8 years ago, # |
Rev. 3   Vote: I like it +25 Vote: I do not like it

Nice problemset!

This was one of the best contest which I do in last 4-5 months! My opinions about tasks and maybe some advices for greater contest in future :

The first task was nice and easy, good for that place. Maybe graph should have been constructed on some other way ( without intersections between diagonals ), but that isn't big deal :)

The second task is good dp problem, I like it very much. It is amazing to see that someone solved it in 10 minutes.

The third problem, also was interesting, generally that is fine task. But I think it is easy to find that we talk about Fibonnaci numbers and coefficient C isn't very important. After that it is obvious to see the sum F[i-1]*F[j-1] + F[i]*F[j] must be some number with certain rule. I think many guys could guess answer with trying brute force solution for smaller constrains or even find on the internet given sum.

For the fourth task I will say right task on the right place :)

Edit: Now I saw editorial for this task and I think I solved it on other and possible easier way. First I used monotonic queue to find range where i-th element is the minimum. After that I used some kind of mapping and summation sum[X] — in how many intervals element with maps bigger or equal to X is the minimum. At the end with using simply math I could find needed answer for each element in the array.

The fifth problem is very good for me, despite I couldn't find any better solution than modified recoursion. I put one line before recoursion and got 20 more points. I put line :

if (k>1e6) printf("%d",-1);

That is a lot of points for such a little and unimportant optimisation, possible I could earn more points if I put on the right side number 50-100.

The difficulty of contest was nice for all HR users, except the second task (it is much harder, for me that is enough even for the third), also my advice that you should put smaller subtasks in the statements. That is usual thing in all other long contests. Setter or manager won't spend a lot of time for it, but it is useful and shows seriousness in work.

Thanks again for nice round.

»
8 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

Sorry for several posts, but Codeforces had some bug and I clicked around 10 times to post my comment :)

»
8 years ago, # |
Rev. 16   Vote: I like it +10 Vote: I do not like it

(CF has server and LaTeX problems...)

I solved the last problem by writing a bruteforce and observing a pattern: for even permutations, there are only two permutations; for odd ones:

  • if we count permutations starting with x for x=1..N, we get 2,3,7..,power of 2,the same sequence repeated backwards..7,3,2

  • the number of permutations is the sum of them, something like N*2^N; any permutation in the second half can be computed by replacing K by the number of possible permutations+1 — K, computing that permutation and replacing each of its elements by N+1- it (it seems some of the following rules have inverted greater/smaller there?)

  • if we count permutations among those 2,3,7.. starting with the same triplet, we get 2,3,7,..,power of 2

  • if we've reached the "power of 2" part, there's a different pattern — add some pairs until the last added element is N/2+1, then the only remaining element that can go after N/2+1 (the max. distance is N/2) and based on the 1-s in the binary representation of K, put pairs of "smallest unused number <= N/2, > N/2" to the beginning or to the end of the remaining part of the sequence

  • the sequence 2,3,7,..=$S$ continues with 16,36,80.. — the i-th member (0-based) is the sum of previous ones plus 2i - 1, so we can generate it easily and it's short

  • we can iterate over S and subtract its elements from K; when encountering an element  ≤ K, choose the first element or a pair of two more (how to choose the pairs: start greedily with the smallest y allowed element greater than the last added and the smallest unused element overall; as we iterate over S, the smaller element in the pair increases and if we're at the "power of 2" part, there's a collision between the elements in the pair, so we should increase the larger one)

  • if we stopped at 2 in S, we can fill the permutation with one of two patterns based on K being 1 or 2 (maybe it's the same as the pattern for "power of 2"?)

Time complexity: O(N|S|log(N)) — one set<> lets us find the greatest/smallest element something.

It's nasty; I didn't bother with checking if the set of rules can't be simpler and memorynuked my computer twice while debugging. But it got me first place.

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

    The sequence 2,3,7,16,36,80.. is (i+5)*2^(i-2), except for the first member.

»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Small observation about Coolguy and Two Subsequences: following solution runs in O(N^2) and at the sime time gets AC in 0.2 seconds :) In CF custom invocation it works 7 seconds for sorted array of size 20k, so it will probably take a few minutes on 200k array.

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

    How did you know that this solution will pass all testcases ?

    You must be very brave to code and submit first this solution :)

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

      It can be simply strategy "submit a bruteforce first, it can be used to debug later".

      Doesn't HR take the time of the first solution with a given number of points? That way, it's not necessary to know/assume how many tests it'll pass.

      • »
        »
        »
        »
        8 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        Yes, I agree that is good strategy!

        I am thinking on other way. For example I am I_love_Tanya_Romanova and I want to win this contest — every minut is important and uwi ( I am saying his name, because I saw he was one of the first persons with right solution) submited his solution in 26 minutes, so I wouldn't spend at beginning 10 minutes and lose more time. Possible I would try to code right solution, submit that and in case it is wrong I would write bf and find bug :) Normally I am not I_love_Tanya_Romanova :D

        And yes, I think everybody should make mistake in the first task and get one day of penalty at the begging of the contest. After that everything is easier and relaxed :)

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

          In a lot of cases it sounds like a good idea to start with naive implementation of correct solution and then to improve it step by step — in this case you can clearly see at which moment it stops working and debug it quickly.

          In a code above I simply forgot that one more optimization is still missing :)

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Still waiting for rating changes ......