B1 + B2 detailed video tutorial

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

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<n; i++){

            if(arr[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
    }
}

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

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

rainboy orz

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;

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;

}

Love it, thank you

for B1 using prefix sum with Binary Search worked for me, but could not apply the same to B2 :(