you are so quickly!

so fast!

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

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.net/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.net/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

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

For F, with x numbers 1, this formula $$$\binom{x}{k/2+1} * \binom{n-(k/2+1)}{k/2}$$$ is correct?

The logic is that we take $$$k/2+1$$$ from $$$x$$$ numbers of 1, and whatever others elements are(taking $$$k/2$$$ from the left $$$n - (k/2+1))$$$ the median will be 1

Can someone solve E when l and r are large i.e upto 1e18 it could possibly turn out to be a good math problem.Please do write if you have any idea on how to do it?

Problem B is unreasonable

I really appreciate problem E. I have seen the pattern: "To use the fewest number of operations possible, we should do the first step on the minimum number, since it has the fewest digits." after writing down a few cases, but I failed to come up with prefix sum part.

Thank you. Now I learn.

Can anyone let me know why this gives TLE.Even the solution code precomputes till 2e5.275010837

In problem E, function $$$f$$$ takes $$$O(\log_3 x)$$$ to compute on a number $$$x$$$, so your complexity is $$$O(n \log n)$$$, not $$$O(n)$$$. However, there is a simple way to compute $$$f(1), f(2), \ldots, f(n)$$$ in $$$O(n)$$$ overall, without utilizing any expensive math functions: notice that $$$f(x) = f(\lfloor x / 3 \rfloor) + 1$$$. The code is even shorter than before: 275014438.

why this code is giving me a TLE question E /*#include<bits/stdc++.h> using namespace std;

define ll long long

vectorv; void seiv(){ ll cnt=1; v.push_back(0); while(cnt<=200000ll){ v.push_back(cnt); cnt*=3; } } int main(){ seiv(); ll t; cin>>t; while(t--){ ll l,r; cin>>l>>r; ll ans=(upper_bound(v.begin(),v.end(),l)-v.begin()-1); ll c=ans; for(ll i=l;i<=r;i++){ if(v[c+1]==i){ c++; } if(v[c]<=i){ ans+=c; } } cout<<ans<<endl; } } */

G2 is just introduction to ternary search.

can anyone tell why my e code of o(n) is giving tle ? :- https://codeforces.net/contest/1999/submission/274942317

I regret not studying interactive problems!

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <ctype.h>
#include <queue>
#include <cstring>
#include <set>
#include <bitset>
#include <map>
#include <chrono>
#include <random>
#include <unordered_map>
#include <stdio.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef std::vector<int> vi;
typedef std::vector<bool> vb;
typedef std::vector<string> vs;
typedef std::vector<double> vd;
typedef std::vector<long long> vll;
typedef std::vector<std::vector<int> > vvi;
typedef vector<vll> vvll;
typedef std::vector<std::pair<int, int> > vpi;
typedef vector<vpi> vvpi;
typedef std::pair<int, int> pi;
typedef std::pair<ll, ll> pll;
typedef std::vector<pll> vpll;

const long long mod = 1000000007;
//ll gcd (ll a, ll b) {return b==0 ? a : gcd(b, a%b);}
//const unsigned gen_seed = std::chrono::system_clock::now().time_since_epoch().count();
//std::mt19937_64 gen(gen_seed);

#define all(c) (c).begin(),(c).end()
#define srt(c) sort(all(c))
#define srtrev(c) sort(all(c)); reverse(all(c))
#define forn(i, a, b) for(int i = a; i < b; i++)
#define read(x) scanf("%d", &x)
#define readv(x, n) vi x(n); forn(i,0,n) scanf("%d", &x[i])

#define pb push_back
#define mp make_pair


void solve ( ) {
ll l = 2 , r = 999  ;


               while ( r -l > 1  ){
                        ll mid = ( l+r)/2 ;

                        cout << "? 1 "<< mid << endl;

                       ll val ;

                       cin >> val;

                       if ( val == (mid+ 1)) {
                        r = mid ;
                       }
                       else {
                        l = mid ;
                       }


               }
        cout << "!" << " " << l+1 << endl;

}
int main()
{
#ifdef LOCAL
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
#endif

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

    int ta;
    scanf("%d\n", &ta);

    forn(ifa,0,ta) {


        solve ( ) ;


    }


}

why this code is giving idelness ?

can anyone help me with this code of f? is this correct approach or not?

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int f(int i,int ones,int zeros,vector<int>&v,vector<vector<vector<int>>>&dp,int k,int m){
    if(k==0){
        if(ones>zeros)return 1;
        else 0;
    }
    if(i>=v.size())return 0;
    if(dp[i][ones][zeros]!=-1)return dp[i][ones][zeros];
    int a=0,b=0;
    if(v[i]==1){
        a=a+f(i+1,ones+1,zeros,v,dp,k--,m);
    }
    else{
         a=a+f(i+1,ones,zeros+1,v,dp,k--,m);
    }
    b=b+f(i+1,ones,zeros,v,dp,k,m);
    
    return dp[i][ones][zeros]=(a+b)%m;
    
}

int32_t main() {
    
    int t;
    cin>>t;
    while(t--){
        int n,k,one=0,zero=0;
    cin>>n>>k;
    vector<int>v;
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        v.push_back(a);
        if(a==1)one++;
        else zero++;
    }
    int m=1e9+7;
    vector<vector<vector<int>>>dp(n+2,vector<vector<int>>(one+2,vector<int>(zero+2,-1)));
    int ans=0;
       ans=f(0,0,0,v,dp,k,m)%m;
        cout<<ans<<endl;
        
    }
    
    
    
    return 0;
}

task b literally sent me into a deep dark depression

#include <bits/stdc++.h>
using namespace std;
#define int long long


void solve(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    int cnta=0,cntb=0;
    if(a>c&&a>d&&b>c&&b>d){
        cout<<4<<endl;    }
    else if((a>c&&b>d)||(a>d&&b>c)){
        cout<<2<<endl;
    }
    else if((a>c&&b==d)||(a>d&&b==c)||(b>c&&a==d)||(b>d&&a==c)){
        cout<<1<<endl;
    }
    else
    cout<<0<<endl;
}
int32_t main() {
	int t;
	cin>>t;
	while(t--){
	    solve();
	}

}

Can someone help which testcase I am missing