shef_2318's blog

India Hacks 2016: awesome prizes and original problems. Qualification round 1
By shef_2318, history, 9 years ago, In English

Hi everyone!

I'm happy to announce you about the new contest organised by HackerEarth — India Hacks 2016!

Just check out the prizes:

There will be 3 qualification rounds with 3 hours duration each. From each qualifier top 1000 participants will advance to the main contest, so the final is going to be a decent battle of 3000 coders.

The first qualification round is taking place on Sunday, January 3, 18.30 Moscow time. View your time here

The problems of the first round were kindly prepared by RomaWhite. As you might already guessed I'm the tester and editorialist. In my opinion this problem set is very nice because it requires more thinking than implementation, but on the other hand most of the problems are not very hard, so it will be a good warm-up for your brain after New Year celebration :)

In order to participate register here.

Important note: this contest has a partial scoring system and all the problems have subtasks. It means that if you don't know how to solve some problem you should try your best to get some partial solution.

Bye-bye and I hope to see you all participating and having fun :)

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

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

The contest starts in less than 2.5 hours. Good luck everyone!

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

    Will there be editorials ?

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

      You are red with black letter, why do you need one? ;)

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

      Editorials were added before the contest, but there are some issues with adding problems to practice again and editorials are unavailable :/ I hope admins will deal with it soon.

      Anyway feel free to ask questions and discuss problems here.

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

First four problems:

1) String Division
If the length of the string is less than 10, bruteforce over all possible ways of splitting the string.

Otherwise the answer is "YES" (split the string into four parts of lengths 1, 2, 3, length - 6)

2) Hungry Lemurs:

Try all possible final values of k, for each one i find it's closest multiple to n, call it v and the answer for this value would be abs(k - i) + abs(n - v).

3) Strange Function:

First sort the array in ascending order and subtract c from all elements of the array. calculate the current answer for this array, call it cur
Now, go through the numbers in descending order, Add 2 * c to the current element, update cur.
The answer will be the maximum value of cur
Updating cur:
Adding 2 * c to an element will decrease the difference between it and each element larger than it by 2 * c (therefore cur will decrease by 2 * c * (n - i) ) and increase the difference between it and each element smaller than it by 2 * c (therefore cur will increase by 2 * c * (i - 1) )
So cur = cur - 2 * c * (n - i) + 2 * c * (i - 1)

4) Permutation Swaps:
Consider pairs that can be swapped as edges, and positions as vertices. A number i can move to it's position in Q if there is a path between it's beginning position and it's final position.
I used DSU to solve this problem , after adding all edges, if there is a number whose position in the first permutation is in a different component than it's position in the second one, then the answer is "NO", and "YES" otherwise.

I would appreciate if someone could explain his solution to the fifth problem

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

    Any proof for the third problem ? How did you come up with that ?

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

      First, subtracting c from all elements then adding 2 * c to some of them is equivalent to subtracting c from some elements, and adding c to others.
      The only assumption in my solution is that after sorting the array and subtracting c from all elements, the elements to which we will add 2 * c form a suffix.
      Proof:
      If we add 2 * c to the ith element and not to the jth element i < j this will affect the answer by:
      2 * c * (i - 1) - 2 * c * (n - i)
      However, If we add to the jth element instead of the ith , this will affect the answer by:
      2 * c * (j - 1) - 2 * c * (n - j)
      and since j > i, then 2 * c * (j - 1) - 2 * c * (n - j) > 2 * c * (i - 1) - 2 * c * (n - i) ,therefore it's better to add to the jth element, so the elements will form a suffix

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

      Another way of looking at it: we need pairwise absolute difference for all pairs.So even if we sort the numbers we don't cause any change(since still the absolute pairwise diff would be the same.) So after we have sorted the data we want (assume 1 based indexing)..(let's see for first element )|a1-a2|+|a1-a3|...|a1-an| as data is sorted this is equal to (a2-a1)+(a3-a1)+...(an-a1).So we notice a1 is subtracted n-1 times . following similar process for a2 we'll get that a2 gets subtracted (n-2)times and added once(1st term of a1 series). so eventually we get a[i] is added (2*i-n+1) times. Now we can accordingly increase or decrease a[i] by c to suit our purpose of maximizing individual positive contribution or minimizing individual negative contribution of a[i],based on signs of a[i] and (2*i-n+1).

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

Can someone tell me how my naive solution got 100 points for the first problem ?
https://ideone.com/6eDaoc

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

    If n>=10 there is always a solution where i = 1, j = 3, k = 6 , so your solution will find the answer quickly

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

      Oh right !

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

      How did you come up with this ? I mean that we need to bruteforce when n<10 ?

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

        because n<10 :D

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

          I'm not getting where is that '10' coming from ?

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

            you can guarantee that 4 strings are pairwise different if they have different lengths right? so you need at least 10 letters to have 4 distinct lengths (1+2+3+4)

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

              I am so stupid!

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

                You're and legendary grandmaster (nutella).

                So you already know all these things. and you're just kidding. ;)

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

                  he is magically legendary grandmaster.

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

                  I know,
                  I'm also kidding.

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

By the way, the editorials are live now. And the problems are open for upsolving, too. Do not underestimate the power of upsolving a contest. (That is, if you failed to solve something!)

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

Are all the rounds online or is there any onsite round as well?

There is something called "PHASE II (OFFLINE)" in the contest website. Does this mean there will be an onsite for Algorithms track as well?

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

When can we expect prizes to be delivered to us? It has been more than 6 months but haven't received prizes yet.

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

    They just keep on postponing the expected date. They always reply that it's in progress and will be delivered to you within next 3 days.

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

    UPD: Today I got a confirmation mail from HackerEarth that my prize has been shipped.

    → Reply