### farukkastamonuda's blog

By farukkastamonuda, history, 3 months ago, , A-Luck(author Halit):

Solution

code by Halit

code

B-)Find the missed number(author Halit)

Solution

code

solution

code

D-) Smart Move(author farukkastamonuda)

solution

code by farukkastamonuda

code
Solution

code by farukkastamonuda

code  Comments (10)
 » 3 months ago, # | ← Rev. 2 →   I've hacked the official solution for E (in custom invocation at least, run in >15000ms) with the following test:350001 2 3 ... 35000.The runtime of the algorithm is actually O(n2) with bad constant, not O(n log n log MAX). And if you do not understand how the optimization in the official solution works, it can be easy to make this mistake.
 » Here is the solution for question C using stack with O(n) Time Complexity, CODE// ABHI YADAV #include using namespace std; #define ll long long signed main(){ ll n, k, i, j; cin >> n >> k; string s; cin >> s; stack> stk; for( i = 0 ; i < n ; i++ ){ if( stk.empty() || ( s[i] != stk.top().first ) ){ stk.push( {s[i],1} ); }else{ if( stk.top().second + 1 < k ){ stk.push({s[i],stk.top().second+1}); }else{ while( !stk.empty() && stk.top().first == s[i] ){ stk.pop(); } } } } string ans; while( !stk.empty() ){ ans += stk.top().first; stk.pop(); } reverse(ans.begin(),ans.end()); cout << ans << endl; return 0; } 
•  » » Good job. implementation with stack is easier than implementation with set. Thank you for your sharing.
 » 3 months ago, # | ← Rev. 4 →   Hi, for D i have a solution which runs in O(N*K) time and O(N+K) space CODE#include #define int long long using namespace std; main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int N, K; cin >> N >> K; int a[N]; for(int i = 0; i < N; i++) cin >> a[i]; int DP[K+1]; DP = 0; for(int i = 1; i <= K; i++) DP[i] = -LLONG_MAX; for(int i = 0; i < N; i++){ for(int k = min(K, i+1); k > 0; k--){ if(DP[k-1] == -LLONG_MAX) continue; int add = a[i] * (k%3) * ((k&1) ? -1 : 1); DP[k] = max(DP[k], DP[k-1] + add); } } for(int i = 1; i <= K; i++) DP[i] = max(DP[i], DP[i-1]); for(int i = K; i; i--) cout << DP[i] << " "; } I compared my code with your solution and it runs in (66 ms / 1153 ms, 3700KB / 193000 KB). I enjoyed the problems, but it was hard for me to understand the statements.
•  » » Thank you! Statements are not clear enough.
 » Can someone explain the optimization part of problem D?? I came up with the n*k*k solution during the contest which is the same as editorial but could not optimize it and even after reading the editorial, I am not able to understand completely.
•  » » if(hak>k) return -inf; I didn't change this if. And with this: int cikar=k-i; int ty=dfs(1,cikar,0,0); Firstly cikar means that how many element you select until now. Firstly cikar=0 then for K-1 case you set cikar to 1 and since it means that you are seen like take 1 element and if(hak>k) return -inf means that you can select at most k-1 elements now and you don't fill the dp array try and try.
•  » » I use recursion dp in this question. When you use recursivic dp ans_k = f(1,0,0,0)then if you dont clear the dp array and get the walue of f(1,1,0,0) then ans_k-1 = thisand you can do at most n*k*2*3 operation at most.
•  » » » Okay so we just didn't have to clear the dp table each time. Thank you, it was indeed a smart move.
 » Stack Solution works in O(n) in problem C.