Div2 C level problems are probably what's preventing us to get beyond the specialist rating on codeforces. Let's practice a lot of them and make breakthroughs into new terrains!!

It is also meaningful to study C problems as a division2 contestant, since C problems are also A problems in division1. This means that problem C in division2 is the first "difficult" problem that requires non trivial algorithmic thinking.

Analysis : Because of the constraint that n is less than or equal to 3000, we can brute force for the solution with time complexity of O(n ²). A possible way to do this is to fix j, then for each i where 0 ≦ i < j, if s[j] > s[i], then update the minimum possible cost we can for i for this particular j. Do the same for k for all j+1 ≦ k < n. The final answer would be min(minimum cost for i for chosen j + cost for j + minimum cost for k for chosen j).

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map> 
using namespace std; 
#define IOFAST() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
const long long INF = (long long)2e17+88; 
long long s[3005]; 
long long c[3005]; 
int main(int argc,char *argv[]){
    IOFAST();   
    int n; 
    cin >> n;  
    for (int i = 0; i < n; i++){
        cin >> s[i]; 
    }
    for (int i = 0; i < n; i++){
        cin >> c[i]; 
    }
    long long ans = INF; 
    for (int j = 0; j < n; j++){
        long long min_cost_i = INF, min_cost_k = INF;  
        for (int i = 0; i < j; i++){
            if (s[i] < s[j]) min_cost_i = min(min_cost_i,c[i]);  
        }
        for (int k = j+1; k < n; k++){
            if (s[j] < s[k]) min_cost_k = min(min_cost_k,c[k]);  
        }
        ans = min(ans,min_cost_i + c[j] + min_cost_k); 
    }
    if (ans == INF) cout << -1 << endl; 
    else cout << ans << endl; 
    return 0; 
}

Analysis : Initially I thought about the following algorithm - given a,b I multiply ab, then prime factorize this number. I then check whether each of its prime factors have exponent equal to 3. If not then it must not be the answer. This method most likely times out because ab can be at most 10¹⁸, and the prime factorization algorithm that I know of runs in O(sqrt(ab)) time complexity. What makes it worse is that there will at most 350000 queries. This means that I need another method. I tried various method until I forfeited and read the tutorial. The tutorial's reasoning was quite simple. Given a,b, define S as the numbers called out by Slastyona and P as the result called out by Pushok. Since a represents the results of Slastyona and b represents the result of Pushok respectively, we must have a = S ²P and b = SP². Furthemore ab = S³P³. Now S = S²P/SP = a/∛ab. Similarly P = SP²/SP = b/∛ab. This means that we have to check two things.

#include <iostream>
#include <cstdio> 
#include <cstdlib>
#include <algorithm>
using namespace std; 
typedef long long ll;  
ll isPerfectCube(ll x){
    ll l = 1LL, r = min(x,1000000LL);  
    while (l <= r){
        ll mid = (l+r)>>1LL; 
        if (mid*mid*mid == x) return mid; 
        else if (mid*mid*mid < x) l = mid+1; 
        else r = mid-1; 
    }
    return -1;  
}
int main(){
    int n; 
    scanf("%d",&n);  
    while (n--){
        ll a,b; 
        scanf("%lld %lld",&a,&b);  
        ll c = a*b,x;  
        if ((x = isPerfectCube(c)) != -1){
            if (a%x == 0 && b%x == 0) puts("Yes");   
            else puts("No");   
        }else{
            puts("No");   
        }
    }
    return 0; 
}

Analysis : After reading the problem I realised instantly that choosing the appropriate value of k would require binary search over the space [1,n]. However, for each binary search we do, we have to check if the value of k we chose is appropriate or not. Wouldn't this checking function that too much time because n is at most 10 ¹⁸? It turns out that simply simulating the entire process is quick enough. In fact the checking function is capped by at most 500 (probably even less but this is just a rough estimate) steps because note that 10 ¹⁸ * (0.9) ⁵⁰⁰ is already a very small value that is close to zero. This shows that at each step n decreases exponentially. As a result we can binary search for the appropriate k and just code up a simulation of what's described in the problem for our checking function.

#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;  
typedef long long ll; 
bool ok(ll x,ll n){
    ll vasya = 0; // amount eaten by vasya
    ll temp = n;   
    while (temp){
        vasya += min(x,temp); 
        temp -= min(x,temp); 
        temp -= temp/10; // reduce by ceiling of 10% 
    }
    return 2LL*vasya >= n; 
} 
int main(){
    ll n;  
    cin >> n; 
    ll l = 1LL, r = n;  
    while (l <= r){
        ll mid = (l+r)>>1LL;  
        if (ok(mid,n)){
            r = mid-1; 
        }else{
            l = mid+1; 
        }
    }
    cout << l << endl; 
    return 0; 
}

Codeforces Div2 C level problems

Analysis by Luke Kim