you are so quickly!

好快

I will kill myself over B. UPD: Found my error

I spent lot's of time considering 1:0 situations in problem B.

fast editorial

Clarification: SlavicG and I actually are best friends, he's just playing hard to get.

In problem E, my code was giving me expected/correct output in my local machine, but is giving wrong output during codeforce's testing 274941437

Could any one tell why is that?

Can't believe how much bad this one went

G1<<E or F

can anyone help me, for which test case my code didn't work

//this code

#include<bits/stdc++.h>

using namespace std;

int main(){
    int t;
    cin>>t;
    while (t--)
    {
        int a1,a2,b1,b2;
        cin>>a1>>a2>>b1>>b2;
        int x1 = min(a1,a2), x2 = max(a1,a2);
        int y1 = min(b1,b2), y2 = max(b1,b2);

        if(x1==x2 && y1==y2 && x1==y1){
            cout<<0<<endl;
        }

        else if(x1>=y2){
            cout<<4<<endl;
        }

        else if(x2<=y1){
            cout<<0<<endl;
        }

        else{
            cout<<2<<endl;
        }
    }
    
    return 0;
}

my idea in D was right but i didn't code it

can someone help me with what's wrong with my solution of B?

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	// your code goes here
    int T;
    cin>>T;
    
    while(T--){
        int a1, a2, b1, b2;
        cin>>a1>>a2>>b1>>b2;
        
        int cnt = 0;
        if(a1 > b1 && a2 > b2) cnt++;
        if(a1 > b2 && a2 > b1) cnt++;
        if(a2 > b1 && a1 > b2) cnt++;
        if(a2 > b2 && a1 > b1) cnt++;
        
        cout<<cnt<<endl;
    }
}

I had the same intuition for F but I got stuck and I had no idea why my code was failing for the last provided test case. Values seem fine, but it keeps dumping to stack trace, isn't it just a O(n) loop with my factorials memoized?

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

#define debug 1

const ll limit = 2e5;
const ll mod = 1e9+7;

template<typename... Args>
void mycout(const Args&... args) 
{
    #if debug
    ((cout << args << ", "), ...); // Fold expression
    cout << endl;
    #endif
}

unordered_map<ull, ull> factorials;

const ull factorial(const ull n) 
{
    if (n <= 1) 
        return 1;

    if(factorials.contains(n))
        return factorials[n];

    factorials[n] = n * factorial(n-1);

    return factorials[n];
}

const ull pickKFromN(const ull n, const ull k)
{
    if(n <= 0)
        return 0;

    const ull top = factorial(n);
    const ull btm = factorial(k) * factorial(n-k);
    
    return top/btm;
}

int main()
{
    ios::sync_with_stdio(false); 
    cin.tie(0); 
    cout.tie(0);
    
    ll t;
    cin >> t;

    while(t--)
    {
        // k is odd
        ll n,k;
        cin >> n >>k;

        vector<ll> v(n);
        ll sum{};

        
        for(ll i{}; i < n; ++i)
        {
            cin >> v[i];

            sum = (sum + v[i]) % mod;
        }

        if(k == 1)
        {
            cout << sum << endl;
            continue;
        }

        sort(v.begin(),v.end());
        
        // eg 3 will be 2th element so index 1
        ll medianIndex = (k == 1 ? 0 : (k+1)/2 - 1);
        
        if(k == n)
        {
            cout << v[medianIndex] << endl;
            continue;
        }

        ll result{};

        // given median index
        // i can pick index elements on the left
        // then pick k - 2

        /*
            6 3
            1 0 1 0 1 1
            
            medianindex == 1
            0 0 1 1 1
              ^

            1*2*2 == 4
            1*3*1 == 3
            

            0 0 1 1

            i1 : 
        */
        
        for(ll i{medianIndex}; i < n; ++i)
        {
            if(v[i] == 0)
                continue;

            const ull leftElements = i;
            const ull rightElements = n-i-1;

            const ull pickLeft = medianIndex;
            const ull pickRight = k-(medianIndex+1);

            const ull left = pickKFromN(leftElements,pickLeft) % mod;
            const ull right = pickKFromN(rightElements,pickRight) % mod;
            const ull combined = (((v[i] * left) % mod) * right) % mod;
            
            mycout(i,result,combined);
            mycout(leftElements,pickLeft,left);
            mycout(rightElements,pickRight,right);
    
            result = (result + combined) % mod;
        }

        cout << result << endl;
    }

    return 0;
}

from math import *
for _ in range(int(input())):
  l,r=map(int,input().split())
  ans=0
  if l<3:
    ans=1
  else:
    if power(l):
      ans+=ceil(log(l,3))+1
    else:
      ans+=ceil(log(l,3))
  before=ans
  print(ans,"BEFORE")
  for i in range(l+2,r+1):
    if power(i):
      ans+=ceil(log(i,3))+1
    else:
      ans+=ceil(log(i,3))
  print(ans,"AFTER")
  if r>l:
    ans+=ceil(log((3*before)*(l+1),3))+(1 if power((3*before)*(l+1)) else 0)
  print(ans,"ANSWER")

Got the Logic Couldn't make it up.

In editorial of G2 , if a < x <= b, area should be a * (b + 1) but given (a+1) * b. May be it's a Typo SlavicG

I think G1 and G2 were much easier than E and F... the most basic binary search in both versions

Why my code 274894324 is getting WA on E? I did all exactly as in editorial

i swear to god B took more time than A,C,D,E

Should've been able to solve E. But we move

In the code for B, since you are using Python, ans++ should give syntax error. Just a minor detail! Thanks for the quick editorial:D

Need to improve my comprehensive understanding of paragraphs , spend a lot of time on B,

missed the point that only one win is enough when the second one is draw (missed this one)

Just got an observation for E:
[1, 3) -> all elements require 1 operations to become 0
[3, 9) -> all elements require 2 operations to become 0
[9, 27) -> all elements require 3 operations to become 0
[27, 81) -> all elements require 4 operations to become 0
[81, 81 * 3) -> all elements require 5 operations to become 0
and so on.

I think this could be optimal.

I love E, F, G2. Brilliant idea!!!

Can anyone tell me how to test our code for an interactive problem?

For problem E why is this O(n) code getting TLE?(https://codeforces.com/contest/1999/submission/274854161)

In G2, those who didn't understand how we are calculating value of a and b, here is the explanation:

Let, l < a < b < r, where a-l ≈ b-a ≈ r-b ≈ x, consider differences are almost same

So, we can say that r-l = 3x, where x = (r-l)/3, a = l + x, and b = l + 2x.

Hence, a = (2*l + r)/3 and b = (l + 2*r)/3

got humbled :'(

I'm so used to "Sum of n over all cases doesn't exceed $$$ 2 \times 10^5 $$$ " :)

I always thought I didn't need them yet, till maybe Spclist or Xpert. After reading the editorial, now i feel pitiful not learning how to do interactive problems earlier.

In which test case my submission 274924034 for E is failing.

Can some one tell the failing testcase for problem B for this code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int mod=1000000007;
int MAX_INT=2147483647;
                      
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--){
    int a1,a2,b1,b2;
    cin>>a1>>a2>>b1>>b2;
    int ans=0;
    if(a1>b1 && a2>=b2)
    ans++;
    if(a2>b1 && a1>=b2)
    ans++;
    if(a1>b2 && a2>=b1)
    ans++;
    if(a2>b2 && a1>=b1)
    ans++;
    cout<<ans<<endl;
}
return 0;
}

I dont understand why this gives wrong ans; E

Your code here...
int fun(ll x){
  int count = 0;
  while(x){
    count++;
    x = x/3;
  }
  return count;
}

void solve() {
  ll l, r;
  cin >> l >> r;
  ll ans = 0;
  ans += fun(l);
  ans+= fun(3*ans*(l+1));
  for(int i = l+2; i <= r; i++){
    ans+=fun(i);
  }
  cout << ans << endl;
}

Why is my D solution so slow? 274970418 I am using the same two pointer strategy that the editorial mentions and get TLE every time. I have a single loop iterating through the string and that is it. Am I using any expensive operations without realizing it? Thanks in advance.

F is a pretty simple combinatorics problem, and G1 is a simple binary search. However I somehow failed to solve those problems in the contest :(

Can anyone tell that why in E O(n log n) doesn't work ? To be precise the overall complexity would be 2.5*10^6, which should pass in 1 sec. ? isn't it?

I got another simpler setup approach to E, perhaps.

We will make an array of the exponentiation of 3, like lt[0] = 1, lt[1] = 3, lt[2] = 9, lt[3] = 27, ..., lt[15] = 3^15. (Because r <= 2 . 10 ^ 5)

We will make a prefix sum before making the testcase. For each i, call j is the smallest number satisfying a[i] >= lt[j], (1 <= j <= 15).

For example, a[1] = 1, a[2] = 1, a[3] = 2, a[4] = 2, ..., a[8] = 2, a[9] = 3, a[10] = 3, ... After that we will make a prefix sum of a[] called f[]. For instance, f[1] = 1, f[2] = f[1] + a[2] = 2, f[3] = f[2] + a[3] = 4, ...

For each n, m in the testcase, to find the minimum operation needed, while n, m is typed from the keyboard, the answer will be pre[m] — pre[n-1].

Then plus the a[n], as we have to make n become 0 to minimize the operations, the final thing to do is f[m] — f[n-1] + a[n].

Link: My sub

Can anyone help me find out the bug in my code for problem D? It passed all testcases, but it got hacked, and I don't know how to find the specific testcase in which it failed at.

https://codeforces.com/contest/1999/submission/274881476

Thanks in advance! If this is against the rules of the contest, please let me know so I can delete this comment.

You know for the Showering question how did you not get a memory exceeded error??

#include <bits/stdc++.h>

using namespace std;


int main(){
  cin.tie(nullptr)->sync_with_stdio(false);
  int t,n,s,m;
  cin >> t; 
  int start, end;
  vector<int> time; 
  while (t--){
    time.clear();
    cin >> n >> s >> m;// 0 is free and 1 is busy
    while (n--){
      cin >> start >> end;
      while(start < end){
        time.push_back(start);
        start += 1;
      }
    }
    sort(time.begin(), time.end());
    int free_time = time[0];
    for (int x = 0; x<time.size() - 1; x++){
      if (time[x+1] - time[x] > 1 && time[x+1] - time[x] > free_time){
        free_time = time[x+1] - time[x] - 1;
      }
    }
    if (m - time[time.size()-1] - 1 > free_time){
      free_time = m - time[time.size() - 1] - 1;
    }
    if (s <= free_time){
      cout << "YES" << "\n";
    }
    else{
      cout << "NO" << "\n";
    }
  }
  return 0; 
}

I am also using a linked list to store the timings which aren't available. But test case 3 threw a memory exceeded error.

in the problem E as the editorial said f(x) = 1 + Math.floor(log(x) in base 3) then why the below code is giving wrong answer

**Can anyone tell me , why its giving Tle , or is it wrong ** ~~~~~ int main() { // startTime = clock(); ios_base::sync_with_stdio(false); cin.tie(NULL);

ifndef ONLINE_JUDGE

freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);

endif

int N = 1e5;
vector<int> dp(2*N + 100);
dp[0] =0, dp[1] =1 , dp[2] =1 , dp[3] =2;
for(int i=4;i< dp.size();i++) dp[i] = 1 + dp[(i/3)];
int test ;
cin >> test;

while (test--) {
    int x,y;
    cin>>x>>y;
    int ans =0;
    ans = 2*(1 + dp[(x/3)]);
    x+=1;
    // for(int i=0;i<=10;i++) cout<<i<<" "<<dp[i]<<"   ";
    while( x<= y){
        ans += (1 + dp[(x/3)]);
        x++;
    }
    cout<<ans<<endl;
}
return 0;

} ~~~~~

E is good, but isn't the data range a bit small? Many $$$O(Tn)$$$ algorithms can pass this problem, and it's hard to hack them.

For Problem E, I am running a loop here of size (b-a+1) each time. I tried hacking my solution on max size testcase $$$10000 \newline 1\;200000\newline....\newline....\newline1\;200000\newline$$$ . I don't know this solution got accepted? Can anybody tell the reason for the same or else try to hack it?

Submission link

Harder Version of F if anyone wants to try. Sum of Medians

Can any one give me more explain for problem F , i did not Understand tut :(

I solved E without DP, iteratively and a bit of maths.. My Solution

I spent much time on D,at first,i don't kown the meaning of it,due to this,i don't have time to solve E