Auto comment: topic has been updated by cry (previous revision, new revision, compare).

The G2 problem can also be solved by the MO algorithm. My solution is:https://mirror.codeforces.com/contest/2009/submission/279633321

binary search forces

Nice Div. 3 contest !

In problem E i used prefix sum and got MLE bruh...

Can we solve D faster than O(n^2) if xi's were real numbers instead of integers ?

In the C problem, there is a neat way to check whether there will be any other case or not.

Following the given explanation, one can see, that if any of the points on the side which contributes 2 points to the triangle are moved, the angle increases, and since we can't get them any closer without falling into Case 1, we can't have any more cases.

Another way that can be used is the fact that the slopes of the two perpendicular lines must give a product of -1.

So, if the points were $$$(x_{1}, 0), (x_{2}, 1), (x_{3}, 0)$$$, then we would have :

$$$(\frac{x_{2} - x_{1}}{1 - 0}) * (\frac{x_{3} - x_{2}}{0 - 1}) = -1$$$

which leads to :

$$$(x_{2} - x_{1})(x_{3} - x_{2}) = 1$$$

And since the differences will always be integers, we have :

$$$x_{1} + 1 = x_{2} = x_{3} - 1$$$

~~~~~~

if(x > y){
    cout << 2* ceil(1.0 * x/k) - (ceil(1.0 * x/k) >= ceil( 1.0 * y/k)) << endl;
    continue;
}

else {
    cout << 2 *ceil(1.0*  y/k)<< endl;
    continue;
}

~~~~~

why this fails??

I'm really happy to unrate b/c I'm really mad because I don't submit my code. :)))))

G2 and G3 are not div4 problems. They should only appear in div2 or div1.

Sharing my video of winning the round along with explanations of my solutions: https://www.youtube.com/watch?v=JhL-oPzptlI

E was great !

I tried solving E by interpreting it as a function and using the quadratic equation, but it keeps giving the wrong answer for n = 1000000000, k = 1000000000

typedef int64_t ll;
ll n, k, sk;
cin >> n >> k;

sk = gauss(k - 1); // starting k : the gauss sum of the numbers before the start of the series

ll max = gauss(k + n - 1) - sk;

// quadratic equation

// pref = gauss(n) - sk
// pref = (n^2 + n)/2 - sk
// where does 2pref intersect max? (because we want pref = max-pref)
// n^2 + n - 2*sk = max
// n^2 + n - (2*sk + max) = 0

// a = 1, b = 1, c = -(2*sk+max)

// delta = 1 ^ 2 - 4 * -(sk+max)
// delta = 1 + 4 * (2*sk + max)

ll delta = 1 + 4 * (2*sk + max);

// x1,2 = (-b +- sqrt(delta))/2*a
//	= (-1 +- sqrt(1 + 4 * (2 * sk+max)))/2 

ll x1 = round((-1 + sqrt(delta)) / 2);
ll x2 = round((-1 - sqrt(delta)) / 2);

ll x = min(abs(x1), abs(x2));

ll ans = 2 * (gauss(x) - sk) - max;
cout << abs(ans) << '\n';

For G1: There's a mathematical logic behind "ai — i". Let's say we have a sequence "(C, C + 1, C + 2, C + 3 + ...)". Any 'ith' element ai will be equal to "C + i — L", where 'L' is the starting index of the window. So (ai = C + i — L) => (C — L = ai — i). This (C — L) is a static part, which means we have to find the maximum occuring "ai — i".

You can think of E as an inverted mountain array and look for the minimum point using binary search

I think G1 can be solved by finding the longest increasing subarray for each query in O(logN)

Ans will be (right — left + 1) — longest;

My solution 279640569 of F, is giving correct output as 13 on my local and online compilers but wrong answer as 12 on codeforce's judge for following test case:

1

5 1

4 8 3 2 4

7 10

Can someone explain it?

dit con me codeforces lam gan het thoi gian moi bao deo cong rating, dung la cf rac

import java.util.*;
 
public class one {
    public static void main(String[] args) {
        java.util.Scanner sc = new java.util.Scanner(System.in);
 
        int t = sc.nextInt();
 
        for (int i = 0; i < t; i++) {
            long x = sc.nextLong();
            long y = sc.nextLong();
            long k = sc.nextLong();
            
            long jumpsX = (x + k - 1) / k; 
            long jumpsY = (y + k - 1) / k; 
 
            long moves = Math.max(jumpsX, jumpsY) * 2 ;
 
           
            if (x>y) {
                moves--;
            }
 
            System.out.println(moves);
        }
        sc.close();
    }
}

why wasnt this AC for the frog and freya question?

can somebody explain how they used binary search for E? i found the function to be unimodal and hence i applied ternary search to find the point of minima, i dont get the intuition for binary search (i dont see monotonicity)

The entire universe is against me for becoming pupil. Was doin super well today until that announcement appeared, L cry, L servers... MikeMirzayanov I think its time to add a new god damm server.

I miss SlavicG,mesanu,flamestorm ... (╥﹏╥)

Here is a clean(er than the edi) solution to C and a unique solution to D.

For C we can see that

As for D, which I found much more interesting, though do note I misread it and as such overcomplicated it.

Here are submissions for both, hope that puts these problems into a bit of a different perspective! C: 279561294 D: 279622363

This contest had quite a few issues with the queue and pages loading, however I still enjoyed the problems and I hope you did too! I would have gotten plus VE if this contest was rated however instead of complaining I had fun solving these problems even if I did overcomplicate D a bit, however it would give insight to a possible harder version of the problem if it was not only 0 and 1 on the Y.

G题太难啦。写了个 BZOJ4262 的做法才过。

This was a good round, sad that it got unrated.

thanks for writing, issues not your fault!

I have a different solution for G2. Use a set and a map to get the minimum moves for the window of size k starting from every index. Then use a stack to build a vector to store the index of next smaller number. Then use jumps to next smaller number to compute answer for every range.

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;
#define intt int64_t 

void solve()
{
    intt n, k, q;
    cin>>n>>k>>q;
    vector<intt> v(n);
    map<intt, intt> mp;
    for(int i=0;i<n;i++) 
    {
        cin>>v[i];
        v[i]-=i;
    }

    set<pair<intt, intt>> s;
    for(int i=0;i<k;i++)
    {
        mp[v[i]]+=1;
    }

    for(auto i:mp) s.insert({i.second, i.first});
    vector<intt> ans(n-k+1, 0);
    auto it = --s.end();
    ans[0]=k-(*it).first;

    for(int i=k;i<n;i++)
    {
        s.erase({mp[v[i-k]], v[i-k]});
        mp[v[i-k]]--;
        if(mp[v[i-k]]>0) s.insert({mp[v[i-k]], v[i-k]});
        mp[v[i]]++;
        s.insert({mp[v[i]], v[i]});
        auto it = --s.end();
        ans[i-k+1]=k-(*it).first;
    }
     
    vector<intt> next_min(n-k+1, 1e9);
    stack<intt> ck;
    for(int i=n-k;i>=0;i--)
    {
        if(ck.empty()) ck.push(i);
        else 
        {
            while(ck.size() and ans[i]<=ans[ck.top()])
            {
                ck.pop();
            }
            if(ck.size()) next_min[i]=ck.top();
            ck.push(i);
        }
    }
    while(q--)
    {
        intt l, r;
        cin>>l>>r;
        intt i = l-1;
        intt p =0;
        while(next_min[i]<=r-k)
        {
            p+=(next_min[i]-i)*ans[i];
            i=next_min[i];
        }
        p+=(r-k-i+1)*ans[i];
        cout<<p<<"\n";
    }
    
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

Nice Div3 Contest !!!

My code is failing in case of- 1000000 100000 10 givng me answer- 200000 !! Can someone point the mistake ?? Thanks

#include<bits/stdc++.h> 
using namespace std;
int main(){ 
   long t; cin>>t; 
   for(long i=0;i<t;i++){ 
      long long x,y,k; 
      long count=0; 
      cin>>x>>y>>k; 
      while(x>0 || y>0){ 
         int result_x=min(x,k);
         x-=result_x; 
         int result_y=min(y,k); 
         y-=result_y; 
          count+=2;
        } 
        cout<<count<<endl; 
    } 
    return 0;
}

I loved the HSR and Genshin references. Please do continue naming problems on our favourite characters. Thank you!

I have implemented the same logic as the solution above for 2009D - Satyam and Counting, but keep getting

Wrong answer on test 2: wrong answer 7th numbers differ - expected: '100', found: '99'

I cannot see the corresponding input.

Can anyone please tell me what I am missing? https://mirror.codeforces.com/contest/2009/submission/279654100

We can use binary search to search for the greatest i such that a1+⋯+ai≥ai+1+⋯+an

Isn't the solution for E wrong? If the above statement is the correct solution, the greatest i is just len-1 no?

In problem E's editorial ...

We can use binary search to search for the greatest i such that a₁ + ⋯ + a_i ≥ a_i+1 + ⋯ + a_n . Note that here, the positive difference is minimized. If we move to i+1 , then the negative difference is minimized (since the sum of prefix will now be less than the sum of suffix). The answer is the minimum absolute value of both cases.

It should be a₁ + ⋯ + a_i ≤ a_i+1 + ⋯ + a_n because we want to minimize the difference.

cry
(ignore the formatting)

Can't understood editorial solution for G2

G2 can also be solved using sqrt decomposition in $$$O(Q*N/B*log(B))$$$ where $$$B=\sqrt{N}$$$.

For each query, maintain the answer from left to right. If the current minimum is greater than the current block's minimum, we can use a binary search to find where the current block's first minimum is.

Submission: 279662760

Can we use ternary search at the problem E, though we need to find the minimum here?

anyone mind to explain solutions of G3?

Can someone suggest a testcase where this will fail for C? It fails on testcase 2.

wrong answer 862nd numbers differ — expected: '2', found: '1'

void solve()
{
    int x, y, k; cin >> x >> y >> k;
    int ans = 0;
    if (y >= x) {
        ans += (y / k) + (y % k > 0);
        ans *= 2;
    }
    else {
        ans = 2 * (x / k + (x % k > 0) - 1) + 1;
    }
    cout << ans << endl;

    cerr << endl;
    return;

}