Блог пользователя dyps

[HackerRank] 101 Hack 24th Edition Sponsored by Cogito API
Автор dyps, 10 лет назад, По-английски

Hello Coders,

The 24th edition of 101 Hack is here. This time we have 5 interesting challenges lined up for you.
The contest commences on 29th April 2015 at 16:30 UTC, and will run for 2 hours. You can sign up for the contest here.

This edition of the contest is sponsored by Cogito API and prizes include

1st place: Pebble watch
2nd place: wireless headphones by Voxoa
3rd place: Hubscan quadcopter
4-20 will each get a HackerRank T-shirt

The problem statements will be available in English, Russian and Chinese.

Problem Setters

Bidhan
sevenkplus

Problem Testers

wanbo

Please try all problems, Editorials will be available at the end of contest.

GL&HF

  • Проголосовать: нравится
  • +52
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится +23 Проголосовать: не нравится

The winner should be able to pick one of those prizes. They all seem equally cool.

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

I am not sure about penalty time calculation (considering it is not displayed anywhere). Am I guaranteed a win here?

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

I would really like Hackerrank people to add more countdowns until the contest finish on all pages. This is the second time in a row I submit a full solution for the last problem few minutes (if not seconds) after the finish with no idea how much time if left.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    There is a countdown in challenges page. It is not viewable from all pages though and only shows time in minutes.

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +17 Проголосовать: не нравится

      Yes, but there's no reason for me to open the challenges page frequently, there's no useful info there. I've usually got a problem opened, and I don't want to change tabs every time I want to know how much time is left.

      → Ответить
      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        So do I. I am not satisfied with that either. Just wanted to inform that a poor version exists :)

        → Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I had lots of fun in solving, very nice problems!

Very strange, I got almost half points for the sightseeing problem just using 3-fors algorithm.

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

When I solved second problem(Twisty Tuple), I misread the constraint as N ≤ 3 * 105 instead of N <  = 5 * 103 until contest end and open codes of others. And I'm shocked that I can solve it during contest!

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Wow, I am amazed by it, can you explain the solution? :)

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится +22 Проголосовать: не нравится

      The main idea of my solution is:

      Let a be the number of tuples (i,j,k) such that Ai < Aj.

      Let b be the number of tuples (i,j,k) such that Ai ≤ Aj and Ai ≤ Ak.

      Let c be the number of tuples (i,j,k) such that Ai = Aj and Aj ≤ Ak.

      Then the answer is a - b + c.

      Thanks spiderbatman to point out my bug.

      → Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    I misread the same way. This 3 really looks like 5. Couldn't solve it, I was searching for easy solution. At the end submited slow solution in order to get any points and got accepted =).

    → Ответить
»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

I didn't understand the editorial to the third problem. Why are we sorting the problems? How is the state transition working? :/ Can someone please explain?

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Lets say that student i solves problem j for time to be minimum. Also say student i uses those D minutes to explain the N problems to set of another m students(total m*D mins).Now if student i solves problem j after teaching those problems to m students than the answer will be better than or equal to the case when student i solves problem j before teaching problems to his m students because when he teaches first,then those m students have oppurtunity to solve their respective problems or to teach it to other remaining students. Thus after a student solves a problem then he would not use those D mins to teach problems to any1 n he will be idle thereafter. Also if we are assuming that he will solve problem j then it should be the unsolved problem needing maximum time, again because of a greedy arguement that he is anyway going to be idle after solving his respective problem,so y not solve problem that requires maximum time rather than keeping it for later students . To get this maximum time unsolved problem in O(1),we sort the times.Hence while recursing in dp if say e students have solved their respective problem,then the problem solved by this(i'th) student would be n — e — 1(0 based) and time for that would be time[n-e-1](0 based)

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
      ← Rev. 12   Проголосовать: нравится 0 Проголосовать: не нравится

      How is this part of the code in the setter's code working? What is the state transition in the dp? I don't understand the recurrence relation behind it...

      for(int probC = n-1; probC >= 0; probC--) {
  for(int manC = n; manC >= 1; manC--) {
    if( manC >= n - probC ) dp[ manC ][ probC ] = a[ probC ];
    else {
      dp[ manC ][ probC ] = d + dp[ min(n, manC<<1) ][ probC ];
      if(manC > 1) {
        long long C = max( a[ probC ] , dp[ manC-1 ][ probC+1 ]);
        dp[ manC ][ probC ] = min( dp[ manC ][ probC ], C);
      }
    }
  }
}
cout << dp[ 1 ][ 0 ] << endl;
      → Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 5   Проголосовать: нравится +8 Проголосовать: не нравится

    As Sumeet.Varma has explained above, it is optimal when each person explains a certain number of times and then solves his problem. And when one quits explaining and starts solving he should solve the problem with the largest time (because he starts earliest). That made me think of the following dp solution (I think it's not exactly the same as the editorial, because I don't really get that either :) ):

    Let f(i, j) = the minimum time to complete the task when person [0..i - 1] know all the problems and person [0..j - 1] don't explain anymore. The answer then is f(1, 0).

    When i =  = n and j =  = n everybody knows all the problem and nobody is explaining anymore, which means every problem has been solved, so f(n, n) = 0.

    Otherwise, if j ≥ i we reached an impossible state. If j > i more people stoped explains than persons actually knowing the problems. And if j =  = i there's no way to tell the remaining people about the problems, so that's not possible as well. Therefor f(i, j), j ≥ i = infinity.

    Now the transition, we got two options:

    The (i - 1) - (j - 1) = i - j people that still explain can explain once again. That means now i + i - j = 2i - j people know the problems now (and obviously not more than n can know the problems). This takes d time and only makes sense when there are people left to explain the problems to.

    The second option is for person j to stop explaining, which brings us to state f(i, j + 1). But person j needs to solve a problem, the one with the largest time. As we've sorted problems by time he needs to solve problem j. So max(time[j], f(i, j + 1)) (whatever takes longer).

    I hope that clears things up. Code

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      This problem can also be solved using binary search. If it is not possible to solve all problems in time x it is not also possible to possible to solve for every time x' < x.

      To check if it is possible to solve the problem in time x one can use a greedy solution after sorting the array t in non increasing order (ti >= tj, i < j). If t0 > x than clearly the problems can't be solved, otherwise create an array time:

      For every i: time[i] + t[i] <= x. If at any point this condition can't be achieved for a certain i a solution for x does not exist.

      For every ti, 0 < i < n we just need to find k < i such that time[k] + d + t[k] <= x. This can be done in O(n) using two pointers technique.

      If such k can't be found than x will not suffice to solve all problems. Otherwise: time[k] = time[k] + d and time[i] = time[k].

      Overall complexity is O(nlogn).

      → Ответить
»
10 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

I almost always get "It looks like you're not able to connect to our sync servers. Please wait for a few secs..." error dialogue when trying to view other contestants' code. And loading heavy CodePair page with chat and stuff when I just want to see the code is such an overkill. Java 8 and C# code is accessible as plain text though, wish it was like this for all languages.

→ Ответить
»
10 лет назад, # |
← Rev. 3   Проголосовать: нравится -23 Проголосовать: не нравится

Pebble watches are great. tourist will enjoy it.

→ Ответить