#	User	Rating
1	tourist	4009
2	jiangly	3773
3	Radewoosh	3646
4	ecnerwala	3624
5	jqdai0815	3620
5	Benq	3620
7	orzdevinwang	3612
8	Geothermal	3569
8	cnnfls_csy	3569
10	gyh20	3447

#	User	Contrib.
1	cry	161
2	maomao90	160
2	awoo	160
4	atcoder_official	157
5	-is-this-fft-	155
5	nor	155
7	adamant	154
8	maroonrk	152
8	Um_nik	152
10	djm03178	146

Thanks for participating. We hope you enjoyed the contest!

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

void solve() {
	int n;
	cin >> n;
	cout << (n / 10) + (n % 10) << '\n';	
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

1999B - Card Game

Idea: SlavicG

Tutorial

Solution

def f(a, b):
    if (a > b): return 1
    if (a == b): return 0
    if (a < b): return -1
for _ in range(int(input())):
    a, b, c, d = map(int, input().split())
    ans = 0
    if f(a, c) + f(b, d) > 0:
        ans += 1
    if f(a, d) + f(b, c) > 0:
        ans += 1
    if f(b, c) + f(a, d) > 0:
        ans += 1
    if f(b, d) + f(a, c) > 0:
        ans += 1
    print(ans)

1999C - Showering

Idea: SlavicG

Tutorial

Solution

def solve():
    n, s, m = map(int, input().split())
    segs = [[0, 0], [m, m]] + [list(map(int, input().split())) for i in range(n)]
    segs.sort()
    for i in range(1, n + 2):
        if segs[i][0] - segs[i - 1][1] >= s:
            print('YES')
            return
    print('NO')


#sys.stdin = open('in', 'r')
for _ in range(int(input())):
    solve()

1999D - Slavic's Exam

Idea: SlavicG

Tutorial

Solution


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

int main() {
    int test_cases; cin >> test_cases;
    while(test_cases--) {
        string s, t; cin >> s >> t;
    	int idx = 0;
    
    	for(int i = 0; i < (int)s.size(); ++i) {
    		if(s[i] == '?') {
    			if(idx < (int)t.size()) s[i] = t[idx++];
    			else s[i] = 'a';
    		} else if(s[i] == t[idx]) ++idx;
    	}
    	if(idx >= t.size()) cout << "YES\n" << s << "\n";
    	else cout << "NO\n";
    }
}

1999E - Triple Operations

Idea: flamestorm

Tutorial

Solution


#include <bits/stdc++.h>

using namespace std;

const int MAX = 200'007;
const int MOD = 1'000'000'007;

int a[MAX], psum[MAX];

int f(int x) {
	int cnt = 0;
	while (x) {
		x /= 3;
		cnt++;
	}
	return cnt;
}

void solve() {
	int l, r;
	cin >> l >> r;
	cout << psum[r] - psum[l - 1] + a[l] << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	psum[0] = 0;
	for (int i = 1; i < MAX - 1; i++) {
		a[i] = f(i);
		psum[i] = psum[i - 1] + a[i];
	}
	
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

1999F - Expected Median

Idea: mesanu

Tutorial

Solution


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

const int N = 2e5 + 5, mod = 1e9 + 7;
int64_t fact[N];
int64_t pw(int64_t a, int64_t b) {
	int64_t r = 1;
	while(b > 0) {
		if(b & 1) r = (r * a) % mod;
		b /= 2;
		a = (a * a) % mod; 
	}
	return r;
}
int64_t C(int64_t n, int64_t k) {
	if(n < k) return 0LL;
	return (fact[n] * pw((fact[n - k] * fact[k]) % mod, mod - 2)) % mod;
}
int main() {
	int t; cin >> t;
	fact[0] = 1;
	for(int64_t i = 1; i < N; ++i) fact[i] = (fact[i - 1] * i) % mod;
	while(t--) {
		int n, k; cin >> n >> k;
		vector<int> a(n);
		int ones = 0;
		for(int i = 0; i < n; ++i) {
			cin >> a[i];
			ones += a[i];
		}
		//at least k/2+1 ones
		int64_t ans = 0;
		for(int cnt_ones = k / 2 + 1; cnt_ones <= min(ones, k); ++cnt_ones) {
			ans += C(ones, cnt_ones) * C(n - ones, k - cnt_ones) % mod;
			ans %= mod;
		}
		cout << ans << "\n";
	}
}

1999G1 - Ruler (easy version)

Idea: flamestorm

Tutorial

Solution


#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200'007;
const int MOD = 1'000'000'007;
 
void solve() {
	int l = 2, r = 1000;
	while (l < r) {
		int mid = l + (r - l) / 2;
		cout << "? 1 " << mid << endl;
		int resp; cin >> resp;
		
		if (resp == mid) {
			l = mid + 1;
		} 
		else {
			r = mid;
		}
	}
	cout << "! " << l << endl;	
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

1999G2 - Ruler (hard version)

Idea: flamestorm

Tutorial

Solution


#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200'007;
const int MOD = 1'000'000'007;
 
void solve() {
	int l = 1, r = 999;
	while (r - l > 2) {
		int a = (2 * l + r) / 3;
		int b = (2 * r + l) / 3;
		cout << "? " << a << ' ' << b << endl;
		int resp; cin >> resp;
		
		if (resp == (a + 1) * (b + 1)) {
			r = a;
		}
		else if (resp == a * b) {
			l = b;
		}
		else {
			l = a; r = b;
		}
	}
	if (r - l == 2) {
		cout << "? 1 " << l + 1 << endl;
		int resp; cin >> resp;
		
		if (resp == l + 1) {l = l + 1;}
		else {r = l + 1;}
		
	}
	cout << "! " << r << endl;
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

//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; }

#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")

#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; }

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; }

#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; }

void solve() { int l,r; cin>>l>>r; int cnt = 0 , mul = 1 , ans = 0; while( mul <= l ) { mul *= 3; cnt++; ans++; } while( l <= r ) { int range = min(r-l+1,mul - l); ans += range*cnt; l = mul; mul *= 3; cnt++; } cout<<ans<<endl; }

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; } } */

#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 ( ) ; } }

#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; }

#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(); } }

int point_for_round(int diff){ if(diff == 0) return diff; return diff> 0 ? 1 : -1; } void solve(){ int a1,a2,b1,b2; cin>>a1>>a2>>b1>>b2; int ans = 0; ans += (point_for_round(a1-b1) + point_for_round(a2-b2) > 0 ? 1 : 0); ans += (point_for_round(a1-b2) + point_for_round(a2-b1) > 0 ? 1 : 0); cout<<ans*2<<endl; }; int main(){ int t; cin>>t; while(t--){ solve(); } return 0; }

`void tripleOperations(int l, int r)` `{` ` vector<int> power3;` ` power3.push_back(1);` `` ` while (power3.back() <= r) power3.push_back(3 * power3.back());` ` int const n = power3.size();` `` ` int ix = upper_bound(power3.begin(), power3.end(), l) - power3.begin();` ` long long ans = 2*ix;` ` l++;` `` ` while (ix <= n-1)` ` {` ` ans += (min(r, power3[ix] - 1) - l + 1) * (ix);` ` l = power3[ix];` ` ix++;` ` }` `` ` cout<<ans<<'\n';` `}`

define int long long

signed main(){ ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0); int t; cin >> t; while(t--){ int l,r; cin >> l >> r; float ans=0.0; if(l == 1){ ans = 2.0; } else{ ans = ceil(log(l)/log(3)); ans *= 2; }

for(int i=l+1; i<=r; i++){ ans += ceil(log(i)/log(3)); if(ceil(log(i)/log(3)) == log(i)/log(3)){ ans++; } } cout << (int)ans << "\n"; }

} ~~~~~

for the input l = 19 & r = 84 it is giving ans = 262 but in vs code as well as in online c++ compiler it is showing 263 which is correct. please help.

Comments (206)

Write comment?

bawanglong

5 weeks ago, # |

you are so quickly!

→ Reply

yaLen

← Rev. 4 →

-22

so fast!

Allen123

5 weeks ago, # ^ |

use english, plz.

← Rev. 2 →

ok!

Rohak

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

steelxu

me too

SOMANSH24

same :___

Shaurya_Tomer

us moment

iamfreeezing

real

ziad-abdou1

me but i found it after one hour :(

Jack_2001

you and me both brother

AlexGook

i also cant understand, where is the mistake in my solution, it has the same meaning, but i get an error in test 2 every time

maut12

i'm a noob, but most probably what you were doing is only taking a subset of all possible combination. like i was not considering cases where first number can be equal and second is greater so win and i also was not considering if first number is greater second even if equal, we still get win.

nomanbinsafar

thanks found my mistake

Cp_Geek

You may check this out: Solution

Even i got frustrated over getting WA on test case 2, but eventually got what i was doing wrong. I just implemented all the 4 cases and found what was said.

Hope it helps!

Fastergood

哪道题？

so, i found my mistake, i didnt take into account that if there will be, for example, (a1 == b1 && a2 > b2), thats will be the victory of the first player(i dont know how will be the names of players of the task in english language, because i am I am a Russian-speaking person

scarywitcher

i got the answer from the notes section for B.

Plossom

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

hh我也是

nxsang1611

fast editorial

ScarletS

+25

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

AZaman007

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?

Aspirebugs

try using c++20 and then you will probably get wa on test2

keaucucal

Maybe different machine use different implement causing the different output ? Better not use log in this problem I guess, I stuck on that too.

hm, might be. My solution for d also passed test 1 but could not other ones,sad.

But all in one, I am happy to solve atleast few :D

SkibidiPilav

probably rounding errors with log. safer not to use log when you dont have to

haidarTawbeh

Try not using log

Drkway

Can't believe how much bad this one went

uday_bhai

G1<<E or F

Nxxlt

G1<F maybe, but E is definitely easier

anjay29

-6

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

redimberoc.cpp

Bro your code is correct only with the first case

Can you tell me where I am wrong? I don't know where I am wrong, for which test case my code is not working

Kesh_1523

you should add else if(x2<y2||x1<y1) cout<<0<<endl;

but bro the example you take 2 2 3 3,

x1 = 2 and y1 = 3

x2 = 2 an d y2 = 3

the output for above example is 0 and my code gives the 0 as output

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 == y1 && x2 == y2 )
        {
            cout << 0 << endl;
        }

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

        else if (x1 < y1 || x2 < y2)
        {
            cout << 0 << endl;
        }

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

    return 0;
}

Bro try this code. i just added a corner case to your code.

1574354102

9 days ago, # ^ |

for example: 1 2 1 2, your answer is 2, but current answer is 0;
1 3 2 2, your answer is 2, but current answer is 0;

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

TheRacistK

same

Can you tell me where I am wrong? I don't know where I am wrong, for which test case my code is not working.

FZFFFFFF

double point is okay

tapasyadimree

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

Spoiler

...

#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;
    }
}

you forgot about when Suneet wins one round and draws other...The equalities

oh righttt, thanks!

Are you talking about this case — 1 8 1 7

yes , here Suneet can win in two ways (1,1) ,(8,7) and (8,7) ,(1,1).

saudanwar17

you forgot to consider the cases like where a1>b1 && a2>=b2 This is also the win case

donnyboy

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?

opal_Inwza007x

← Rev. 3 →

I think you forgot to mod at factorial. And you should add mod inverse too :D

I’ll research on this, thanks!

Aswineeey

Got the Logic Couldn't make it up.

Daredevil_18

You have to use floor instead of ceil. The bigger problem here was many people getting WA on test 2 i.e. 1 243, this happened because of the definition of log function which uses natural log to calculate the log of any number. This causes errors due in precision and floating point arithmetic in some cases. So either the better way is to just do repeated floor division by 3, or by changing how log3 is implemented. I defined log3(n) = log2(n)/log2(3) which worked better because log2 works with binary which means better precision and less errors.

PizzaPasta

because r <= 2e5, you can do the array f[n] = ceil(log(n)), then f[i] = f[i/3] + 1, with f[0] = 0

A_xor_A

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

hrueschwein

Also, (2,a] should be [2, a]

flamestorm

Thanks, it'll be fixed soon.

Kotanys

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

AlephNullams2008

they're equally easy... it's just in F you should be more careful when preprocessing the factorial and the inverse array, while in E, G1 and G2 it's much easier to implement the idea, which was already easy before

I suppose you're right. It's just that to me F-like problems (with combinatorics etc.) are very difficult

MaxxxCoder

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

krism

← Rev. 5 →

check this testcase

243 244

l<r

Sorry...I have corrected it

noproblem :D

try 1, 999

This error is due to implementation of log here, which might give wrong answers due to floating point arithmetic errors. Better to either define log3(n)=log2(n)/log2(3) or to use while loop while doing floor division by 3.

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

sewarikyash

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

gurutej7

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)

Amit9

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.

This is exactly the idea I used in my solution 274869114

I was not left with enough time since stucked in correcting B :(
Btw your implementation is good.

Thanks! But I couldn't solve B at all, so sad

zrnstnsr

Yes, this can reach $$$O(\log\log n)$$$ complexity and also feasible to $$$r\le 10^{18}$$$.

How to precompute in log(log(n)) complexity?

I mean O(loglogn) for each query

This is what I did too, although I ended up writing extremely messy code.

actually this is only needed in the preprocessing phase so it won't improve the code much. also, the complexity goes from O(N + n) to O(log(log(N)) + n(log(n)), which is worse.

In what best complexity it can be done?

Ceon

another way would be to use dp, precompute the value for each number and then just add it by a for loop for the required l, r

nflight11

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

Imran435

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

You can write an answer function according to the description of problem. Then use it to simulate this whole process. Check my submission if you know python.

Thanks for the reply!!

But I did not quite understand it.

Would be great if I could find a C++ solution for that.

harikrishna_n

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

i dont think O(n) solutions passed, they used O(n) to precompute and then O(1) for each test case

Sum of $$$r-l$$$ is not bounded by $$$10^5$$$

For instance, $$$l=1, r=10^5$$$ can be given $$$10^4$$$ times. In that case, your approach will TLE

I don't understand. The time limit given in questions is 'per test case', then how do we analyze multiple test cases? Shouldn't O(n) for l = 1, r = 10^5 always pass in 1 second?

_Kee

No, the time limit is per test file, not per test case. If $$$t = 10^4$$$, your code must solve all the $$$10^4$$$ test cases within the time limit. (If the code was allowed $$$1$$$ second to run per test case, it would take at most $$$10^4$$$ seconds to finish all the cases, which is obviously infeasible.)

The problem doesn't guarantee the sum of $$$r-l$$$ is below $$$2\times 10^5$$$

coder0687

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

moz127

got humbled :'(

vsvg

Real shite

puupil

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

adiroy2

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.

bhagwandai

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

pspriyanshu601

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

rootCTRLer

8 1 1 1 doesn't work. Should be 4 but your program outputs 2.

i_would_win

I dont understand why this gives wrong ans; E

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.

CatsAreCool5530

In java, adding a letter to the end of a string is an O(n) operation, as it creates an entirely new string.

njmetro_jxzb

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 :(

ayush_5267

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?

'cuz the complexity is actually $$$O(tn\log n)$$$. Usually the problem guarantees the sum of $$$n$$$, $$$m$$$, etc. doesn't exceed $$$2\times 10^5$$$, but this problem does not.

ahh i get that, thanks dude!

because sum of r-l over all test cases isnt guaranteed to be under 2*10^5, so your code runs in O(t*n*logn)

ZeroPointTwo

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

this is actually the same as the editorial, it's just you're adding two pointer to it. but it's still better, as you're precomputing in O(n). another similar idea is that you build the a[] array like this: a[i] = a[i/3] + 1 for all 1 <= i <= 2e5

BlueGlaucus1

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.

Consider aaaaaaaaaaaaaaaaaaaaab and aaaaaaaaaaac. Your code will compare $$$O(n^2)$$$ times in this case.

Thanks!

JayceFR

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

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

The interval can be as large as $$$10^9$$$.

Oh i see, thank you so much.

_Abhinavv_

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

zugzwang15

The set of representable numbers on fixed floating point arithmetic is finite, and numbers that do not belong to it are rounded to the nearest representable number. Hence, usually it is difficult to keep perfect precision while doing floating point operations as it can behave in unexpected ways.

See this relevant blog: https://codeforces.net/blog/entry/78161

daf_2

I have the same error and take two hours to fix :))))) you can rewrite the log func with long long parameter.

Inkyo

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.

bhut_ho_gya

Can this solution pass higher constraints? Link

Turkmeniscoldish

You cannot have a $$$\mathcal{O}(Tn)$$$ algorithm for Problem E as the statement does not guarantee that the sum of all $$$n$$$ over all test cases does not exceed $$$2 \times 10^5$$$.

A $$$\mathcal{O}(Tn)$$$ algorithm could easily reach $$$2 \times 10^9$$$ iterations at worst, which is certainly not optimal to pass all tests under the time constraints imposed.

drgrenkenstein

you are repeating what he said

AdityaTakkar

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

Dominater069

the compiler isnt that stupid, it can optimize out obviously unnecessary parts

Timosh

-8

Firstly, you can't share hacks. Secondly, as the code works in $$$O(r - l)$$$ per test, the max amount of operations is 1e4 * 2e5, which is 2e9 operations, which is just enough to pass.

Trippie

Why can't you share hacks?
2e9 operations shouldn't pass in 1 second. That part of the code is obviously optimized by the compiler.

Anongoat

-10

The hacking phase is still running, Posting your hack is technically the same as sharing your solution during the contest.

djm03178

You can't simply count the number of operations to decide whether it will run in a specific time or not. The 'weight' of an operation depends on many other aspects than just a simple number of CPU instructions, and in this case the naive part is a very very light one, because it's about simply iterating and summing through an array in order, which leads to perfect cache hit rates and doesn't include any kind of heavy operations. 2e9 of such operations can mostly fit in time with computers nowadays.

But now that I see it, that specific solution is just compiler-optimized, and it didn't actually run the loop 2e9 times.

Can I see where it is stated that open hacks can't be shared? It's a post-contest hack where people can discuss the solutions, so I don't see why the test part can't be discussed. Hacks don't even give additional points. I've never seen discussion on open hacks being prohibited by anyone before.

Sometimes, the hack tests are added to the main tests early during the phase and people can see them so they're not even guaranteed to be private.

Also, I think the main purpose of having an open hack phase is to strengthen the tests by making anti-tests against actual participants' solutions, because it is easy to miss them when you don't have enough samples to work with. For this purpose the discussion on hacks shouldn't be discouraged.

Noted! Learn from mistakes. I just was referring to

will not communicate with other participants, share ideas of solutions and hacks

curly_braces

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 :(

yes, so basically a median from a subsequence is counted into sum only if the median is 1. So for having median of a subsequence of length k we need to have greater than or equal to (k+1)/2 number of 1s in the subsequence (since k is odd). For example if we have k=5 then we need to have at least three 1s in our subsequence. So for every array we try to find the number of ways of collecting at least (k+1)/2 1s and remaining 0s. For that we're using combinatorics...... For example, let's suppose n=10, k=5, and we have 7 ones and 3 zeroes. So, for having median 1 in subsequence of length 5 we need either 3 ones or 4 ones or all 5 ones in our subsequence. We'll sum up all 3 cases..... 1.) 3 ones out of 7 ---> 7C3, rest 2 elements in our subsequence must be zeroes, so 2 (k-ones) zeroes out of 3 --> 3C2, so this can be arranged in (7C3)*(3C2) ways. Similarly for the rest of the cases....

This basically gives the formula inside the for loop:-

int ans = 0;
for(int i=(k+1)/2;i<=min(k, number of ones);i++)
{
   ans = (ans + (number of ones)C(i) * (number of zeroes)C(k-i))%mod;
}

link to my submission

hinowbye

Hi, still very confused about this. Why does the median being 1 == there has to be at least k + 1 /2 1s? Can't it just be 1 in the middle, and 0s on both sides?

nevermind, we sort it first. Idk how i missed that

For finding median, we sort the subsequence and number at (k+1)/2th position is called median..

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

HeQuanSha5

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

rumike

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

Noluck_167

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?

you can precompute the log(log3()) array, and then use binary search to find the answer

tangdong_

Notice that 3^n gets large really fast (3^38 > 1e18). For each x (3^i <= x < 3^(i+1)), it takes i operation to make x zero

And then i just need to multiply it i.e i*(x-3^i)?

Yes, there are 3^(i+1)-3^(i)-1 of such numbers for each i, handle ones with l,r carefully

ctzm

https://codeforces.net/contest/1999/submission/274827875

you can see my solution on this: Link to submission

Summer_Wind

KyLen_Mou

Problem B is unreasonable

_regular_show

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.

perspective_

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

Because there are t sets of examples, and the total number is unlimited

u precomputed but then u still run from l to r

Got it.Thanks a lot

nskybytskyi

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.

Got it , thanks a lot

__reviver__

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

Sweet

G2 is just introduction to ternary search.

_Untrackable_

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

T×N complexity.

thnx :( . i hardly check size of T .would be remebered next time

ysyswd

I regret not studying interactive problems!

yash_yadav

why this code is giving idelness ?

thesmoker

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

dobrishk

task b literally sent me into a deep dark depression

Amaterasu_03

Can someone help which testcase I am missing

Kaleem_Raza_Syed

Well, the answer can only be 0, 2, 4. For any game, we have a selection of Round 1 and Round 2 for which we won, we can change the order to the rounds(Round 1 as the second round and vice versa). And ordering doesn't here doesn't change the winner.

Got it,Thanks

pink_floyd25

A simple solution :

Thanks bro

Itsadijmbt

The code I have for problem 1999E functions properly in ide (usaco,sublime), but it returns an incorrect answer in testcase 1. 1999E - Triple Operations

i get all correct answer for testcase 1 but the judge return Wrong Answer solution id:

SevenAlarm

When will we get the rating updates? Im kinda excited

schrodonger

hey all, for problem E, why does the following not work?

code

import math

def solve():
    l, r = map(int, input().split())

    ops = math.floor(math.log(l, 3)) + 1
    extras = math.floor(math.log(l, 3)) + 1
    
    for i in range(l + 1, r + 1):
        ops += math.floor(math.log(i, 3)) + 1

    print(ops + extras)

num_of_tests = int(input())
for _ in range(num_of_tests):
    solve()

the idea is :

first, i find the number of operations to obtain the first 0 from L
for all other numbers, i calculate the number of operations required to reach 0 as well
i sum the number of operations required for all other numbers + the additional operations due to making L into 0

thank you in advance !

-rynk2200

I never saw a question like E problem which fails for O(nt). Weird question

Sayan_001

Can somebody point out what is wrong?: 274922968

Nilesh_

If problem F was to count odd length subsequences having median as 1. What can be the solution?

Mahmoood

Is there a standard rating criteria for div 4 problems? I've noticed that the last div 4 contest you organized had the last task as a 2100-rated 2-SAT problem, while this one had the last two tasks being standard binary and ternary search problems. Both were fun btw so thanks :)

ankush_9302

help me in B ~~~~~~~~~ int Solve() { int a1,a2,b1,b2; cin>>a1>>a2>>b1>>b2; int ans=0; if(a1>b1){ if(a2>b2){ ans+=2; }else if(a2==b2){ ans+=1; } }else if(a1==b1){ if(a2>b2){ ans++; } } if(a1>b2 ){ if(a2>b1){ ans+=2; }else if(a2==b1){ ans+=1; } }else if(a1==b2){ if(a2>b1){ ans++; } }

return ans; } ~~~~~~~~~~~~~~~~ This is my solution for B problem and i am not able to understand why it is failing i have covered all the possible cases can anyone please help me!

AB2004

Can anyone help me out with my code for card game question in java

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

int wins = 0;

        if(a1>b1&&a2>b2)
        {
            wins+=2;
        }
        if(a1>b2 && a2>b1)
        {
            wins+=2;
        }
        System.out.println(wins);

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

YZHhegwb

IF a1==b1&&a2>b2 or a1==b1&&a2>b1 wins should+=2

It is inconceivable that the solution to my problem E was not successfully hacked.Obviously O (nT) solutions should be given to TLE.But in 37 hacks, no one succeeded.I feel like I will be given TLE in the final test due to excessive time

lakkshyag

Alternate solution to problem E, works in O(log3(r))

Basically make the smallest element (l) zero and then use that to make other elements zero as well. While we were making l zero (divide by 3k), we also multiplied some element by 3k and hence first we remove that. Then we just iterate over different powers of 3 (since they decide how many times we divide a number to make it zero) and find number of elements to divide by that number (the power tells us number of times this division is required)

Raghav_05

its more than 24 hours contest had been ended, still the result is not out yet. Why?

koushikad

Rating not updated

now it's updated, got my handle coloured!

pinakiz

In E,my submission fails at test case 1, where as it works well in my local machine as well as in online cpp shell. Can anyone let me know why it happened, Thanks.

using log function might be the case it create inconsistencies you could have used while loop to count same thing

aaravm

Can anyone help me in G2? I am getting wrong answer Integer 0 violates the range [1, 1000] (test case 1) in Test 1. I even manually wrote exceptions, that if my variable is 0, output 1 instead. Still, I do not know why I am getting output 0 https://codeforces.net/problemset/submission/1999/275154103

-Jarvis-

← Rev. 6 →

275163443

Why my this solution for E giving me TLE? Isn't this only O(N)?

Thanks :)

O(N) will give TLE as there is no limit across all test cases. So, O(N) will take t*(r-l)= 2*10^9. Think. you can do much better than O(N)

Understood ;) solved it using the precomputation. thanks!

why did i use RMQ on E? :skull:

R.i.n.Nabil

Thanks for the problem G2.

lmaoaadiez

275239437 why is this giving me TLE while i have the exact same logic as the solution

aritg

← Rev. 17 →

In this contest, the question was just about if else and due to which it matched with some one. How can you declare that I was cheating in that contest. Please look into this matter. Thanks mine : aritg/274372105 23CS02002/274399627

NotSoDumb

Got stuck at problem E :( found the logic but was trying to implement it in a complicated manner.

thanks for this wonderful contest and fast editorial.

red_army98

Can any one tell me what is the mistake in the code for G2 275301648

cseshamim47

can anybody please tell me why my G2 is giving TLE?

It does not give TLE if I run a loop for 6 times. Why r-l > 2 gives TLE? I know sometimes it can get stuck when l and r remains same. But with my logic, l and r will must change, hence the loop will end.

275323221

mamadam69.

getting the detail right on problem b was so easy yet frustrating

ganneo

I'm not sure if anyone else said this already but the title for the tutorial of 1999G2 isn't translated to english

inferno_7

4 weeks ago, # |

In G2, according to the solution, would there be 8 queries in worst case (binary search has 7 and the if condition of r-l=2 has 1 query) Can anyone explain?

Arya_Trivedi

"E. Triple Operations" my code is giving different answer on codeforces compiler and vs code in my machine. I also checked on online c++ compiler it is showing exactly same as vs code output but codeforces is giving wrong answer. Please Help.!

Code: ~~~~~

include<bits/stdc++.h>

using namespace std;

define endl "\n"

_cjcj

can anyone help me with Triple Operations problem: https://codeforces.net/contest/1999/submission/276881314

dino_merlin

3 weeks ago, # |

Alternative solution for A, write an if statement for each of the 90 possible inputs. This is very efficient because you don't use a for loop or any other costly operation such as division or modulo. My code: https://codeforces.net/contest/1999/submission/277148166

tbquan08hanoi

2 weeks ago, # |

knew G2 is ternary search but can't implement :skull:

flamestorm's blog

define ll long long

include<bits/stdc++.h>

define endl "\n"

define int long long