### flamestorm's blog

By flamestorm, 5 weeks ago,

Thanks for participating. We hope you enjoyed the contest!

1999A - A+B Again?

Idea: flamestorm

Tutorial
Solution

1999B - Card Game

Idea: SlavicG

Tutorial
Solution

1999C - Showering

Idea: SlavicG

Tutorial
Solution

1999D - Slavic's Exam

Idea: SlavicG

Tutorial
Solution

1999E - Triple Operations

Idea: flamestorm

Tutorial
Solution

1999F - Expected Median

Idea: mesanu

Tutorial
Solution

1999G1 - Ruler (easy version)

Idea: flamestorm

Tutorial
Solution

1999G2 - Ruler (hard version)

Idea: flamestorm

Tutorial
Solution
• +77

 » 5 weeks ago, # |   +1 you are so quickly!
 » 5 weeks ago, # | ← Rev. 4 →   -22 so fast!
•  » » 5 weeks ago, # ^ |   0 use english, plz.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 ok!
 » 5 weeks ago, # | ← Rev. 2 →   +2 I will kill myself over B. UPD: Found my error
•  » » 5 weeks ago, # ^ |   0 me too
•  » » 5 weeks ago, # ^ |   0 same :___
•  » » 5 weeks ago, # ^ |   0 us moment
•  » » 5 weeks ago, # ^ |   0 real
•  » » 5 weeks ago, # ^ |   0 me but i found it after one hour :(
•  » » 5 weeks ago, # ^ |   0 you and me both brother
•  » » 5 weeks ago, # ^ |   0 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
•  » » » 5 weeks ago, # ^ |   0 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.
•  » » » » 5 weeks ago, # ^ |   0 thanks found my mistake
•  » » » 5 weeks ago, # ^ |   0 You may check this out: SolutionEven 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!
•  » » » 5 weeks ago, # ^ |   0 哪道题？
•  » » » 5 weeks ago, # ^ |   0 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
•  » » 5 weeks ago, # ^ |   0 i got the answer from the notes section for B.
 » 5 weeks ago, # |   +1 I spent lot's of time considering 1:0 situations in problem B.
•  » » 5 weeks ago, # ^ |   0 hh我也是
 » 5 weeks ago, # |   0 fast editorial
 » 5 weeks ago, # |   +25 Clarification: SlavicG and I actually are best friends, he's just playing hard to get.
 » 5 weeks ago, # |   0 In problem E, my code was giving me expected/correct output in my local machine, but is giving wrong output during codeforce's testing 274941437Could any one tell why is that?
•  » » 5 weeks ago, # ^ |   0 try using c++20 and then you will probably get wa on test2
•  » » 5 weeks ago, # ^ |   0 Maybe different machine use different implement causing the different output ? Better not use log in this problem I guess, I stuck on that too.
•  » » » 5 weeks ago, # ^ |   0 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
•  » » 5 weeks ago, # ^ |   0 probably rounding errors with log. safer not to use log when you dont have to
•  » » 5 weeks ago, # ^ |   0 Try not using log
 » 5 weeks ago, # |   0 Can't believe how much bad this one went
 » 5 weeks ago, # |   +4 G1<
•  » » 5 weeks ago, # ^ |   0 G1
 » 5 weeks ago, # |   -6 can anyone help me, for which test case my code didn't work //this code #include 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<=y2){ cout<<4<
•  » » 5 weeks ago, # ^ |   0 Bro your code is correct only with the first case
•  » » » 5 weeks ago, # ^ |   0 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
•  » » 5 weeks ago, # ^ | ← Rev. 4 →   0 you should add else if(x2
•  » » » 5 weeks ago, # ^ |   0 but bro the example you take 2 2 3 3,x1 = 2 and y1 = 3x2 = 2 an d y2 = 3the output for above example is 0 and my code gives the 0 as output
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Code#include 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.
•  » » 8 days ago, # ^ | ← Rev. 2 →   0 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;
 » 5 weeks ago, # |   0 my idea in D was right but i didn't code it
•  » » 5 weeks ago, # ^ |   0 same
•  » » 5 weeks ago, # ^ |   0 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.
•  » » 5 weeks ago, # ^ |   0 double point is okay
 » 5 weeks ago, # |   0 can someone help me with what's wrong with my solution of B? Spoiler... #include 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<
•  » » 5 weeks ago, # ^ |   0 you forgot about when Suneet wins one round and draws other...The equalities
•  » » » 5 weeks ago, # ^ |   0 oh righttt, thanks!
•  » » » 5 weeks ago, # ^ |   0 Are you talking about this case — 1 8 1 7
•  » » » » 5 weeks ago, # ^ |   0 yes , here Suneet can win in two ways (1,1) ,(8,7) and (8,7) ,(1,1).
•  » » 5 weeks ago, # ^ |   0 you forgot to consider the cases like where a1>b1 && a2>=b2 This is also the win case
 » 5 weeks ago, # |   0 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 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 void mycout(const Args&... args) { #if debug ((cout << args << ", "), ...); // Fold expression cout << endl; #endif } unordered_map 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 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; } 
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   0 I think you forgot to mod at factorial. And you should add mod inverse too :D
•  » » » 5 weeks ago, # ^ |   0 I’ll research on this, thanks!
 » 5 weeks ago, # |   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.
•  » » 5 weeks ago, # ^ |   0 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.
•  » » » 5 weeks ago, # ^ |   0 because r <= 2e5, you can do the array f[n] = ceil(log(n)), then f[i] = f[i/3] + 1, with f[0] = 0
 » 5 weeks ago, # | ← Rev. 3 →   0 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
•  » » 5 weeks ago, # ^ |   0 Also, (2,a] should be [2, a]
•  » » » 5 weeks ago, # ^ |   0 Thanks, it'll be fixed soon.
 » 5 weeks ago, # |   0 I think G1 and G2 were much easier than E and F... the most basic binary search in both versions
•  » » 5 weeks ago, # ^ |   0 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
•  » » » 5 weeks ago, # ^ |   0 I suppose you're right. It's just that to me F-like problems (with combinatorics etc.) are very difficult
 » 5 weeks ago, # |   0 Why my code 274894324 is getting WA on E? I did all exactly as in editorial
•  » » 5 weeks ago, # ^ | ← Rev. 5 →   0 check this testcase1243 244
•  » » » 5 weeks ago, # ^ |   0 l
•  » » » » 5 weeks ago, # ^ |   0 Sorry...I have corrected it
•  » » » » » 5 weeks ago, # ^ |   0 noproblem :D
•  » » 5 weeks ago, # ^ |   0 try 1, 999
•  » » 5 weeks ago, # ^ |   0 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.
 » 5 weeks ago, # |   0 i swear to god B took more time than A,C,D,E
 » 5 weeks ago, # |   0 Should've been able to solve E. But we move
 » 5 weeks ago, # |   0 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)
 » 5 weeks ago, # | ← Rev. 2 →   +4 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 0and so on.I think this could be optimal.
•  » » 5 weeks ago, # ^ |   0 This is exactly the idea I used in my solution 274869114
•  » » » 5 weeks ago, # ^ |   0 I was not left with enough time since stucked in correcting B :(Btw your implementation is good.
•  » » » » 5 weeks ago, # ^ |   0 Thanks! But I couldn't solve B at all, so sad
•  » » 5 weeks ago, # ^ |   0 Yes, this can reach $O(\log\log n)$ complexity and also feasible to $r\le 10^{18}$.
•  » » » 5 weeks ago, # ^ |   0 How to precompute in log(log(n)) complexity?
•  » » » » 5 weeks ago, # ^ |   0 I mean O(loglogn) for each query
•  » » 5 weeks ago, # ^ |   0 This is what I did too, although I ended up writing extremely messy code.
•  » » 5 weeks ago, # ^ |   0 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.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 In what best complexity it can be done?
•  » » 5 weeks ago, # ^ |   0 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
 » 5 weeks ago, # |   0 I love E, F, G2. Brilliant idea!!!
 » 5 weeks ago, # |   0 Can anyone tell me how to test our code for an interactive problem?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 5 weeks ago, # ^ |   0 Thanks for the reply!!But I did not quite understand it. Would be great if I could find a C++ solution for that.
 » 5 weeks ago, # | ← Rev. 2 →   0 For problem E why is this O(n) code getting TLE?(https://mirror.codeforces.com/contest/1999/submission/274854161)
•  » » 5 weeks ago, # ^ |   0 i dont think O(n) solutions passed, they used O(n) to precompute and then O(1) for each test case
•  » » 5 weeks ago, # ^ |   0 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
•  » » » 5 weeks ago, # ^ |   0 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?
•  » » » » 5 weeks ago, # ^ |   0 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.)
•  » » 5 weeks ago, # ^ |   0 The problem doesn't guarantee the sum of $r-l$ is below $2\times 10^5$
 » 5 weeks ago, # | ← Rev. 5 →   0 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 sameSo, 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
 » 5 weeks ago, # |   0 got humbled :'(
•  » » 5 weeks ago, # ^ |   0 Real shite
 » 5 weeks ago, # |   +1 I'm so used to "Sum of n over all cases doesn't exceed $2 \times 10^5$ " :)
 » 5 weeks ago, # |   0 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.
 » 5 weeks ago, # | ← Rev. 2 →   0 In which test case my submission 274924034 for E is failing.
 » 5 weeks ago, # |   0 Can some one tell the failing testcase for problem B for this code #include 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<
•  » » 5 weeks ago, # ^ |   0 8 1 1 1 doesn't work. Should be 4 but your program outputs 2.
 » 5 weeks ago, # |   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; } 
 » 5 weeks ago, # |   0 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.
•  » » 5 weeks ago, # ^ |   0 In java, adding a letter to the end of a string is an O(n) operation, as it creates an entirely new string.
 » 5 weeks ago, # |   0 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 :(
 » 5 weeks ago, # |   0 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?
•  » » 5 weeks ago, # ^ |   0 '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.
•  » » » 5 weeks ago, # ^ |   0 ahh i get that, thanks dude!
•  » » 5 weeks ago, # ^ |   0 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)
 » 5 weeks ago, # | ← Rev. 4 →   0 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
•  » » 5 weeks ago, # ^ |   0 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
 » 5 weeks ago, # | ← Rev. 2 →   0 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://mirror.codeforces.com/contest/1999/submission/274881476Thanks in advance! If this is against the rules of the contest, please let me know so I can delete this comment.
•  » » 5 weeks ago, # ^ |   0 Consider aaaaaaaaaaaaaaaaaaaaab and aaaaaaaaaaac. Your code will compare $O(n^2)$ times in this case.
•  » » » 5 weeks ago, # ^ |   0 Thanks!
 » 5 weeks ago, # |   0 You know for the Showering question how did you not get a memory exceeded error?? #include using namespace std; int main(){ cin.tie(nullptr)->sync_with_stdio(false); int t,n,s,m; cin >> t; int start, end; vector 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 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.
•  » » 5 weeks ago, # ^ |   0 The interval can be as large as $10^9$.
•  » » » 5 weeks ago, # ^ |   0 Oh i see, thank you so much.
 » 5 weeks ago, # | ← Rev. 2 →   0 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 Spoilerint log(int n){ return 1 + (int) Math.floor(Math.log(n) / Math.log(3)); }
•  » » 5 weeks ago, # ^ |   0 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://mirror.codeforces.com/blog/entry/78161
•  » » 5 weeks ago, # ^ |   0 I have the same error and take two hours to fix :))))) you can rewrite the log func with long long parameter.
 » 5 weeks ago, # |   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.
•  » » 5 weeks ago, # ^ |   0 Can this solution pass higher constraints? Link
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +1 you are repeating what he said
 » 5 weeks ago, # |   0 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
•  » » 5 weeks ago, # ^ |   0 the compiler isnt that stupid, it can optimize out obviously unnecessary parts
•  » » 5 weeks ago, # ^ |   -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.
•  » » » 5 weeks ago, # ^ |   +4 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.
•  » » » » 5 weeks ago, # ^ |   -10 The hacking phase is still running, Posting your hack is technically the same as sharing your solution during the contest.
•  » » » » 5 weeks ago, # ^ |   +3 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.
•  » » » » » 5 weeks ago, # ^ |   0 But now that I see it, that specific solution is just compiler-optimized, and it didn't actually run the loop 2e9 times.
•  » » » 5 weeks ago, # ^ | ← Rev. 4 →   +3 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.
•  » » » » 5 weeks ago, # ^ |   +3 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.
•  » » » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 Noted! Learn from mistakes. I just was referring to... will not communicate with other participants, share ideas of solutions and hacks ...
 » 5 weeks ago, # |   +5 Harder Version of F if anyone wants to try. Sum of Medians
 » 5 weeks ago, # |   0 Can any one give me more explain for problem F , i did not Understand tut :(
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 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:- Codeint 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
•  » » » 5 weeks ago, # ^ |   0 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?
•  » » » » 5 weeks ago, # ^ |   0 nevermind, we sort it first. Idk how i missed that
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 For finding median, we sort the subsequence and number at (k+1)/2th position is called median..
 » 5 weeks ago, # |   0 I solved E without DP, iteratively and a bit of maths.. My Solution
 » 5 weeks ago, # |   0 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
 » 5 weeks ago, # |   0 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
 » 5 weeks ago, # |   0 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?
•  » » 5 weeks ago, # ^ |   0 you can precompute the log(log3()) array, and then use binary search to find the answer
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 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
•  » » » 5 weeks ago, # ^ |   0 And then i just need to multiply it i.e i*(x-3^i)?
•  » » » » 5 weeks ago, # ^ |   0 Yes, there are 3^(i+1)-3^(i)-1 of such numbers for each i, handle ones with l,r carefully
•  » » 5 weeks ago, # ^ |   0
•  » » 5 weeks ago, # ^ |   0 you can see my solution on this: Link to submission
•  » » 5 weeks ago, # ^ |   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<
 » 5 weeks ago, # |   0 Problem B is unreasonable
 » 5 weeks ago, # |   0 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.
 » 5 weeks ago, # |   0 Can anyone let me know why this gives TLE.Even the solution code precomputes till 2e5.275010837
•  » » 5 weeks ago, # ^ |   0 Because there are t sets of examples, and the total number is unlimited
•  » » 5 weeks ago, # ^ |   0 u precomputed but then u still run from l to r
•  » » » 5 weeks ago, # ^ |   0 Got it.Thanks a lot
 » 5 weeks ago, # |   +8 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.
•  » » 5 weeks ago, # ^ |   0 Got it , thanks a lot
»
5 weeks ago, # |
Rev. 2   0

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

 » 5 weeks ago, # |   +2 G2 is just introduction to ternary search.
 » 5 weeks ago, # |   0 can anyone tell why my e code of o(n) is giving tle ? :- https://mirror.codeforces.com/contest/1999/submission/274942317
•  » » 5 weeks ago, # ^ |   0 T×N complexity.
•  » » » 5 weeks ago, # ^ |   0 thnx :( . i hardly check size of T .would be remebered next time
 » 5 weeks ago, # |   0 I regret not studying interactive problems!
 » 5 weeks ago, # |   0 #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef long double ld; typedef std::vector vi; typedef std::vector vb; typedef std::vector vs; typedef std::vector vd; typedef std::vector vll; typedef std::vector > vvi; typedef vector vvll; typedef std::vector > vpi; typedef vector vvpi; typedef std::pair pi; typedef std::pair pll; typedef std::vector 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 ?
 » 5 weeks ago, # |   0 can anyone help me with this code of f? is this correct approach or not? #include #include using namespace std; #define int long long int int f(int i,int ones,int zeros,vector&v,vector>>&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; vectorv; for(int i=0;i>a; v.push_back(a); if(a==1)one++; else zero++; } int m=1e9+7; vector>>dp(n+2,vector>(one+2,vector(zero+2,-1))); int ans=0; ans=f(0,0,0,v,dp,k,m)%m; cout<
 » 5 weeks ago, # |   0 task b literally sent me into a deep dark depression
 » 5 weeks ago, # |   0 #include 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<c&&b>d)||(a>d&&b>c)){ cout<<2<c&&b==d)||(a>d&&b==c)||(b>c&&a==d)||(b>d&&a==c)){ cout<<1<>t; while(t--){ solve(); } } Can someone help which testcase I am missing
•  » » 5 weeks ago, # ^ |   0 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.
•  » » » 5 weeks ago, # ^ |   0 Got it,Thanks
•  » » » » 5 weeks ago, # ^ |   0 A simple solution : 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<>t; while(t--){ solve(); } return 0; } 
•  » » » » » 5 weeks ago, # ^ |   0 Thanks bro
 » 5 weeks ago, # |   0 The code I have for problem 1999E functions properly in ide (usaco,sublime), but it returns an incorrect answer in testcase 1. 1999E - Triple Operationsi get all correct answer for testcase 1 but the judge return Wrong Answer solution id:
 » 5 weeks ago, # |   0 When will we get the rating updates? Im kinda excited
 » 5 weeks ago, # | ← Rev. 4 →   0 hey all, for problem E, why does the following not work? codeimport 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 !
 » 5 weeks ago, # |   0 I never saw a question like E problem which fails for O(nt). Weird question
 » 5 weeks ago, # |   0 Can somebody point out what is wrong?: 274922968
 » 5 weeks ago, # |   0 If problem F was to count odd length subsequences having median as 1. What can be the solution?
 » 5 weeks ago, # |   0 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 :)
 » 5 weeks ago, # |   0 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!
 » 5 weeks ago, # | ← Rev. 2 →   0 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);~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
•  » » 5 weeks ago, # ^ |   0 IF a1==b1&&a2>b2 or a1==b1&&a2>b1 wins should+=2
 » 5 weeks ago, # |   0 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
 » 5 weeks ago, # |   0 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) void tripleOperations(int l, int r) {  vector 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<
 » 5 weeks ago, # |   0 its more than 24 hours contest had been ended, still the result is not out yet. Why?
 » 5 weeks ago, # |   0 Rating not updated
•  » » 5 weeks ago, # ^ |   0 now it's updated, got my handle coloured!
 » 5 weeks ago, # |   0 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.
•  » » 5 weeks ago, # ^ |   0 using log function might be the case it create inconsistencies you could have used while loop to count same thing
 » 5 weeks ago, # |   0 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://mirror.codeforces.com/problemset/submission/1999/275154103
 » 5 weeks ago, # | ← Rev. 6 →   0 275163443Why my this solution for E giving me TLE? Isn't this only O(N)?Thanks :)
•  » » 5 weeks ago, # ^ |   0 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)
•  » » » 5 weeks ago, # ^ |   0 Understood ;) solved it using the precomputation. thanks!
 » 5 weeks ago, # |   +1 why did i use RMQ on E? :skull:
 » 5 weeks ago, # |   0 Thanks for the problem G2.
 » 5 weeks ago, # |   0 275239437 why is this giving me TLE while i have the exact same logic as the solution
 » 5 weeks ago, # | ← Rev. 17 →   0 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
 » 5 weeks ago, # |   0 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.
 » 5 weeks ago, # | ← Rev. 2 →   0 Can any one tell me what is the mistake in the code for G2 275301648
 » 5 weeks ago, # |   0 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
 » 5 weeks ago, # |   0 getting the detail right on problem b was so easy yet frustrating
 » 4 weeks ago, # |   0 I'm not sure if anyone else said this already but the title for the tutorial of 1999G2 isn't translated to english
 » 4 weeks ago, # |   0 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?
»
4 weeks ago, # |
Rev. 3   0

"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 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.

 » 4 weeks ago, # |   0 can anyone help me with Triple Operations problem: https://mirror.codeforces.com/contest/1999/submission/276881314
 » 3 weeks ago, # |   0 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://mirror.codeforces.com/contest/1999/submission/277148166
 » 2 weeks ago, # |   0 knew G2 is ternary search but can't implement :skull: