Yury_Bandarchuk's blog

Invitation to 101 Hack Feb 2016
By Yury_Bandarchuk, 9 years ago, In English

Hello CodeForces Community,

I would like to invite you to participate in 101 Hack Feb 2016 will be held on Sunday, 21 of February. The problems were set by me (Yury Bandarchuk) and tested by CherryTree (Siarhei Kulik) and wanbo. Also, I am so grateful to pashka for solving some problems on Java.

101 Hack is back with its 34th edition! Passionate programmers will enjoy solving algorithmic challenges. It's all about speed, accuracy and efficiency: 5 challenges in 120 minutes. Every second counts!

Top 10 winners on the leaderboard will receive a HackerRank T-Shirt.

Hope, you will participate and enjoy the problems.

Good luck && have fun!

UPD: Contest has ended! Congratulations to winners! Editorials for every problem are available now.

  1. riadwaw

  2. I_love_Tanya_Romanova

  3. Errichto

Want to hear your feedback about the problems!

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

»
9 years ago, # |
  Vote: I like it +35 Vote: I do not like it

It's colliding with Codechef Cook Off. If possible, can you guys change your timings in order to accommodate that?

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

Want to hear your feedback

I consider the problem statements as well-formed and easy to understand.
Thanks for the round, it was interesting to participate!

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

The problem statement of A was difficult to understand for me. The other problem statements were easy to understand.

C was a nice ad hoc problem that can be solved using many approaches.

In D, how to get the formula with complex numbers? The editorial doesn't explain this.

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

    1. Write many formulas from the Newton's binom.

    2. Use wolframalpha.com :)

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

    In D one could you matrix exponentiation, no need for complex numbers

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

Good problems, however, I failed this round. :)
For me, D was easier (actually I've just googled from OEIS) rather than C, but I was late to code because I couldn't understand its statement. I understood only after my friend explained me. :(

P.S. Hackerrank was showing something like "1 hour 3 minutes left" when actual time left was only 3 minutes...

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

    I had something like "ended X minutes from now" but contest was running. That's because of your local time settings on your computer.

    → Reply
»
9 years ago, # |
  Vote: I like it +15 Vote: I do not like it
  • Beautiful Pairs — Ok. Maybe the statement would be easier to understand with multisets instead of sequences?
  • Minimum Penalty Path — Ok. I think I know a solution with complexity O((N+M)log(MAX_COST)) but maybe I'm mistaken. Let's start with the answer 1023 (only 1's in the binary system). In linear time we can check whether A and B are connected (if not the print "-1"). For each bit from the most significant one we try to turn it off and check whether A and B are connected. If they are then we turn off this bit for ever — we can so we want to. implementation
  • Beautiful Strings — At first I thought it will be tedious to code but turned out to be nice and not complicated. My favorite problem from this contest.
  • King and Four Sons — Without any thinking I used the Wolframalpha, so I didn't like this problem at all. How can we obtain the formula with complex numbers? Can you give me some links or theorems about it?
  • Beautiful Segments — Ok but I personally don't like this kind of problems. More coding than thinking.
→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +34 Vote: I do not like it

    King and Four Sons — in case you want to avoid "ouch, I tried Wolfram Alpha and it suggested some smart magic stuff" situation: we have dynamic programming DP[i][j] — in how many ways we can pick X among first i soldiers, so that X%4=j. We are interested in finding DP[A][0]. This DP is already fast enough for "small" subtask with A<=1000. Now what about making it work faster? OK, there are only 4 states in one layer of DP table, and transitions look cool and simple (either pick current soldier and move to (j+1)%4, or don't take it and stay and j), let's use matrix exponentiation!

    You have 4x4 matrix, so it is working fast enough, and thinking about it in terms of DP+matrix exponentiation sounds like a very classic idea.

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

      Thanks, nice approach. Though I would still like to learn how to find a formula for that sum.

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

    :)

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

We didn't understand your solution for last problem, but it seems that you don't need treaps and complex segment tree, if you notice that base array of segment tree is increasing, so you may use binary search.

As for feedback: I'd say that difference in difficulty between A-D and E was too big.

And it's quite strange to give 500 lines code in editorial and expect people to understand it

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

    The same for me — I did not understand the editorial.

    But how do you suggest to use binary search? I came to a solution with fractional cascading on a segment tree for fixed X, but cannot handle updates in O(logN) time then.

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

      Well, I didn't think about detail but idea:

      for fixed X you have array: for each left border you have right border. Now when you change x you change some of this right borders

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

        That's true — the total number of updates will be not more than O(NlogN).

        But how to perform a request "given [l, r] find amount of intervals in it" in O(logN)?

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

          suppose an array explained before is t (i.e t[l] = r)

          Now you have query [L; R), you need to calculate sum(R — t[x] + 1) for all x such that x in [L, R) and t[x] <= R.
          Such x's form a segment [L, z) where z may be found using binary search. And after that you just need sum(R — t[x] + 1) = (R + 1) * cnt — sum(t[x]) where x in some segment. It may be done with fenwick/segment tree

          There was link, but it doesn't work

          → Reply