AtCoder Beginner Contest 165

C - Many Requirements

Problem Statement: here

Solution:

TAG - BackTracking, Full Search

The problem must be solved using the concept of recursion. The constraints were so small, that we could generate all the possible permutations of sequence A and check each sequence with all queries and compute the maximum answer.

I used simple recursion for each possible value of my current position. Since the element at the current position should be greater than the previous element, I pass the previous element as a parameter. Also do not forget to remove the element from vector once your forward recursion is complete.

The code:

V(ll) v; V(ll) q[51]; ll n,m,qp; ll ans = INT_MIN; void full(ll pos, ll past){ if (pos == n){ ll tsum = 0; rep(i,0,qp){ if (v[q[i][1]-1] - v[q[i][0]-1] == q[i][2]){ tsum += q[i][3]; } } ans = max(ans,tsum); return; }

rep(i,past,m+1){ v.PB(i); full(pos+1,i); v.pop_back(); } } void solve(){ cin >> n >> m >> qp; rep(i,0,qp){ rep(j,0,4){ ll t; cin >> t; q[i].PB(t); } } full(0,1); cout << ans << endl; }

Floor Function

Problem Statement: here

Solution:

This problem was simply based on a binary search. I applied the binary search blindly and it gave me AC. So, there is nothing to discuss I guess, but if you are not sure how binary search is working, (like me, lol NO!) you can take up values of A and B and check for values of x varying from 1 to N and plot it roughly. 

void solve() { ll a,b,n; cin >> a >> b >> n; ll low = 0; ll high = n; ll ans = INT_MIN; while(low <= high){ ll mid = (low + high)/2; if ((a*mid)/b - a*(mid/b) >= ans){ low = mid+1; ans = (a*mid)/b - a*(mid/b); } else high = mid-1; } cout << ans; }