By Adarsh, history, 13 months ago,

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

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

Good Luck!!!

• +47

 » 13 months ago, # |   +21 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
•  » » 13 months ago, # ^ |   0 Exactly, 9:30 is too early for Indian participants. Generally 9:00 to 16:00 is college timings in Engg. Colleges.
•  » » » 13 months ago, # ^ |   +6 Yeah and we indians got used to give contest in night even codechef hold their every short contest at night
•  » » 13 months ago, # ^ |   0 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.
 » 13 months ago, # |   0 How to solve the last problem?
•  » » 13 months ago, # ^ | ← Rev. 2 →   +13 For now, you can see this.upd. previous link had some typos
 » 13 months ago, # |   +8 Weak test cases in last problem just by printing 0 gives 50 points
•  » » 13 months ago, # ^ | ← Rev. 4 →   0 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.
•  » » » 13 months ago, # ^ |   0 Weak test cases in last problemHackerearth is known for this. Spoiler
•  » » » 13 months ago, # ^ |   -7 trying to mitigate the mistake :3
 » 13 months ago, # |   0 How to solve Numbers in a range problem?
 » 13 months ago, # |   0 Could you provide an editorial or at least share the general idea of each problem's solution? perfect_wall_flower
•  » » 13 months ago, # ^ |   +1 Editorial for Numbers in a Range: https://drive.google.com/file/d/1eSoMOD0Pi_NyiysL1VUGwVAFIlFloXVk/view?usp=sharing
•  » » 13 months ago, # ^ | ← Rev. 2 →   +4 $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. All the vertices should be visitable There should be no cross or forward edge 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.
 » 13 months ago, # |   0 Its been 10 days but the rating is not updated yet why?