### nikesh04's blog

By nikesh04, history, 13 months ago,

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

 » 12 months ago, # |   +15 contest is not loading 502 gateway error:(
 » 11 months ago, # | ← Rev. 2 →   0 Hint for last problem ?probably greedy with taking mid does not work
 » 11 months ago, # | ← Rev. 2 →   0 Please share approach for "Arrays and Sum" , I solved 4 questions and this one partial .
•  » » 11 months ago, # ^ |   0 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, # ^ |   0 Can u please share your code ... and it will be more helpful if anyone share most optimized approach for this question
•  » » » » 11 months ago, # ^ |   0 Code#include #define ll long long int #define pll pair 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; }
•  » » » » » 11 months ago, # ^ |   0 What u just did brute force , remove current element and apply subset sum problem for remaining elements . WTH.
•  » » » » » 11 months ago, # ^ |   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).
•  » » 11 months ago, # ^ |   +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).
•  » » » 11 months ago, # ^ |   0 What's your complexity N3 ?
•  » » » » 11 months ago, # ^ |   0 o(n^2)
•  » » » » » 11 months ago, # ^ |   0 Please share your code .
•  » » » » » » 11 months ago, # ^ | ← 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(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 →   0 " 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
•  » » 11 months ago, # ^ | ← 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#include #define rep(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<
 » 11 months ago, # |   0 Can someone share the intuition for the F problem? Problem LinkI was able to arrive at an O(N^2) solution using dp.How to solve it efficiently ?
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 A brief writeup of my O(N*logM) soln. SpoilerNotice that one will be at a[i-1] when we want to go to a[i].This gives N^2 DP.There are 2 transitions for each state (a[i-1],y) to (a[i-1],a[i]) or (a[i],y).Lets calculate a[i],j 0<=j<=M from a[i-1],k 0<=K<=M.Ignore the first transition.For 2nd transition update (a[i],a[i-1]) with min(abs(y-a[i])+dp[a[i]][y]) — abs(a[i]-a[i-1]) for 0<=y<=M.Difference if we opt for 2nd instead of first.Can be done in O(logM) using segment trees.At last add abs(a[i]-a[i-1]) for 0<=i<=N in minimum(a[n],y).
•  » » » 11 months ago, # ^ |   +3 Won't there be a state for number of days we have successfully passed?
•  » » » » 11 months ago, # ^ |   -8 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.
•  » » » » » 11 months ago, # ^ |   0 Can you share the code,as they're not visible yet.
•  » » » » » » 11 months ago, # ^ |   0 Sure. link