perfect_wall_flower's blog

By perfect_wall_flower, history, 6 weeks ago, In English,

Hello Everyone!

I invite you all to November Easy '19 an exciting contest for beginners which focuses on 5 algorithmic programming questions that you have 3 hours to solve. Partial scoring will be used (you get points for passing each test case). The contest will start on November 2, 04:00 UTC.

The problems are prepared by tanmay2904 Tanmay Agrawal, Dishant_18 Dishant Trivedi, saurabh303 Saurabh Kumar Singh, memento Mamnoon Siam and me perfect_wall_flower Adarsh Agrawal. Thanks to arpa AmirReza PoorAkhavan for testing the problems and coordination of the contest.

Here are the prizes for the top three contestants:

  • $75 Amazon gift card
  • $50 Amazon gift card
  • $25 Amazon gift card

HackerEarth T-shirts for top 10 participants with ratings less than 1600

Good Luck!!!

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

»
6 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

Why hackerearth change their time of holding a contest. they changed time directly by 12 hours.

For India it used to happen at 9:30 P.M and now it is 9:30 A.M which is very unusual time for Indian Coder

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

    Exactly, 9:30 is too early for Indian participants. Generally 9:00 to 16:00 is college timings in Engg. Colleges.

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

      Yeah and we indians got used to give contest in night even codechef hold their every short contest at night

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I actually prefer the new timings because it is easier for me to participate in the morning than in the night, when I am quite sleepy or wanting to watch a movie. It also gives me a motivation to wake up early in weekends. I hope HackerEarth continues this new timing.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve the last problem?

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Weak test cases in last problem just by printing 0 gives 50 points

  • »
    »
    5 weeks ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    Hi, there are several things working against creating a strong test data.

    First of all, hackerearth has a weird scoring system — you get partial credit for each test file passed.

    Then, you cannot add all kinds of corner cases in a single test file where size of the graph is very big (maximum n according to the constraints). Which test files have large n, they have very small amount of testcases (~3). As you can guess, this can be very bad for yes/no problems. For example, if you even print outputs with rand()%2, there is a high chance that you will get ~30% of the full score (maybe even more). I've set half of the testfiles with small n (=> many testcases) and they are pretty strong.

    But if a test file has small n, then bruteforce solutions will easily work.

    So, there are some testcases with moderate n, which have several number of testcases and also n is quite big for bruteforce solutions to overcome them.

    At last, it is very very unlikely that you will get 100 without a correct solution.

    But, I am very sorry that only no tcs appeared 50% of the times.

    I am really sorry for this :(

    Moral: Dont underestimate the power of 0.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Weak test cases in last problem
      Hackerearth is known for this.

      Spoiler
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      trying to mitigate the mistake :3

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Numbers in a range problem?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you provide an editorial or at least share the general idea of each problem's solution? perfect_wall_flower

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it
    • $$$A$$$ Determining Numbers : We can simply brute force and find the frequency of each number but the editorial had a very beautiful solution.

    Given $$$N$$$ integers in which every integer occurs twice except $$$1$$$, which is the integer that occurs only once ?

    We can get this answer by taking the XOR of all the integer. The integers that occur twice cancel each other out, leaving only the unique integer.

    Now, when we have $$$2$$$ unique integers $$$u$$$ and $$$v$$$, the XOR of the integers is $$$u \oplus v$$$. Let us take any bit set in $$$u \oplus v$$$. This means that one of $$$u, v$$$ has this bit set and the other does not.

    So, we will make two arrays — $$$A$$$ and $$$B$$$, where $$$A$$$ consists of integers which have that bit set and $$$B$$$ consists of integers which do not have that bit set and it reduces to the first problem that we discussed.

    • $$$B$$$ Exchanging Money : It is based on Bezout's Identity and the solution is to find the GCD of the entire array and check if it is $$$1$$$
    • $$$C$$$ Zero Operations : We can't change the values of the nodes to negative integers so we will just set values of nodes to $$$0$$$. If a vertex is a leaf, then it will never lie on the path between two vertices. Since, we know that it is a connected tree, the leaves are all the vertices with degree $$$= 1$$$
    • $$$D$$$ Numbers in Range : We can convert it to a Stars and Bars question after making $$$1$$$ nice observation. The only thing to be careful about is that the sequence should be strictly increasing. This means that we will make $$$A_i = \max(1, A[i])$$$. If $$$A_i = 0$$$, then we should set it to $$$1$$$ since that is the minimum allowed difference.

    • $$$E$$$ One and Only Flow : We need to think in terms of the DFS tree.

    1. All the vertices should be visitable
    2. There should be no cross or forward edge
    3. Whenever there is a path from $$$u$$$ to $$$v$$$, there should be exactly $$$1$$$ path that facilitates flow from $$$v$$$ to $$$u$$$ as well. While we are doing DFS, we will check if we get a back-edge. Let $$$f(v)$$$ represent the number of paths via which flow can start from some descendant of $$$v$$$ (possibly itself) and reach some ancestor of $$$v$$$. Whenever we get a back edge from $$$x$$$ to $$$y$$$, we will add $$$+1$$$ to $$$f(x)$$$ and $$$-1$$$ to $$$f(y)$$$. Then, we will sum over the values as we are doing DFS. This is similar to the problem where we are given $$$N$$$ entry times and $$$N$$$ exit times and must count the number of people at time $$$t$$$.

    Here are my solutions for this contest.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Its been 10 days but the rating is not updated yet why?