Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
for _ in range(int(input())):
n = int(input())
s = input()
print("NO" if s.count('1') == n else "YES")
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
fun main(args: Array<String>) {
repeat(readln().toInt()) {
val (n, p, l, t) = readln().split(' ').map { it.toLong() }
val cntTasks = (n + 6) / 7
fun calc(k: Long) = k * l + minOf(2 * k, cntTasks) * t
var lf = 0L
var rg = n
while (rg - lf > 1) {
val mid = (lf + rg) / 2
if (calc(mid) >= p)
rg = mid
else
lf = mid
}
println(n - rg)
}
}
Tutorial
Tutorial is loading...
Solution (awoo)
from math import gcd
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
g = 0
for i in range(n - 1):
g = gcd(g, a[i + 1] - a[i])
g = max(g, 1)
a.sort()
j = n - 1
res = a[-1]
while True:
while j >= 0 and a[j] > res:
j -= 1
if j < 0 or a[j] != res:
break
res -= g
print((a[-1] * (n + 1) - (sum(a) + res)) // g)
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
using pt = pair<int, int>;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int n, q;
cin >> n >> q;
string s;
cin >> s;
vector<pt> pos(n + 1);
for (int i = 0; i < n; ++i) {
pos[i + 1].x = pos[i].x + (s[i] == 'R') - (s[i] == 'L');
pos[i + 1].y = pos[i].y + (s[i] == 'U') - (s[i] == 'D');
}
map<pt, vector<int>> mp;
for (int i = 0; i <= n; ++i) mp[pos[i]].push_back(i);
auto check = [&](pt p, int l, int r) {
if (!mp.count(p)) return false;
auto it = lower_bound(mp[p].begin(), mp[p].end(), l);
return it != mp[p].end() && *it <= r;
};
while (q--) {
int x, y, l, r;
cin >> x >> y >> l >> r;
int nx = pos[r].x + pos[l - 1].x - x, ny = pos[r].y + pos[l - 1].y - y;
bool f = check({x, y}, 0, l - 1)
| check({nx, ny}, l, r - 1)
| check({x, y}, r, n);
cout << (f ? "YES" : "NO") << '\n';
}
}
Idea: Roms
Tutorial
Tutorial is loading...
Solution (Roms)
#include <bits/stdc++.h>
using namespace std;
const int N = int(1e6) + 99;
int nxt;
int to[N][26];
int sum[N];
long long res;
void add(const string& s) {
int v = 0;
++sum[v];
for (auto c : s) {
int i = c - 'a';
if (to[v][i] == -1)
to[v][i] = nxt++;
v = to[v][i];
++sum[v];
}
}
void upd(const string& s) {
int curLen = s.size();
int v = 0;
for (auto c : s) {
int i = c - 'a';
if (to[v][i] == -1) {
res += sum[v] * 1LL * curLen;
break;
} else {
int nxtV = to[v][i];
res += (sum[v] - sum[nxtV]) * 1LL * curLen;
--curLen;
v = nxtV;
}
}
}
void solve(int n, vector <string> v) {
int sumSizes = 0;
for (int i = 0; i < n; ++i)
sumSizes += v[i].size();
nxt = 1;
memset(sum, 0, sizeof sum);
memset(to, -1, sizeof to);
for(int i = 0; i < n; ++i)
add(v[i]);
for (int i = 0; i < n; ++i) {
reverse(v[i].begin(), v[i].end());
upd(v[i]);
}
}
int main() {
ios_base::sync_with_stdio(false);
int n;
cin >> n;
vector <string> v(n);
for (int i = 0; i < n; ++i)
cin >> v[i];
res = 0;
solve(n, v);
for(int i = 0; i < n; ++i)
reverse(v[i].end(), v[i].end());
solve(n, v);
cout << res << endl;
return 0;
}
1902F - Trees and XOR Queries Again
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 200043;
const int K = 20;
typedef array<int, K> base;
int a[N];
vector<int> g[N];
vector<int> path_up[N];
int tin[N], tout[N];
int T = 0;
int fup[N][K];
base make_empty()
{
base b;
for(int i = 0; i < K; i++)
b[i] = 0;
return b;
}
int reduce(const base& b, int x)
{
for(int i = K - 1; i >= 0; i--)
if(x & (1 << i))
x ^= b[i];
return x;
}
bool add(base& b, int x)
{
x = reduce(b, x);
if(x != 0)
{
for(int i = K - 1; i >= 0; i--)
if(x & (1 << i))
{
b[i] = x;
return true;
}
}
return false;
}
bool check(const base& b, int x)
{
return reduce(b, x) == 0;
}
vector<int> rebuild_path(const vector<int>& path, int v)
{
base b = make_empty();
vector<int> ans;
if(add(b, a[v])) ans.push_back(v);
for(auto x : path) if(add(b, a[x])) ans.push_back(x);
return ans;
}
void dfs(int v, int u)
{
tin[v] = T++;
if(u == v)
path_up[v] = rebuild_path(vector<int>(0), v);
else
path_up[v] = rebuild_path(path_up[u], v);
fup[v][0] = u;
for(int i = 1; i < K; i++)
fup[v][i] = fup[fup[v][i - 1]][i - 1];
for(auto y : g[v])
if(y != u)
dfs(y, v);
tout[v] = T++;
}
bool is_ancestor(int u, int v)
{
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int LCA(int x, int y)
{
if(is_ancestor(x, y)) return x;
for(int i = K - 1; i >= 0; i--)
if(!is_ancestor(fup[x][i], y))
x = fup[x][i];
return fup[x][0];
}
bool query(int x, int y, int k)
{
base b = make_empty();
int z = LCA(x, y);
for(auto v : path_up[x])
if(!is_ancestor(v, y))
add(b, a[v]);
for(auto v : path_up[y])
if(!is_ancestor(v, x))
add(b, a[v]);
add(b, a[z]);
return check(b, k);
}
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
for(int i = 0; i < n - 1; i++)
{
int x, y;
scanf("%d %d", &x, &y);
--x;
--y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(0, 0);
int q;
scanf("%d", &q);
for(int i = 0; i < q; i++)
{
int x, y, k;
scanf("%d %d %d", &x, &y, &k);
--x;
--y;
if(query(x, y, k)) puts("YES");
else puts("NO");
}
}
E was awesome. Thanks for great problems
that was the first time I ever solved Div2 E
are you really yuzi? or just a fan of yuzi
When will you update the rating change for this round?
It has been unrated I guess
How could that be!? Contest title clearly says it's Rated for Div2
Idk but when I filtered my contests to only unrated.I found it there so I thought maybe it was made unrated.
All contests are shown under 'unrated' before ratings are updated. You can't make any assumtions based on that. If a contest is made unrated, it will be announced on the original contest announcement.
I've noticed that my position on the leaderboard has increased after the competition fully finished. Maybe they are trying to prune out cheaters?
C was the coolest
Thank for contest! But where is rating?
It's amazing to see how much implementation matters in Question D — the solution by Neon is so concise and pretty.
awoo, I think there is a typo in the editorial for Problem 1902E - Collapsing Strings. It should be $$$|C(a,b)|=|a|+|b|− \textbf{2} \times |LCP(a′,b)|$$$.
Thank you, will be fixed in a couple of minutes
F was cute :)
For Problem D
How Δi,j is found over there in editorial? Is there a simpler way?
I did this in the below given way
Found the pattern of how reversing changes the path(about what lines the pattern is reflected) and accordingly what distance each point is moving with respect to reflections, there by finding the Δi,j.
If you reach point p=path[l]+d then when commands are reversed you'll have to walk d to reach the end: rp+d=path[r]
You can also see that the path with reversed actions is obtained through a 180-degree CCW rotation and a shift.
I feel like tests for F are not really strong or otherwise, I am not sure why my $$$O(n \log n B^2 + q B^2)$$$ solution 235594622 is so fast. I didn't try to optimize anything.
LOL, I feel so stupid after looking at the editorial for B. but I am happy to have learnt these "new"(for me) techniques (especially, generating files to find failing testcases, use of ceil() function, proving a greedy approach) and I believe that is one of the main objective of the EDU rounds! I tried to apply greedy approach, was not able to figure out on which cases the code was failing, after like 5 submissions I realized that first ,I should find those days where 2 tasks can be completed like on day 8, 22, 36 etc and add (l+2*t) to points. Then if still points are not enough, add (l+t) to answer if left with any task, and then finally add any remaining points in the form of l. this is my messy solution 235754545. looking forward to better performances in the future.
The Trie answer for E is accepted by PyPy3 but not PyPy3-64. :(
Yeah had the same issue, from what i saw you can use lists instead of dicts to pass it, and since there are only 26 letters at max you can check in O(1) time if the element exists.
Generally i feel like Div 2 E is as far as you can get with python, which is why i am trying to transfer to C++. I have had it happen so many times, that i couldn't pass E, but after translating my code to C++ it passed.
What is the difference between https://codeforces.net/contest/1902/submission/235770255 and https://codeforces.net/contest/1902/submission/235600034 ? Why does it work when I change beginning to 2n*sum(1->n) then subtract and not when i continuously add to a starting val of 0 length*n+sum-subtracted value . of lengths? When I use summation rules the outcome is the same.
(totallength+(sum of all individual length(which is total length)))*n = 2n sum of all length, then I did not change the way I calculated what I need to subtract subtract.
The second code doesn't work since
s.length()*n
can overflow.Silly mistake... thanks for the help
My first time solving every problem before editorial))))
So, it means that the points that the robot visits can be represented as follows: for an integer k such that l≤k≤r, perform all commands from 1 to r, except for the commands from l to k
Could someone explain this part of the tutorial for D please?
For example if a take k = l, the this means that I'll make all the commands from 1 to l-1 and then from l+1 to r? I don´t get it :'(
It means you can check the path for the commands from 1 to l-1 and then from r to the end.
Notice that when you flip the instructions from l to r, the path from 1 to l-1 is unaffected (because nothing has changed for those parts).
Now notice that when you flip the instructions, you are just changing the order of instructions, the instructions that are carried out are still the same (in other words, if there are 5U and 5L before flipping, there will still be 5U and 5L after flipping, the order is just different).
Let us take the change in coordinates caused by flipped instructions as {dx, dy}.
Notice that dx = number of r — number of l, and dy = number of u — number of d. Since the number of instructions for each direction remains unchanged, we can conclude that dx and dy remains the same.
All this means is that before flipping, we start at the same place, and after flipping, we end at the same place as compared to our original path. Since there are no changes to the instructions after flipping, we can also conclude that the path before and after flipping is the same.
Hence, we can check the original path for 1 to l-1 and r to the end, then check the reversed path (with some simple math) from l to r.
Thank you ArtemiszenN!! Actually it was not the answer I was lookinfor but you made me notice something important to understand what I was asking and that is the instructions remain the same just in other order.
Literally I couldn't notice that when taking k and process instructions from 1 to l-1 and then from k+1 to r leads to the same coordinate when processing instructions from 1 to l-1 and then the first k instructions in the flipped string.
Thank you ^-^
The solution of problem F in $$$O(n\log^2 V)$$$ is awesome! I just came up with a simple $$$O(n\log^3 V)$$$ solution:
Through the definition of XOR base (mentioned in the official tutorial) we can conclude that for two integer set $$$A$$$ and $$$B$$$, $$$X(A\cup B) = X(X(A)\cup X(B))$$$, where $$$X(S)$$$ means the XOR base of an integer set $$$S$$$. Through, we can merge two XOR base in $$$O(\log^2 V)$$$ time: Simply insert all element of $$$X(A)$$$ and $$$X(B)$$$ into the resulting XOR base.
Therefore, using binary lifting algorithm on tree just like solving LCA, we get an $$$O[(n + q)\log^3 V]$$$ solution.
Usually the $$$O[(n + q)\log^3 V]$$$ complexity with no optimization can't pass all tests (TLE on test [70, 93]). So here's a trick to improve your constant factor: When adding integers into a XOR base $$$B$$$, if $$$B$$$ has exactly $$$20$$$ element, then do noting, because it will not change any element of $$$B$$$. Hope this will help you.
Here is an example: (C++)
Can someone please explain how do we arrive at $$$2*n \sum_{i=1}^{n} Si - 2* \sum_{i=1}^{n} \sum_{i=1}^{n} LCP(Si', Sj)$$$.
I wanna know specifically how do we get $$$2*n \sum_{i=1}^{n} si$$$. Thankyou!
Oh I get it each string occurs $$$2*n$$$ times, once on it's own pairs, and once paired with others.
Problem C: Can someone please help me out to understand the limitation of using
int[]
compared tolong long[]
for storing all the values in an array.using long long: https://codeforces.net/contest/1902/submission/235786184
using int: https://codeforces.net/contest/1902/submission/235786137
did u find it? I've the same issue.
AC with long long -> link
WA with int -> link
no no not yet...
ans += (a[n-1] — (a[idx] — diff))/diff;
diff can be 2e9
Hack:
Thanks a lot it, I completely missed it.
Alternate solution of problem E: https://codeforces.net/contest/1902/submission/236207452
why does an $$$O(n \ log \ n)$$$ hash based solution for E TLE :/ slow modulo?
AC with the same code by replacing map with unordered_map: 236707409
I have problem that a lgm can't answer,and if someone is able to, everyone will admire him and he will be legend
How to get a girlfriend?
For D, i suppose offline queries ( sorted by r) method would be more easier. Then no need of binary search also. submission
Can anyone please help me in identifying the mistake in the code? My logic is correct but I am not able to identify a case where it is giving a zero answer.
Submission
I don't know what is the problem here, everything seems fine. But I made some changes to your code and submitted it, and it worked. https://codeforces.net/contest/1902/submission/242354858
My code for problem D is giving tle at test 41. Here is the code https://codeforces.net/contest/1902/submission/241087945 Can anyone suggest any optimization that can be done here. Thanks
same . could u tell me how u resolve this issue?
I tried to solve problem E using Trie, but it repeatedly gives Memory Limit Exceeded on test case 16. I don't see any mistake in the construction of the Trie and looks like it used O(S*26) memory. Any sort of discussion will help a lot. This is the submission link : https://codeforces.net/contest/1902/submission/244942580
Reverse the operation sequence, and the new path is equivalent to the original path being symmetrical about the midpoint of the starting and ending line.
nice
could anyone tell me why i am getting tle on test case 41? my solution is of o(nlogn) {if i am not wrong} . and by seeing constraints it should pass the testcases?. anyone?
sumbission link :- https://codeforces.net/contest/1902/submission/256209886
Plz help with this submission for problem E, couldn't find any reason for a runtime error. It passes all small test cases. Integer overflow is taken care of.
https://codeforces.net/contest/1902/submission/287423396