Блог пользователя nikesh04

Автор nikesh04, история, 4 года назад, По-английски

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!

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

contest is not loading 502 gateway error:(

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Code
        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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).

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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).

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      What's your complexity N3 ?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        o(n^2)

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Please share your code .

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
            Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
            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";
            }
            
  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 ?

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    Spoiler