What is the pattern of Tim's answer sheet that can give him maximum score?
Let's say there are $$$n$$$ problems take $$$A$$$ as the answer, therefore he can only get $$$n$$$ points with the answer $$$A$$$. The same is correct for $$$B$$$, $$$C$$$ and $$$D$$$. Therefore, the maximum score can be achieved is $$$min(n, A) + min(n, B) + min(n, C) + min(n, D)$$$.
Time complexity: $$$O(4n)$$$
t = int(input())
for _ in range(t):
n = int(input())
s = input()
print(sum(min(n, s.count(c)) for c in "ABCD"))
Find a way to make all the elements even. Then odd.
In the worst case, the number of operations required is the number of even elements + 1. Why?
First, if all elements already have the same parity, we don't need to do perform any operation.
Next, if the array contains both $$$even$$$ and $$$odd$$$ numbers. In this case, it is impossible to convert all elements to $$$even$$$ numbers.
If we apply an operation on:
- two $$$odd$$$ elements, one of them remains $$$odd$$$.
- two elements of distinct parities, one of them is replaced with their sum, which is an $$$odd$$$ number.
This implies even if we want to change an $$$odd$$$ element to $$$even$$$ number, it fails in both ways possible.
So we just want to convert all of them to $$$odd$$$ numbers. Now come the greedy part:
- $$$even + even = even \longrightarrow$$$ it doesn't reduce the number of $$$even$$$ elements, so skip it.
- $$$odd + odd = even \longrightarrow$$$ this creates another $$$even$$$ number, indeed very awful.
- $$$even + odd = odd \longrightarrow$$$ this is great, but only if the sum replaces the $$$even$$$ one (which means $$$even < odd$$$).
Let's find the largest $$$odd$$$ element and call it $$$s$$$. Then traverse each $$$even$$$ elements $$$t$$$ in non-decreasing order and apply an operation on $$$s$$$ and $$$t$$$:
- If $$$t < s$$$, $$$s+t$$$ becomes largest odd number. Thus, we set $$$s := s+t$$$. This reduce the number of even element by $$$1$$$.
- If $$$t > s$$$, before we do this operation, we need to do another on $$$s$$$ and the largest even element to make $$$s$$$ the largest in the array. Note that this case only happens at most once.
As a result, the answer is the number of even elements (plus $$$1$$$ if the second case occurs).
Time complexity: $$$O(n\log n)$$$.
t = int(input())
for _ in range(t):
n = int(input())
a = list(map(int, input().split()))
s = -1
v = []
for x in a:
if x%2 == 0:
v.append(x)
elif x > s:
s = x
v.sort()
if s == -1 or v == []:
print(0)
continue
ans = len(v)
for t in v:
if t < s:
s += t
else:
ans += 1
break
print(ans)
Try to find the segments of moments when a light is on.
Select this segment from each light. The answer should be the intersection of all of them.
As soon as a chip is installed, it changes the light's status every $$$k$$$ minutes.
Let's first list the segments of the moments when a light is on if we install a chip at moment $$$x$$$:
- $$$x\rightarrow x+k-1$$$
- $$$x+2k\rightarrow x+3k-1$$$
- $$$x+4k\rightarrow x+5k-1$$$
- $$$\dots$$$
Have you seen the pattern yet? Apparently each segment in the list (except the first one) is actually the segment before it, shifted by $$$2k$$$ minutes. This also means that if we divide by $$$2k$$$ and take the remainder at both ends of each segment, all these segments become equal. With that, let's call $$$(a_i\bmod 2k, (a_i+k-1)\bmod 2k)$$$ the segment of the $$$i$$$-th chip.
Our problem is thus simplified to: find the smallest integer $$$s$$$ such that:
- $$$max(a) \le s$$$
- $$$s\bmod 2k$$$ appears in every segments of all chips.
In order to satisfy the first condition, it seems if we figure out some $$$r = s\bmod 2k$$$ that satisfy the second condition, we may come up with:
Next, in order for a segment to contain $$$r$$$, this inequality must be satisfied: $$$r-k+1 \le a_i \le r \pmod{2k}$$$. This is because a light is on only for at most $$$k$$$ minutes (before it gets turned off), so it must come not long before the moment $$$r$$$. Let's call $$$d[z]$$$ the number of chips that has $$$a_i \equiv z \pmod{2k}$$$, then in order for all lights to be on at moment $$$s$$$, the condition is:
This idea can be implemented using two-pointer technique, that traverse all $$$r$$$ from $$$0$$$ to $$$2k-1$$$. As there can be many possible values of $$$r$$$, we only take one that produces $$$s$$$ with minimum value. Be careful when handling signs in problems with modules to avoid unnecessary errors.
Time complexity: $$$O(n)$$$.
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, k, d[2*N];
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
while (t--) {
cin >> n >> k;
int mx = -1;
fill(d, d + 2*k, 0);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
assert(x >= 1);
d[x % (2*k)]++;
mx = max(mx, x);
}
int cnt = 0;
int ans = INT_MAX;
for (int i = 0; i <= k - 2; i++) {
cnt += d[i];
}
for (int l = 0, r = k-1; l < 2*k; l++, r++) {
if (r >= 2*k) r -= 2*k;
if (cnt += d[r]; cnt == n) {
int wait = (r-mx) % (2*k);
if (wait < 0) wait += 2*k;
ans = min(ans, mx + wait);
}
cnt -= d[l];
}
if (ans == INT_MAX) {
ans = -1;
}
cout << ans << '\n';
}
}
Is there any method to calculate median without sorting?
Is there any relationship between the original array with the final array?
Note: in order to explain this solution easier, we'll suppose all arrays are 0-indexed.
If $$$n \le k$$$, we don't have to remove any segment since the statement only tell us to do it while the length of $$$a$$$ is greater than $$$k$$$. That way, the median of $$$a$$$ is fixed. Let's find a way to calculate this value without sorting the array.
Given an integer $$$x$$$. If $$$x$$$ is less than or equal to the median of $$$a$$$, then suppose we sort $$$a$$$ in increasing order, $$$x$$$ is somewhat to the left of $$$med(a)$$$. That means the number of elements greater than or equal to $$$x$$$ is more than the number of elements less than $$$x$$$. Using this observation, we can create another array $$$b$$$ of the same size as $$$a$$$, such that $$$b[i] = 1$$$ if $$$x \ge a[i]$$$, otherwise $$$b[i] = -1$$$. The trick here is if $$$sum(b) > 0$$$, then the condition $$$x \le med(a)$$$ is satisfied. Using this trick, we can easily binary search the median of $$$a$$$ by fixing value of $$$x$$$, checking if $$$sum(b) > 0$$$ and adjusting the value range of $$$med(a)$$$.
How about $$$n>k$$$. In this case, we'll keep using the same strategy as above. That is: fix the value of $$$x$$$, find a way to delete segments of $$$a$$$ so that the array $$$b$$$ has largest sum, check if that sum is greater than $$$0$$$ and adjust the value range of the answer.
Note that each time we delete a segment, the size of $$$a$$$ is reduced by $$$k$$$. We do that until $$$|a|\le k$$$. Let's call the final array $$$a$$$ after deleting segments $$$a'$$$. After some calculation, we come up with $$$|a'| = ((n-1)\bmod k) + 1$$$.
Also, it can be seen that the elements $$$a'[0], \dots, a'[m-1]$$$ (where $$$m = |a'|$$$) always originate from the elements $$$a[i_0], \dots, a[i_{m-1}]$$$ such that $$$i_0\equiv 0\pmod k, i_1\equiv 1\pmod k, \dots, i_{m-1}\equiv m-1\pmod k$$$.
Suppose we want to delete the segment $$$[i, i+k-1]$$$ from $$$a$$$. This operation shift all the elements from the right by $$$k$$$ units to the left, which means the indexes are subtracted by $$$k$$$ units. But if we only care about the indexes modulo $$$k$$$ before and after deleting the segments, shifting $$$k$$$ units doesn't change their modulos at all.
With all above observations, we come up with the following DP formula to find the optimal segment deletions:
- $$$dp[0] = b[0]$$$
- If $$$i\equiv 0\pmod k$$$ and $$$i > 0$$$, then $$$dp[i] = max(dp[i-k], b[i])$$$
- Otherwise $$$dp[i] = dp[i-1] + b[i]$$$. If $$$i > k$$$ then maximize $$$dp[i]$$$ by $$$dp[i-k]$$$
Then, the maximum sum of $$$b$$$ in the optimal deletions equals to $$$dp[n-1]$$$.
Time complexity: $$$O(n\log max(a))$$$.
#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
int n, k, a[N];
int dp[N], b[N];
bool check(int med) {
for (int i = 0; i < n; i++) {
if (a[i] >= med) {
b[i] = 1;
} else {
b[i] = -1;
}
}
dp[0] = b[0];
for (int i = 1; i < n; i++) {
if (i%k == 0) {
dp[i] = max(dp[i-k], b[i]);
} else {
dp[i] = dp[i-1] + b[i];
if (i > k) {
dp[i] = max(dp[i], dp[i-k]);
}
}
}
return dp[n-1] > 0;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t; cin >> t;
while (t--) {
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int lo = 1, hi = 1e9;
while (lo <= hi) {
int mid = lo + hi >> 1;
if (check(mid)) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
cout << hi << '\n';
}
}
Try applying an operation on the same row twice. Does it change the matrix significantly?
Now apply operations on two different rows. Does the second row (that the operation is applied) look familiar?
First, let's extend the original matrix by one unit in rows and columns (which means there's an additional $$$(n+1)$$$-th row and $$$(m+1)$$$-th column). Then, assign $$$a[i][m+1] = f(i)$$$ (xorsum of the $$$i$$$-th row) and $$$a[n+1][j] = g(j)$$$ (xorsum of the $$$j$$$-th column). That way, the operation is simplified as follows:
- The first-type operation becomes swapping the $$$i$$$-th row with the $$$(n+1)$$$-th row.
- The second-type operation becomes swapping the $$$j$$$-th column with the $$$(m+1)$$$-th column.
As we know, the first-type operation is to select any row $$$i$$$, then assign $$$a[i][j] = g(j)$$$ for all index $$$j$$$. But after the matrix extension, the value of $$$g(j)$$$ is also $$$a[n+1][j]$$$ so it means replacing the $$$i$$$-th row with the $$$(n+1)$$$-th one.
But we also need to care about the new value of $$$g(j)$$$ for future operations right? Surprisingly, the new value of $$$g(j)$$$ is nowhere strange, just the old value of element $$$a[i][j]$$$ being replaced right before! This takes advantage of the fact that if we perform the operation on the same row twice, the row become unchanged. After swapping two rows, the value of $$$a[n+1][j]$$$ then again become $$$g(j)$$$ of the new matrix.
The change of the second-type operation can be proven the same way.
That way, the matrix can be constructed by the permutation of rows, and the permutation of columns (as we can swap them however we want). After all operations, let's say the rows ordered from the top to the bottom are $$$r_1, r_2, \dots, r_{n+1}$$$. Similarly, the columns ordered from the left to the right are $$$c_1, c_2, \dots, c_{m+1}$$$.
Next thing to consider is: $$$\text{beauty(a)} = R + C$$$ — the beauty of the matrix, where:
- $$$R = \sum\limits_{i=1}^n \sum\limits_{j=2}^m \big|a[i][j] - a[i][j-1]\big|$$$ — sum of adjacent cells on the same row.
- $$$C = \sum\limits_{j=1}^m \sum\limits_{i=2}^n \big|a[i][j] - a[i-1][j]\big|$$$ — sum of adjacent cells on the same column.
Note that we include neither the $$$(n+1)$$$-th row nor the $$$(m+1)$$$-th column when calculating $$$R$$$ and $$$C$$$. That being said, after all operations, the $$$r_{n+1}$$$-th row and the $$$c_{m+1}$$$-th column is excluded and do not make any effect in further calculations anymore.
After that, we calculate two arrays:
- $$$dr[u][v] = $$$ sum of differences between $$$u$$$-th row and $$$v$$$-th row.
- $$$dc[u][v] = $$$ sum of differences between $$$u$$$-th column and $$$v$$$-th column.
Then, we'll rewrite the formulas of $$$R$$$ and $$$C$$$ as: $$$R = \sum\limits_{i=2}^n dr[r_{i-1}][r_i]$$$ and $$$C = \sum\limits_{i=2}^m dc[c_{i-1}][c_i]$$$. From now on, calculating $$$R$$$ and $$$C$$$ is as easy as solving the Travelling Salesman Problem: finding a good permutation $$$r_1, \dots, r_n$$$ that produces the minimum $$$R$$$, and a good permutation $$$c_1, \dots, c_n$$$ that produces the minimum $$$C$$$. At the end, by summing $$$R + C$$$ we got the $$$\text{beauty}$$$ for a fixed excluded row and column for the matrix $$$a$$$.
Time complexity: $$$O((n+1)(m+1)^22^{m+1} + (m+1)(n+1)^22^{n+1})$$$, or $$$O(n^32^n)$$$.
#include <bits/stdc++.h>
using namespace std;
const int N = 16;
int n, m;
int a[N][N];
int fr[N][N], fc[N][N];
int w[N][N], dp[N][1<<N];
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
while (t--) {
cin >> n >> m;
for (int i = 0; i <= n; i++) a[i][m] = 0;
for (int j = 0; j <= m; j++) a[n][j] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
a[i][m] ^= a[i][j];
a[n][j] ^= a[i][j];
a[n][m] ^= a[i][j];
}
}
int fullmask_n = (1 << (n+1)) - 1;
int fullmask_m = (1 << (m+1)) - 1;
for (int rmv = 0; rmv <= m; rmv++) {
for (int i = 0; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
w[i][j] = 0;
for (int l = 0; l <= m; l++) {
if (rmv == l) continue;
w[i][j] += abs(a[i][l] - a[j][l]);
}
w[j][i] = w[i][j];
}
}
for (int i = 0; i <= n; i++) {
fill(dp[i], dp[i] + fullmask_n, INT_MAX);
dp[i][1 << i] = 0;
}
for (int mask = 0; mask <= fullmask_n; mask++) {
for (int last = 0; last <= n; last++) {
if (~mask >> last & 1) continue;
if (__builtin_popcount(mask) == n) continue;
for (int next = 0; next <= n; next++) {
if (mask >> next & 1) continue;
int new_mask = mask | 1 << next;
dp[next][new_mask] = min(
dp[next][new_mask],
dp[last][mask] + w[last][next]
);
}
}
}
for (int i = 0; i <= n; i++) {
fr[i][rmv] = INT_MAX;
int mask = fullmask_n ^ 1 << i;
for (int last = 0; last <= n; last++) {
fr[i][rmv] = min(fr[i][rmv], dp[last][mask]);
}
}
}
for (int rmv = 0; rmv <= n; rmv++) {
for (int i = 0; i <= m; i++) {
for (int j = i + 1; j <= m; j++) {
w[i][j] = 0;
for (int l = 0; l <= n; l++) {
if (rmv == l) continue;
w[i][j] += abs(a[l][i] - a[l][j]);
}
w[j][i] = w[i][j];
}
}
for (int i = 0; i <= m; i++) {
fill(dp[i], dp[i] + fullmask_m, INT_MAX);
dp[i][1 << i] = 0;
}
for (int mask = 0; mask <= fullmask_m; mask++) {
for (int last = 0; last <= m; last++) {
if (~mask >> last & 1) continue;
if (__builtin_popcount(mask) == m) continue;
for (int next = 0; next <= m; next++) {
if (mask >> next & 1) continue;
int new_mask = mask | 1 << next;
dp[next][new_mask] = min(
dp[next][new_mask],
dp[last][mask] + w[last][next]
);
}
}
}
for (int i = 0; i <= m; i++) {
fc[rmv][i] = INT_MAX;
int mask = fullmask_m ^ 1 << i;
for (int last = 0; last <= m; last++) {
fc[rmv][i] = min(fc[rmv][i], dp[last][mask]);
}
}
}
int ans = INT_MAX;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
ans = min(ans, fr[i][j] + fc[i][j]);
}
}
cout << ans << '\n';
}
}
1993F1 - Dyn-scripted Robot (Easy Version)
Let the robot moves freely (no modification on the script).
The new path of the robot is the "mirrored" version of how the robot must go.
Imagine we have two robots, let's call them Alex and Bob. Alex is the one who follows the instruction well, but Bob doesn't (if he tries to move outside the box, he keeps going without modifying the script). Then, you follow the path of each robot that is moving. How do you think their paths differ from each other?
Yes! Suppose at some moment they reach the top side of the box at the same time. Suddenly, Bob wants to move up while Alex know the discipline and modify the script before executing the command and move down. Then, each of them is $$$1$$$ unit away from the top side of the box. If Bob keeps moving up, Alex keep moving down. In case Bob changes his mind and move down then this time Alex changes her mind and move up.
What do we learn from this? They move like two objects facing each other through a mirror. Actually there are four mirror of them, placing at the four sides of the box.
Now, let's say Bob moves up so much that Alex follows the script and reaches the top side and the bottom side as well. Because of that, she has to change the script once again and start moving up like Bob.
When Alex reaches the bottom side at point $$$(x, 0)$$$, then Bob should be at point $$$(x, 2H)$$$ (prove it yourself!). If Bob keeps moving up to the point $$$(x, 4H), (x, 6H), or (x, 8H), \dots$$$, at these moment Alex will also be at point $$$(x, 0)$$$. That being said, Alex's position is $$$(x, 0)$$$ then Bob's position must be $$$(x, y)$$$ where y is a multiple of $$$2H$$$.
This idea is exactly the same as if Bob were moving sideways (left or right). As we only care about the number of times Alex's position is $$$(0, 0)$$$, we know that if we don't change the script at all, the position of the robot must be $$$(x, y)$$$ where $$$x$$$ is a multiple of $$$2W$$$, and $$$y$$$ is a multiple of $$$2H$$$.
So apparently, we need to calculate the number of times the robot reaches $$$(x, y)$$$, where $$$x$$$ is a multiple of $$$2W$$$ and $$$y$$$ is a multiple of $$$2H$$$ (see the general idea above).
Let's call $$$t_k = (x_k, y_k)$$$ how much the robot moves (in direction) after executing the first $$$i$$$ commands of the script. Then: $$$t_0 = (0, 0)$$$ and $$$t_k$$$ can be calculated through $$$t_{k-1}$$$ and $$$s_k$$$.
The robot will execute the script $$$k$$$ times and the script contains $$$n$$$ commands, so we have $$$nk$$$ positions to check out. Each position can be represented by: $$$(x, y) = it_n + t_j = (ix_n + x_j, iy_n + y_j)$$$ (where $$$0\le i\le k-1$$$ and $$$1\le j\le n$$$). Besides, we need:
- $$$x\equiv 0\pmod{2W} \Longrightarrow ix_n + x_j\equiv 0\pmod{2W} \Longrightarrow x_j\equiv -ix_n\pmod{2W}$$$
- $$$y\equiv 0\pmod{2H} \Longrightarrow iy_n + y_j\equiv 0\pmod{2H} \Longrightarrow y_j\equiv -iy_n\pmod{2H}$$$
Lastly, we can traverse all possible $$$i$$$ from $$$0$$$ to $$$k-1$$$ and count the number of $$$j$$$ that satisfies the above equivalence. One possible way to do this is to use a map to count each element in the array $$$t_1, t_2, \dots, t_n$$$. Summing all the counts will give the answer for this problem.
Time complexity: $$$O((n + k)\log n)$$$
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 5;
string s;
ll n, k, w, h;
ll tx[2*N], ty[2*N];
map<pair<ll, ll>, ll> cnt;
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
while (t--) {
cin >> n >> k >> w >> h >> s;
cnt.clear();
ll x = 0, y = 0;
for (int i = 0; i < n; i++) {
if (s[i] == 'L') x--;
if (s[i] == 'R') x++;
if (s[i] == 'D') y--;
if (s[i] == 'U') y++;
x = (x + 2*w) % (2*w);
y = (y + 2*h) % (2*h);
cnt[{x, y}]++;
}
ll ans = 0;
for (int i = 0; i < k; i++) {
ll vx = (-i*x%(2*w) + 2*w)%(2*w);
ll vy = (-i*y%(2*h) + 2*h)%(2*h);
ans += cnt[{vx, vy}];
}
cout << ans << '\n';
}
}
1993F2 - Dyn-scripted Robot (Hard Version)
Coming soon...
Wow really fast editorial thank you
D is cool
agree although i didn't solve it
thanks for fast editorial
can someone explain C
Realize that all the chips are activated after the max(a_i). Let's call the interval corresponding to this max time as interval I, and the chip corresponding to it as chip i. So, since the entire pattern of the intervals being on/off is periodic, we know that there is nothing special (i.e. different) that happens later (after interval I). So, we know that, if the intervals all overlap at some point, it will happen in this first occurrence of chip i being on, over interval I. So, we can just maintain the intersection of the ON intervals (within I) across all the chips, using a high and low. If we end the intersection with a valid interval, the answer is the earliest time in that interval, otherwise the answer is no.
It's so refreshing to see all the participants solving the contest I'd tested.
Thank you GlowCheese for inviting me to become a tester.
Thanks for the Editorial The problems are really fun :D
can we use binary search for problem C ? :)
No, it's not a linear function :D
Yes, I used it in my solution
what did you use for the decision making in your binary search approach?
I just found that if the answer exist, all the lights will be turned on somewhere in the range [mx ; mx + k — 1], where mx is the biggest element in the array. So I used binary search to find for each element in the array the nearest minute (z) where at the minute z the current element will be turned on and the range [z ; z + k — 1] is intersect with the range [mx ; mx + k — 1]. and if the intersect exist for all elements then the answer exist and it is the first point of the range resulting from the intersections. I hope this is helpful.
Hey Sandman10,
How are you ensuring that you are only checking for even numbers, Like ai, ai + 2*k , ai + 4*k, because light will be ON only on even points.
For doing so we need to do
for (ll i = 0; i <= 1e9; i += 2) { arr.pb(i); }
and this will result in MLE.
Exactamento!
u dont need to, since every segments of length k, with the leftmost point congruent to a[i] modulo 2*k, which means u only need to care about the remainder of every a[i], divided by 2*k (and of course, the largest value in the array)
Honestly i feel like its not required. Implementing BS in that is like giving the TC extra logn factor to deal with instead we can just divide the distance from max(a) to a[i] by k and get the range for intersect based in the parity easily. I mean like ur solution is correct and u avoided the mathematical calculations successfully by integrating BS in ur solution but the TC increases by some multiple.
bs : https://mirror.codeforces.com/contest/1993/submission/274424933
Problem C was really funny.. thx :)
You're welcome ;)
Really great problems with nice observations, why is the editorial getting downvotes ? Is it because you guys are mad not able to solve the problems ?
Bro ur post is also getting downvoted!! Funny to see it.
I enjoyed solving D and E very much :) which is quite rare for a div2 round
Thanks a lot
I think you should have lowered constraints in E though since my and probably many others n^4 2^n did not pass, and the optimization is just boring
$$$O(n^4 2^n)$$$ still passes though as I set the time limit pretty high (5 times how intended solution should run), but you may find some luck to get it AC
Take a look at submissions, you will find a lot of TLEs.
5x from n^3 2^n doesnt mean it will pass since going purely theoretically, its 15x
My n^4 * 2^n took 13s on cf custom invo. I removed the factor of n to get it to 1.6s
I'm glad that you liked it :D
Wow fast Editorial
wish i solved D, but really fun contest nonetheless!
algorithm contest -> ❌ math contest -> ✅
It was never supposed to be an algorithm contest, this is a thinking and problem solving contest. Also which problem exactly needed math?
"it was never supposed to be an algorithmic contest"
what a stupid thing to say
The number of using the word "mod" in the solution was more than the total number of questions.
That is because it can be modeled in mathematical terms and that way the solution is easier to understand, it doesn't mean the solution is math based.
how can you say C is not math?
It's not, in the editorial it is modeled mathematically to be precise. This was my thinking process: If there is a possible time, it will be in the first turned on interval of the maximum $$$a[i]$$$. So i will bring every $$$a[i]$$$ so that it intersects with the maximum $$$a[i]$$$ and update the left and right bound of the answer.
and still some of those can be solved without mod at all. C has mod in editorial but can be solved with a different approach that doesn't require mod
Yes, I use some trick with the brain to solve it without mod 274409368, but still you need some good insight for the problem just to solve it :3
I also had the same approach. Honestly, I couldn't still understand how people could think of a solution involving modulus during the contest itself. Great thinking
Actually, people choose to use modulus is it's better to understanding the problem in that way, and you can prove it's correct while my approach may get hack if there is an edge case :3
Thanks for fast editorial!
Ah, I should've been able to do B. Don't know where my code went wrong. Anyway, Thanks for the editorial.
in your code, whenever the "if(store < a)" is true, you can just print out the amount of even numbers+1. the solution will always be either 0, the amount of even numbers, or the amount of even numbers+1.
Yes, I understood my mistake. I should've thought of this. Thanks for replying, buddy!
Nice Solutions.
The solution for F1 (and F2) is really elegant and tricky! I enjoyed (attempting to) solve the problem very much. Hope to see more of such problems.
Editorial is high quality. Nice problems too, been a while since I've seen a moving interval one (C).
274419542 why i didn
t get TL for C task? It
s O(n*k)I don’t understand why binary searching works on D They aren’t even checking whether the bs element is present in array or not?
You are checking if the answer can be at least mid.
Can someone please explain in problem D if I am doing binary search on median and getting that number "mid" should be in middle, how am I even able to check by dp if I can remove segments accordingly, please explain the check function in simpler terms. Thanks in advance!
mid should not be in middle, it should be less than or equal to median. Means we are binary searching on the predicate: f(mid) -> is mid lying to the left of median? and we can do that by counting elements greater than mid, if they are greater than half the size of array, then it will return true.
in C, I did linear search in the range max(array)to max(array)+k and got the answer. the check function i used for every numbers in the range is- ~~~~~ function<bool(int)>check=[&](int t){ for(int i=0;i<n;i++){ if((t-v[i])<0||((t-v[i])/k)%2!=0) return false; } return true; }; ~~~~~ can someone explain how these range working, also i think the complexity is O(N*k)??
very weak tests i think, i saw some O(n*k) solution got hacked, so i think that its just really weak tests.
E is really a good problem
Why, in problem C, the solution with time complexity O(nk) not giving TLE?
I first submitted O(nk) solution (274384802).
Then later, submitted O(n) solution (274394074).
After the system testing, I again submitted my O(nk) solution just to check if it is passing or not, and it got passed. I think the test cases were quite weak for Problem C
just submitted your code and got a TLE
274432933
this is not a contest but rather a clown fest
B- Parity and Sum
can someone please help me understand why my solution was WA on test case 2
C++ solution:
I think the intution is correct, I'm doing the same same thing as per the solution
It's was my first try too. The problem that some times choose the biggest even number from
evn
, it's better than a smaller one. Because if you take $$$a > b$$$, which is at the end ofevn
, then you increasemxod
and nowmxod = mxod + max_elemen(evn)
, so now mxod is in 100% of cases is greater than anyevn
andans += 2
isn't caseWhat is the dp state in the editorial of problem D?
As usual, thanks to the authors for this round ! Here is my advice about the problems:
Good problem, not random lcm problem but not A + B either.
I feel like it's very hard to come up with a good B, this one is perfect imo.
I guess it does the job as a C. The problem felt a bit weird though. Also, there are way too many solves for C so maybe it could be better ? idk
Great great great problem! It is a little bit of a "troll" problem though but the idea is cute and interesting. It felt enlightening. Btw, I don't think it is too hard for D
I did not think more than 10mn about it but wtf? This looks super cursed (but the problem might be cool)
It seems that E is a bit too hard though (looking at the solve count).
In Problem D they did not specify that sum of k is less than 5e5, so after I got pretests accepted with O((n + k) * log(1e9)) per testcase solution, I assumed that it whould fail the system test because of the Time Limit. I fixed and resubmited the solution with O(n * log(1e9)) time complexity and it passed the system tests, but it seems like there was not any test case in the system tests that results in a TLE. So if anybody wants to get free hacks for problem D, they can easily construct a testcase where t = 1e4 and n = 1, k = 5e5 for each test case.
If k>n, the solution is trivial. O(n*log(n)) if you sort the array for finding the median
For D. My solution https://mirror.codeforces.com/contest/1993/submission/274431244 is giving RTE on the following test case:
1
1 500000
3169420
But when I am running it locally it is working just fine. Can anyone please help me?
for(int i = 0 ; i < k ; ++i){
Your solution looped $$$k$$$ independently from $$$n$$$, and will fail if $$$k > n$$$.
Thanks a lot!
I solved C, in a slightly different way
1) If the answer exists it's always going to be from (max(a), max(a)+k-1). (Observation from provided test cases).
2) so we add (2*k*r(some integer) to each element a[i] in place, such that a[i]+2k is just greater than max(a).(2k because in every 2k intervals the light will be on)
3) we need to find two things if(max(a)-min(a)>=k) the answer will be -1, else the answer is max(a).
Solution here: https://mirror.codeforces.com/contest/1993/submission/274401978
this ecxactly what i did, more easy to think and code,just greedy, no math no algorithm
Correct me, if I'm wrong, but shouldn't we choose both n+1th row and m+1th column at the same time to correctly calculate R and C?
I mean, e.g. when calculating C, we need at the same time remove one row (to look for the best solution on n remaining rows) and remove one column (because otherwise distance between rows cannot be calculated correctly). Hence complexity should be somewhat $$$O((n+1)(m+1) \cdot ((m+1)^22^{m+1} + (n+1)^22^{n+1}))$$$ or $$$O(n^42^n)$$$
I think the editorial for problem B is for another version of the problem where we can make operations on numbers having the same parity ? You could fix it by just removing the part talking about that x)
Btw it's quite cool that the editorial was writen that much in advance!
Guys i have a doubt
https://mirror.codeforces.com/contest/1993/submission/274430880
Im getting wrong answer on the above submission
but my other solution (https://mirror.codeforces.com/contest/1993/submission/274433114) is getting accepted why? i understand the logic of the 2nd one but whats wrong with my first submission?
Consider test case with
n = 3
,a = [1, 2, 6]
. Your algorithm would first set maxodd to be 1, then it would use 2 operations to turn 1 -> 3 and 2 -> 5, then 2 more operations to turn 5 -> 11 and 6 -> 17. But in an optimal answer you never need to use 2 operations on an even number more than once, so the actual answer is 3 and not 4.Thanks a lot man, but now you made me feel stupid T_T
If
maxodd
is less thanv[i]
, you should add the largest even number tomaxodd
, instead ofv[i]
. Addingv[i]
may lead to extra operations.There's typo in editorial of D, it should be: $$$b[i]=1$$$ if $$$a[i]≥x$$$ right?
Funny thing is: there is a recent video with 3blue1brown which mentioned general idea from F (they called it quite popular but i'm not really into geometry so idk)
With that video in mind it was much easier to think up the solution
In problem B you must take numbers such that have distinct parities. So you can remove even + even & odd + odd options from editorial. EDIT: I'm a bit late to tell it first.
A, B, C are OK but gap between C & D is not OK.
~~~~~~~~~~~~~~~~~~~ import java.util.*; public class Main{ public static void main(String args[]){ Scanner sc=new Scanner(System.in); int t=sc.nextInt(); while(t-->0) { int n=sc.nextInt();
~~~~~~~~~~~~~~~ can someone please tell me what is wrong in this only the last test case of test case 1 is showing wrong answer
GlowCheese
1) why the fuck is not k <= n in problem D, it makes no sense
2) why do tests not have k = max, and 1e4 tests???? How do you miss that in the tests. My solution uses an array of k size and passeed the initial tests https://mirror.codeforces.com/contest/1993/submission/274400595
Wdym makes no sense? Makes enough sense to troll some careless coders :D
Troll didnt even work due to weak tests :)
Problem D might be my favourite problem ever.
its very common algorithm in Vietnam.If you can do it, your level is equivalent to a fairly good high school student in Vietnam
What's the algorithm called?
its calling binary search on result, that you find the minimal result can be, and the maximum result can be, and binary search on it with a bool check(), remember that the answer must be linear, that is, if one position is satisfied, then the whole in front or behind it must also be satisfied. it is effective for problems that require finding something that is largest or smallest, or the answer involves something that is linear.
I guess binary searching on the result wasn't the tricky part for me, it was more translating the given array into 'b' where 'b[i]' is if the element is greater than the desired median or not.
bro you missed the check for correct parentheses problem XD
Can anyone help me figure out what the time complexity is for my solution to D?
I used recursion with memoization to solve for the answer. Let the initial size of the array be N. I start with the full array, and using recursion I get the answer for every possible array of size N-K, and so on. I store the maximum answer. I keep doing that until the size of the array is smaller than or equal to K. Then I find the median of the array. I have an map which stores the indices that I have removed.
I'm thinking the time complexity is O(N^2log(n)). My reasoning is that there are ~ N^2 subbarays of different sizes, and the sort takes log(N) time. Is that correct.
This is my code: https://mirror.codeforces.com/contest/1993/submission/274435465
B Video Editorial : https://youtu.be/xTb58OEZnJM
C Video Editorial : https://youtu.be/6xtmLO43mD4
Can anyone please tell me where I am going wrong in this code I am always taking the maximum odd number and updating it whenever required and storing the value in ans variable. 274393002
Problem D was cool.
Approached the problems in a million ways. But didn't think in this way.
Was thinking about BS + some sort of greedy
Also thought about some DP
But nice technique of reducing this problem only to a simple dp sum problem.
in D it should be x<=a[i],right?
Was C that easy? I am unable to find any clue to solve even after seeing the comments and editorial
Hello
Can someone help me with my solution for C? I'm getting wrong answer on test 2 on the 2003rd test, so there's an off by one error somewhere. Here's the link to my submission: https://mirror.codeforces.com/contest/1993/submission/274445861
I take the time of the light being installed as lowerbound and that time + k as the upperbound, and I set the lowerbound in an array to be +1 and the upperbound as -1 However if the lowerbound to upperbound contains 2k in the middle, then it loops around after the mod, so i set the lowerbound to +1 and the 0th index to +1 and the new upperbound to -1 to account for this loop around Then I add in the array as I go until I find the first index that has the value n (meaning all lights are on at this moment) and at the end I check if index 0 was an answer, then I shift the answer to put it after max(a)
why is this code for problem C not giving correct output on codeforces compiler? Link to Submission
while same code gives correct output on my local vscode and also on codechef online c++ compiler
for the 1st test case it is giving correct output as given in the problem