Adarsh's blog

By Adarsh, history, 5 years 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 Adarsh 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

| Write comment?
»
5 years 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

  • »
    »
    5 years 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.

    • »
      »
      »
      5 years 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 years 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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve the last problem?

»
5 years 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 years 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 years 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 years ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      trying to mitigate the mistake :3

»
5 years 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? Adarsh

  • »
    »
    5 years 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.

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

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