Shayan's blog

Codeforces Round 961 (Div. 2) — Video Tutorial
By Shayan, history, 2 years ago, In English

1995A — Diagonals

1995B1 — Bouquet (Easy Version)

1995B2 — Bouquet (Hard Version)

1995C — Squaring

1995D — Cases

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.

  • Vote: I like it
  • +10
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
2 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

B1 + B2 detailed video tutorial

https://youtu.be/WIYtTD_-46k?feature=shared

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

B1 can be easily solved using sliding window. But complexity will be O(nlogn) since need to sort the array.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

rainboy orz

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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<n; ++i) {
    if (a[i] == 1 && maxel > 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;
→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I am not able to understand the intuition behind it. why we reversing the square when a[i]>maxel

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      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).

      → Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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.

include <bits/stdc++.h>

define INF_INT 2147483647

define what_is(x) cerr << #x << " is " << x << endl;

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;

}

→ Reply