nikesh04's blog

Invitation to HackerEarth's June Easy '20
By nikesh04, history, 4 years ago, In English

Hello Everyone!

I would like to invite you to participate in HackerEarth's June Easy '20. It will be held on Saturday, June 06 at 12:00 — CDT.

I (nikesh04), vivaan_gupta, Finding_Infinity, spar5h, and Kritagya Agarwal are the setters of this round, and Arpa is the tester of the problems.

You will be given 6 algorithmic questions to solve in 3 hours. Partial scoring will be used (you get points for passing each test case). Although the contest is targeted towards beginners, we hope that everyone finds the tasks interesting. The contest is rated for all and the prizes will be awarded to the top 3 beginners (i.e. programmers with a rating of 1600 or less before the challenge starts):

First place: $75 Amazon gift card.

Second place: $50 Amazon gift card.

Third place: $25 Amazon gift card.

Good luck to everyone, and I hope you like the contest!

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

Comments Comments (19)
| Write comment?
»
4 years ago, # |
  Vote: I like it +15 Vote: I do not like it

contest is not loading 502 gateway error:(

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

Hint for last problem ?probably greedy with taking mid does not work

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

Please share approach for "Arrays and Sum" , I solved 4 questions and this one partial .

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

    I do not know how but subset-sum did the work for me. According to the constraints I should have got partial points.

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

      Can u please share your code ... and it will be more helpful if anyone share most optimized approach for this question

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

          My in contest soln was similar just that it used bitsets for a /32 constant factor.
          I assumed it to be O(N*1000/32). After reading your comments I realized it was O(N*1000*1000/32).

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

    just do knapsack, and if u can make the sum looking more than 1 time than there is another subset that can make this sum. corner case is zero (ignore it).

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

      What's your complexity N3 ?

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

        o(n^2)

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

          Please share your code .

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
            ← Rev. 2   Vote: I like it +3 Vote: I do not like it 
            void solve(){
   int n ; 
   cin >> n ; 
   vector < int > a(n) ;
   for( int i = 0 ; i < n ; i++) cin >> a[i] ;
   vector < vector < int > > dp(n,vector<int>(1001));
   dp[0][0] = 1 ;
   dp[0][a[0]] = 1 ;
   for( int i = 1 ; i < n ; i++){
       for( int j = 0 ; j < 1001 ; j++){
           dp[i][j] = dp[i-1][j] ;
           if(j>=a[i] && a[i]!=0){
               dp[i][j] += dp[i-1][j-a[i]];
               if(dp[i][j]>2) dp[i][j] = 2 ;
           }
       }
   }
   vector < int > ans(n);
   for( int i = 0 ; i < n ; i++){
       if(dp[n-1][a[i]]==2 || a[i]==0){
           cout << "1 " ;
       }
       else{
           cout << "0 ";
       }
   }
   cout << "\n";
}
            → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    You can store the number of ways to get a sum of x by in dp[x]. Thus, if the number of ways is greater than 1, then there exists a subset with equal sum. One implementation detail to take care of is to ignore 0 valued elements and set dp[0] to 1 initially as sum of empty set is 0.

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

Can someone share the intuition for the F problem? Problem Link

I was able to arrive at an O(N^2) solution using dp.

How to solve it efficiently ?

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

    A brief writeup of my O(N*logM) soln.

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

      Won't there be a state for number of days we have successfully passed?

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

        Solve like sweep algorithm.
        Keep O(M) states when we reach ith index and then convert them into O(M) i+1 th. Notice that only one of them changes.

        → Reply