### 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!  Comments (21)
 » contest is not loading 502 gateway error:(
 » 11 months ago, # | ← Rev. 2 →   Hint for last problem ?probably greedy with taking mid does not work
 » 11 months ago, # | ← Rev. 2 →   Please share approach for "Arrays and Sum" , I solved 4 questions and this one partial .
•  » » I do not know how but subset-sum did the work for me. According to the constraints I should have got partial points.
•  » » » Can u please share your code ... and it will be more helpful if anyone share most optimized approach for this question
•  » » » » 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] = true; for (ll i = 1; i <= sum; i++) subset[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; } 
•  » » » » » What u just did brute force , remove current element and apply subset sum problem for remaining elements . WTH.
•  » » » » » 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).
•  » » 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).
•  » » » What's your complexity N3 ?
•  » » » » o(n^2)
•  » » » » » Please share your code .
•  » » » » » » 11 months ago, # ^ | ← 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(1001)); dp = 1 ; dp[a] = 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 →   " 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 →   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 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 = 1; rep(i,0, n) { if( v[i] == 0) continue; rep2(j,1000,v[i]) if( dp[j - v[i]] > 0) dp[j]++; } dp = INF; rep(i,0,n) cout<<( dp[v[i]] > 1) <<" "; cout<
 » 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 →   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).
•  » » » Won't there be a state for number of days we have successfully passed?
•  » » » » 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.
•  » » » » » Can you share the code,as they're not visible yet.
•  » » » » » » Sure. link