nikesh04's blog

By nikesh04, history, 13 months 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

»
12 months ago, # |
  Vote: I like it +15 Vote: I do not like it

contest is not loading 502 gateway error:(

»
11 months 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

»
11 months 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 .

  • »
    »
    11 months 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.

    • »
      »
      »
      11 months 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

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

          What u just did brute force , remove current element and apply subset sum problem for remaining elements . WTH.

        • »
          »
          »
          »
          »
          11 months 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).

  • »
    »
    11 months 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).

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

      What's your complexity N3 ?

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

        o(n^2)

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

          Please share your code .

          • »
            »
            »
            »
            »
            »
            11 months 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";
            }
            
            • »
              »
              »
              »
              »
              »
              »
              11 months ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              " Heyy, can you please help me that what is wrong with my code , it's giving WA "

              ////////////////////////////////////////////////

              ll dp[10000+2][1000+4];

              int main() {

              // Use ctrl+shift+b ( second option )
              ios_base::sync_with_stdio(false);
              cin.tie(0);
              cout.tie(0);
              
              ll t;
              cin >> t;
              
              while (t--) {
              
                  ll n;
                  cin>>n;
              
                  ll a[n+2];
                  ll max_e = INT_MIN;
                  for(ll i=1;i<=n;i++){
                      cin>>a[i];
                      if(max_e < a[i]){
                          max_e = a[i];
                      }
                  }
              
                  sort(a+1,a+n+1);
              
                  memset(dp,0,sizeof(dp));
              
              
                  for(ll i=0;i<n+2;i++){
                      for(ll j=0;j<max_e+4;j++){
                          if(i==0)
                              dp[i][j]=0;
                          if(j==0)
                              dp[i][j]=1;
                      }
                  }
              
                  ll ans[n+3]={0};
                  for(ll i=1;i<=n;i++){
                          if(dp[i-1][a[i]]==1){
                              ans[i] = 1;
                          }else{
                              ans[i] = 0;
                          }
                      for(ll j=1;j<=max_e+1;j++){
                          if(a[i]<=j){
                              dp[i][j] = dp[i-1][j] | dp[i-1][j-a[i]];
                          }else{
                              dp[i][j] = dp[i-1][j];
                          }
                      }
                  }
              
                  for(ll i=1;i<=n;i++){
                      cout<<ans[i]<<" ";
                  }cout<<"\n";
              
              
              }
              
              
              return 0;
              

              }

  • »
    »
    11 months 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
»
11 months 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 ?

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

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

    Spoiler
    • »
      »
      »
      11 months 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?

      • »
        »
        »
        »
        11 months 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.