Thanks for participating. We hope you enjoyed the contest!
Idea: flamestorm
Tutorial
Tutorial is loading...
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();
}
Idea: SlavicG
Tutorial
Tutorial is loading...
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)
Idea: SlavicG
Tutorial
Tutorial is loading...
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()
Idea: SlavicG
Tutorial
Tutorial is loading...
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";
}
}
Idea: flamestorm
Tutorial
Tutorial is loading...
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();
}
Idea: mesanu
Tutorial
Tutorial is loading...
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";
}
}
Idea: flamestorm
Tutorial
Tutorial is loading...
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();
}
Idea: flamestorm
Tutorial
Tutorial is loading...
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();
}
you are so quickly!
好快
I will kill myself over B. UPD: Found my error
me too
us moment
real
me but i found it after one hour :(
you and me both brother
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
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.
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?
try using c++20 and then you will probably get wa on test2
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
probably rounding errors with log. safer not to use log when you dont have to
Try not using log
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
Bro your code is correct only with the first case
your code does not work if x1==y1&&x2==y2.
for example 2 2 3 3.
you should write this part separately in your code.
my idea in D was right but i didn't code it
same
can someone help me with what's wrong with my solution of B?
...
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).
you forgot to consider the cases like where a1>b1 && a2>=b2 This is also the win case
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?
I think you forgot to mod at factorial. And you should add mod inverse too :D
I’ll research on this, thanks!
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
Also, (2,a] should be [2, a]
Thanks, it'll be fixed soon.
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
check this testcase
1
243 244
l<r
Sorry...I have corrected it
i swear to god B took more time than A,C,D,E
Should've been able to solve E. But we move
In the code for B, since you are using Python,
ans++
should give syntax error. Just a minor detail! Thanks for the quick editorial:DNeed 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.
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
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 love E, F, G2. Brilliant idea!!!
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.
For problem E why is this O(n) code getting TLE?(https://codeforces.com/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
The problem doesn't guarantee the sum of $$$r-l$$$ is below $$$2\times 10^5$$$
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
8 1 1 1 doesn't work. Should be 4 but your program outputs 2.
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.
In java, adding a letter to the end of a string is an O(n) operation, as it creates an entirely new string.
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?
'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.
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)
I got another simpler setup approach to E, perhaps.
We will make an array of the exponentiation of 3, like lt[0] = 1, lt[1] = 3, lt[2] = 9, lt[3] = 27, ..., lt[15] = 3^15. (Because r <= 2 . 10 ^ 5)
We will make a prefix sum before making the testcase. For each i, call j is the smallest number satisfying a[i] >= lt[j], (1 <= j <= 15).
For example, a[1] = 1, a[2] = 1, a[3] = 2, a[4] = 2, ..., a[8] = 2, a[9] = 3, a[10] = 3, ... After that we will make a prefix sum of a[] called f[]. For instance, f[1] = 1, f[2] = f[1] + a[2] = 2, f[3] = f[2] + a[3] = 4, ...
For each n, m in the testcase, to find the minimum operation needed, while n, m is typed from the keyboard, the answer will be pre[m] — pre[n-1].
Then plus the a[n], as we have to make n become 0 to minimize the operations, the final thing to do is f[m] — f[n-1] + a[n].
Link: My sub
Can anyone help me find out the bug in my code for problem D? It passed all testcases, but it got hacked, and I don't know how to find the specific testcase in which it failed at.
https://codeforces.com/contest/1999/submission/274881476
Thanks in advance! If this is against the rules of the contest, please let me know so I can delete this comment.
Consider
aaaaaaaaaaaaaaaaaaaaab
andaaaaaaaaaaac
. Your code will compare $$$O(n^2)$$$ times in this case.Thanks!
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.
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 answerint log(int n){ return 1 + (int) Math.floor(Math.log(n) / Math.log(3)); }
**Can anyone tell me , why its giving Tle , or is it wrong ** ~~~~~ int main() { // startTime = clock(); ios_base::sync_with_stdio(false); cin.tie(NULL);
ifndef ONLINE_JUDGE
endif
} ~~~~~
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
the compiler isnt that stupid, it can optimize out obviously unnecessary parts
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.
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 :(