ankeshgupta007's blog

By ankeshgupta007, 6 months ago, In English,

Hi everyone!

I would like to invite you to participate in HourStorm #10. The contest will start at 16:00 UTC,April 13, 2019

It's a 1-hour competition with 3 traditional (but nice) algorithmic tasks. You will receive points for every test case your solution passes, so you can get some points with partial solutions as well. Check the contest page for more details about contest schedule and rules.

The problems have been prepared by me and FarFromRed, helped by anil_9717 and tested by Arpa. There are prizes for top 3 contestants: $75, $50 and $25 Amazon gift cards respectively. In addition, the top 5 will win HackerEarth t-shirts.

Good Luck and High Ratings!

Upd: Round begins in less that 22 hours!

Upd2: Round has begun. All the best!

Upd3: Round has ended. It was very exciting to watch the leaderboard towards the end with 4 people securing perfect score of 300 at 58th minute :)

Winners:

  1. Gennady Korotkevich (tourist)

  2. Mateusz Radecki (Radewoosh)

  3. Michael Nematollahi (Deemo)

Congratulations to all the winners!

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

»
6 months ago, # |
  Vote: I like it +38 Vote: I do not like it

Sample tests were bad and didn't help to understand statements. Especially in P1 with the answer -1.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    We realized later and apologize for the inconvenience. We will ensure clear samples for our future contests.

»
6 months ago, # |
  Vote: I like it +5 Vote: I do not like it

It is more a "understand the language" than a programming contest. Skipped this one because I (and google translate) was not able to decypher any of the problem statements.

»
6 months ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

In 2nd one, do we use any properties of the graph. Or just m*sqrt(n) bipartite matching was intended. Obviously inside binary search

  • »
    »
    6 months ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    Since no more than 2 people like a cake, we can do a case analysis for both the people and then create the bipartite graph. If there are three or more people, several cases would arise, like any two people out of three can finish the cake alone but any one cannot do it alone.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I get till the bipartite part. I want to know what is the complexity of this bipartite matching. Is it m*sqrt(n). Or do we use that graph has extra properties of one side having atmost degree 2 and do a better analysis or maybe better algorithm.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No there is no further use of the property. I think we can come up with another algorithm but I did not do further analysis.

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          So the total intended complexity is m*sqrt(n)*log(n) and time limit was 1 sec because your solution ran in less than 1/2 sec maybe. Great job on this!

          Also was there any slow solution like n*m or something?

          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            You're right. It could have been about 3 seconds or so. Hopcroft matching runs quite fast in general so I decided to go with 1s TL. I've come across several problems involving matching with lower time limits so I thought that shouldn't be a problem.

            • »
              »
              »
              »
              »
              »
              »
              6 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              But likely those problems asked to run bipartite matching only once, not $$$O(\log n)$$$ times. Are you sure your solution works in 1s for any test?

              • »
                »
                »
                »
                »
                »
                »
                »
                6 months ago, # ^ |
                  Vote: I like it +5 Vote: I do not like it

                I guess this will help with how good the tests are.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 months ago, # ^ |
                    Vote: I like it +19 Vote: I do not like it

                  We too, were surprised. We expected greedy's to earn partial. We tried designing tests to avoid greedy. But this clearly showed that indeed our test data were weak.

                  I also understand the point you and Errichto are trying to make regarding time limit, and true we should have been more calculative.

                  Apologies for the inconvenience.