Invitation to HackerEarth's June Easy '20

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
22:43:57
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

Invitation to HackerEarth's June Easy '20

Автор 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!

#hackerearth, june easy, 2020

nikesh04
4 года назад
21

Комментарии (19)

Показать архивные | Написать комментарий?

living_in_genjutsu

4 года назад, # |

+15

contest is not loading 502 gateway error:(

→ Ответить

Chocobar

4 года назад, # |

← Rev. 2 →

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

→ Ответить

chandanagrawal23

4 года назад, # |

← Rev. 2 →

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

→ Ответить

Too_stupid

4 года назад, # ^ |

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

→ Ответить

chandanagrawal23

4 года назад, # ^ |

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

→ Ответить

Too_stupid

4 года назад, # ^ |

Code

#include <bits/stdc++.h>
#define ll long long int
#define pll pair <ll,ll>
 
using namespace std;
 
inline bool cool(ll set[], ll n, ll sum) 
{
    bool subset[n + 1][sum + 1]; 
    for (ll i = 0; i <= n; i++) 
        subset[i][0] = true; 
    for (ll i = 1; i <= sum; i++) 
        subset[0][i] = false; 
    for (ll i = 1; i <= n; i++) 
    { 
        for (ll j = 1; j <= sum; j++) 
        { 
            if (j < set[i - 1]) 
                subset[i][j] = subset[i - 1][j]; 
            if (j >= set[i - 1]) 
                subset[i][j] = subset[i - 1][j] || subset[i - 1][j - set[i - 1]]; 
        } 
    }
    return subset[n][sum]; 
} 
int main()
{
    ll t;
    cin >> t;
    while(t--)
    {
        ll n;
        cin >> n;
        ll ar[n];
        for(ll i = 0; i < n; i++)
            cin >> ar[i];
        for(ll i = 0; i < n; i++)
        {
            ll fuck[n - 1];
            ll idx = 0;
            fill(fuck, fuck + n - 1, false);
            for(ll j = 0; j < n; j++)
            {
                if(i != j)
                {
                    fuck[idx] = ar[j];
                    idx++;
                }
            }
	    if(cool(fuck, n - 1, ar[i]))
                cout << 1 << " ";
            else
                cout << 0 << " ";
        }
        cout << endl;
    }
    return 0;
}

→ Ответить

aryanc403

4 года назад, # ^ |

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

→ Ответить

darkworld1

4 года назад, # ^ |

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

→ Ответить

chandanagrawal23

4 года назад, # ^ |

What's your complexity N³ ?

→ Ответить

darkworld1

4 года назад, # ^ |

o(n^2)

→ Ответить

chandanagrawal23

4 года назад, # ^ |

Please share your code .

→ Ответить

darkworld1

4 года назад, # ^ |

← Rev. 2 →

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";
}

→ Ответить

Eunoia__1729

4 года назад, # ^ |

← Rev. 2 →

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

#include <bits/stdc++.h>
#define rep(i,a,b) for (i=a;i<b;i++)
#define rep2(i,a,b) for (i=a;i>=b;i--)
#define endl '\n'
#define ll long long
#define vll vector < ll >
#define pb push_back
#define mk make_pair
#define sz(a) a.size()
#define all(a) a.begin(),a.end()
using namespace std;
int main()
{
    ll t, n, m, q, maxx,  i, j, k, x, y, flag, sum, cnt, ans, minn, cur;
    cin>>t;
    while(t--)
    {
        cin>>n;
        vll v(n);
        vll res(n, 0);
        rep(i,0,n)
            cin>>v[i];
            
        vll dp(1001, 0);
        dp[0] = 1;
        rep(i,0, n)
        {
            if( v[i] == 0)
                continue;
            rep2(j,1000,v[i])
                if( dp[j - v[i]] > 0)
                    dp[j]++;  
        }
        dp[0] = INF;
        rep(i,0,n)
            cout<<( dp[v[i]] > 1) <<" ";
        cout<<endl;
    }
    return 0;
}

→ Ответить