### Shayan's blog

By Shayan, history, 10 days ago,

## 1995E2 — Let Me Teach You a Lesson (Hard Version)

Just explained a code. If you know the full solution, please write that in the comments below.

• +4

 » 10 days ago, # |   +5 B1 + B2 detailed video tutorialhttps://youtu.be/WIYtTD_-46k?feature=shared
 » 10 days ago, # |   -27 Solved Problem C using dp.It was a very fun round.static PrintWriter out = new PrintWriter(System.out); static FastReader s = new FastReader(); public static void main(String[] args) { int T = 1; T = s.nextInt(); outer:while (T > 0) { T--; int n = s.nextInt(); long arr[] =s.readArrayLong(n); long count = 0; for(int i = 0 ; i < n; i++){ if(arr[i] > 1)count++; if(arr[i]==1 && count > 0){ System.out.println(-1); continue outer; } } long ans = 0; long dp[] = new long[n]; for(int i =1; i=arr[i-1] && arr[i-1] !=1 ){ long a = arr[i-1]; long sum = 0; while(a < arr[i]){ a = a*a; sum = sum+1; } long b = 0; if(a > arr[i])b++; if(sum <= dp[i-1]){ dp[i] = Math.abs(sum -dp[i-1])+b; ans = ans+dp[i]; } }else if(arr[i] < arr[i-1]){ long a = arr[i]; long sum = 0; while(a < arr[i-1]){ a = a*a; sum++; } dp[i] = sum + dp[i-1]; ans = ans+dp[i]; } } System.out.println(ans); // end of while loop } }
 » 10 days ago, # |   0 How to find maximal value of a * i + b * j <= K, if 0 <= i <= N, 0 <= j <= M ?I guess, solving it less than O(N), is solution for B2 + B1
•  » » 10 days ago, # ^ |   0 Here a+1=b, so we can do it without anything special. Let me explain how I processed each type of flower. Take as many flowers of type a with m coins. Calculate the number of petals. If b=a+1, take as many flowers of type b with the remaining coins. Increase the number of petals according to this. Now lets say u have chosen x flowers of type a and y flowers of type b. If the total number of flowers of type b is b_total, you still have the option to take b_total-y flowers, but dont have the coins for it. But you still can replace the flowers of type a which are already taken with flowers of type b which which are not taken by spending 1 extra coin (since a+1=b). So your number of petals can increase by min(x,b_total-y,remaining_coins). Do this for each type of petal a.The implementation can be different but this is the idea which helped me solve it.
 » 10 days ago, # |   0 B1 can be easily solved using sliding window. But complexity will be O(nlogn) since need to sort the array.
•  » » 10 days ago, # ^ |   0 I sorted the array and was able to solve both B1 and B2.
 » 10 days ago, # |   0 rainboy orz
 » 10 days ago, # |   0 Hi, I used mathematics to make the problem C a little simpler. Check my solution - int n; cin >> n; vi a(n); read(a); int powcnt = 0; int maxel = a[0]; int count = 0; for (int i=1; i 1) { cout << -1 << endl; return; } double value; if (maxel > a[i]) { value = log2(log2(maxel) / log2(a[i])); } else { value = -1 * log2(log2(a[i]) / log2(maxel)); } value += powcnt; if (value >= 0) { powcnt = ceil(value); count += powcnt; maxel = a[i]; } else { maxel = a[i]; powcnt = 0; } } cout << count << endl; 
•  » » 10 days ago, # ^ |   0 I am not able to understand the intuition behind it. why we reversing the square when a[i]>maxel
•  » » » 8 days ago, # ^ |   0 We are not squaring anywhere — The intuition is that for A^(2^x) to be <= than B^(2^y), given A (maximum element till now), x (the number of times we did the operation) and b (current element), we need to find y (the number of times we have to do operation for B), which turns out to be the above logarithmic equations after taking logs both side (twice).
»
10 days ago, # |
0

Straight up 2 min code solving B1 is using two pointers. (Why this works?) is because the ranges is <= 1, so if all the elements were sorted then we can find the subarray of the sorted using 2 pointers.

# define all(v) v.begin(), v.end()

typedef long long ll; using namespace std;

void solve() { ll n, m; cin >> n >> m; int a[n];

for (int i = 0; i < n; i++) cin >> a[i];
sort(a, a+n);

int left = 0, right = 0;
ll sum = 0;

ll ans = 0;
while (left < n && right < n) {
while (right < n) {
if (sum + a[right] <= m && a[right] - a[left] <= 1) {
sum += a[right];
right++;
} else {
break;
}
}

ans = max(ans, sum);
sum -= a[left];
left++;
}

cout << ans << '\n';

}

int main(void) { ios::sync_with_stdio(false); cin.tie(nullptr);

int i; cin >> i;

for (int n = 0; n < i; n++) {
solve();
}
return 0;

}

 » 10 days ago, # |   0 Love it, thank you
 » 10 days ago, # |   0 for B1 using prefix sum with Binary Search worked for me, but could not apply the same to B2 :(