Idea: fcspartakm
Tutorial
Tutorial is loading...
Solution (fcspartakm)
#include <bits/stdc++.h>
using namespace std;
int n;
inline void read() {
cin >> n;
}
inline void solve() {
for (int x = 1; x <= 20; x++) {
for (int y = 1; y <= 20; y++) {
if (x + y >= n || x == y) continue;
int z = n - x - y;
if (z == x || z == y) continue;
if (x % 3 == 0 || y % 3 == 0 || z % 3 == 0) {
continue;
}
puts("YES");
cout << x << ' ' << y << ' ' << z << endl;
return;
}
}
puts("NO");
}
int main () {
int t;
cin >> t;
while (t--){
read();
solve();
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
auto dist = [](int x1, int y1, int x2, int y2) {
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
};
int t;
cin >> t;
while (t--) {
int px, py, ax, ay, bx, by;
cin >> px >> py >> ax >> ay >> bx >> by;
double pa = dist(px, py, ax, ay), pb = dist(px, py, bx, by);
double oa = dist(0, 0, ax, ay), ob = dist(0, 0, bx, by);
double ab = dist(ax, ay, bx, by);
double ans = 1e9;
ans = min(ans, max(pa, oa));
ans = min(ans, max(pb, ob));
ans = min(ans, max({ab / 2, pa, ob}));
ans = min(ans, max({ab / 2, pb, oa}));
cout << setprecision(10) << fixed << ans << '\n';
}
}
Idea: Roms
Tutorial
Tutorial is loading...
Solution (Roms)
#include <bits/stdc++.h>
using namespace std;
const int N = 200000;
int t;
int main() {
cin >> t;
for (int tc = 0; tc < t; ++tc) {
string s;
long long pos;
cin >> s >> pos;
--pos;
int curLen = s.size();
vector <char> st;
bool ok = pos < curLen;
s += '$';
for (auto c : s) {
while (!ok && st.size() > 0 && st.back() > c) {
pos -= curLen;
--curLen;
st.pop_back();
if(pos < curLen)
ok = true;
}
st.push_back(c);
}
cout << st[pos];
}
return 0;
}
Idea: Roms
Tutorial
Tutorial is loading...
Solution (Roms)
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
const int N = 300009;
int bp(int a, int n) {
int res = 1;
while(n > 0) {
if (n & 1)
res = (res * 1LL * a) % MOD;
a = (a * 1LL * a) % MOD;
n >>= 1;
}
return res;
}
int n, m;
string s;
int inv[N];
void upd(int &res, int x) {
res = (res * 1LL * x) % MOD;
}
int main() {
inv[1] = 1;
for (int i = 2; i < N; ++i){
inv[i] = bp(i, MOD - 2);
}
cin >> n >> m >> s;
int res = 1, k = n;
bool isZero = false;
for (int i = 0; i < s.size(); ++i)
if (s[i] == '?') {
if (i == 0) {
isZero = true;
} else {
upd(res, i);
}
}
cout << (isZero? 0 : res) << endl;
for(int i = 0; i < m; ++i) {
int pos;
char c;
cin >> pos >> c;
--pos;
if (s[pos] == '?' && (c == '<' || c == '>')) {
if (pos == 0)
isZero = false;
else
upd(res, inv[pos]);
} else if ((s[pos] == '<' || s[pos] == '>') && c == '?') {
if (pos == 0)
isZero = true;
else
upd(res, pos);
}
s[pos] = c;
cout << (isZero? 0 : res) << endl;
}
return 0;
}
1886E - I Wanna be the Team Leader
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
int n, m;
scanf("%d%d", &n, &m);
vector<int> a(n), b(m);
forn(i, n) scanf("%d", &a[i]);
forn(i, m) scanf("%d", &b[i]);
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&a](int i, int j){
return a[i] > a[j];
});
vector<vector<int>> mn(m, vector<int>(n + 2));
forn(i, m){
int r = 0;
forn(l, n + 2){
r = min(n + 1, max(r, l + 1));
while (r <= n && a[ord[r - 1]] * (r - l) < b[i]) ++r;
mn[i][l] = r;
}
}
vector<int> dp(1 << m, n + 1);
dp[0] = 0;
vector<int> p(1 << m, -1);
forn(mask, 1 << m) forn(i, m) if (!((mask >> i) & 1) && dp[mask | (1 << i)] > mn[i][dp[mask]]){
dp[mask | (1 << i)] = mn[i][dp[mask]];
p[mask | (1 << i)] = mask;
}
int mask = (1 << m) - 1;
if (dp[mask] > n){
puts("NO");
return 0;
}
puts("YES");
vector<vector<int>> ans(n);
forn(_, m){
int i = __builtin_ctz(mask ^ p[mask]);
for (int j = dp[p[mask]]; j < dp[mask]; ++j)
ans[i].push_back(ord[j]);
mask = p[mask];
}
forn(i, m){
printf("%d", int(ans[i].size()));
for (int x : ans[i]) printf(" %d", x + 1);
puts("");
}
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
const int N = 3003;
int n;
int k[4];
vector<int> a[4];
struct segtree {
int sz;
int tot;
vector<int> t, p;
segtree(int sz) : sz(sz) {
tot = 0;
t = vector<int>(4 * sz);
p = vector<int>(4 * sz);
build(0, 0, sz);
}
void build(int v, int l, int r) {
if (l + 1 == r) {
t[v] = -l;
return;
}
int m = (l + r) / 2;
build(v * 2 + 1, l, m);
build(v * 2 + 2, m, r);
t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
}
void push(int v) {
if (p[v] == 0) return;
if (v + 1 < 2 * sz) {
t[v * 2 + 1] += p[v];
p[v * 2 + 1] += p[v];
t[v * 2 + 2] += p[v];
p[v * 2 + 2] += p[v];
p[v] = 0;
}
}
void upd(int v, int l, int r, int L, int R, int x) {
if (L >= R) return;
if (l == L && r == R) {
t[v] += x;
p[v] += x;
return;
}
push(v);
int m = (l + r) / 2;
upd(v * 2 + 1, l, m, L, min(m, R), x);
upd(v * 2 + 2, m, r, max(L, m), R, x);
t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
}
void upd(int pos, int x) {
tot += x;
upd(0, 0, sz, max(0, pos), sz, x);
}
int get(int v, int l, int r, int L, int R) {
if (L >= R) return -1e9;
if (l == L && r == R) return t[v];
push(v);
int m = (l + r) / 2;
return max(
get(v * 2 + 1, l, m, L, min(m, R)),
get(v * 2 + 2, m, r, max(L, m), R)
);
}
int get(int L) {
return get(0, 0, sz, max(0, L), sz);
}
int getBad(int v, int l, int r) {
if (t[v] <= 0) return -1;
if (l + 1 == r) return l;
push(v);
int m = (l + r) / 2;
if (t[v * 2 + 1] > 0) {
return getBad(v * 2 + 1, l, m);
} else {
return getBad(v * 2 + 2, m, r);
}
}
int getBad() {
return getBad(0, 0, sz);
}
};
int main() {
cin >> n;
int sz = 1;
for (int i = 0; i < n; ++i) {
int t, s;
cin >> t >> s;
a[t].push_back(s);
sz = max(sz, s + 1);
}
for (int t = 1; t < 4; ++t) {
sort(a[t].begin(), a[t].end());
k[t] = a[t].size();
}
reverse(a[2].begin(), a[2].end());
int ans = 1e4;
for (int len = 1; len <= k[2] + k[3] + 1; ++len) {
segtree L(sz), R(sz);
multiset<int> used;
for (int x : a[1]) L.upd(x, +1);
for (int x : a[2]) R.upd(x, +1);
for (int x : a[3]) {
L.upd(x - len, +1);
if (L.t[0] <= 0) {
used.insert(x - len);
} else {
L.upd(x - len, -1);
L.upd(x, +1);
R.upd(x, +1);
}
}
for (int i = 0; i <= k[2]; ++i) {
if (L.t[0] <= 0 && R.t[0] <= 0 && R.tot + 1 <= len)
ans = min(ans, n + (k[3] - (int)used.size()) + 2);
if (i == k[2]) break;
R.upd(a[2][i], -1);
L.upd(a[2][i] - len, +1);
int pos;
while ((pos = L.getBad()) != -1) {
auto it = used.upper_bound(pos);
if (it == used.begin()) break;
--it;
L.upd(*it, -1);
L.upd(*it + len, +1);
R.upd(*it + len, +1);
used.erase(it);
}
}
}
if (ans == 1e4) ans = -1;
cout << ans << '\n';
}
I think I misunderstood c
Problem C editorial is so nicely written..understood it clearly thanks:)
true
amazing round loved it
Just become expert again Amazing contest
basiji good for you i hope goods
oh my god is he basiji ?
yes
What will be the expected difficulty for problem B it seems bit tough compared to other div 2 B Questions
No it is pretty balanced. You need to know basic geometry and/or binary search
definitely not basic geometry, you should have good practise of it atleast
I thought of using binary search at first, on w but w is floating point number. so how can we apply binary search on it can you please elaborate.
Thanks for slow editorial!
Div2 D Alternate explanation:
Consider ?<??>?>??
Observation : Last > will be n and last < be 1
This is always true. If 1 and n are always in the permutation could there be a > after n and < after 1? No. If there aren't any such symbols for either > or < they will be in 1st position .
However will the subsequent >s after last > also be n-1,n-2,n-3? And will the subsequent <s after last < also be 2,3,4.....?
The answer is No.
This is because we have ?s after last > and last < respectively. There we could put values So that we could form a decreasing sequence from n ( > > >) and an increasing sequence from 1 (< < <). There could be many such sequences clearly.
Now let's propose an algorithm,
?<??>?>??
Starting from the back we have n-2 choices where n is number of els in the set. This is because only the minimum(1) and maximum(N) is fixed. Now remove last element.
?<??>?>? again n-2 choices where n is number of els in the set.
?>??>?>
1 choice last > is fixed. Similarly last < is fixed.
?>??>? now last > is the max el in the set. We remove 2 els and N so far. Irrespective of our choices for the 2 els, there will be 1 unique maximum in the set which will take place of last >. So for ? we have n-2 choices again where n is number of els in the set.
Hope you get the solution.
"However will the subsequent >s after last > also be n-1,n-2,n-3? And will the subsequent <s after last < also be 2,3,4.....?
The answer is No."
I made this wrong assumption and was wondering why my solution is wrong! Thanks for this. I never would have realised why my solution is wrong( This happens a lot to me, I make wrong assumptions and get to a wrong solution but I never find that wrong assumption on my own, and usually some other person points it out for me. I need to work on this by embracing the Sherlock's quote : "When you have eliminated the impossible, whatever remains, however improbable, must be the truth"
Thank you for breaking my false assumption.
Thanks for the amazing editorial!
I don't understand why my solution for C didn't work. It passed the first test case fine, and was very similar to the expected output for the second testcase, so I was wondering where I went wrong.
The fifth character is different.
Problem C. Decreasing String ***** In this problem test number 2 in test case 5. The string is given "pbdtm" and the POS=8 If I select s1=pbdtm s2=pbdm s3=bdm s4=bd s5=b The condition is still right. Because s1>s2>s3>s4>s5 And the POS value of 8 is 'd'.. But why this is wrong answer?
$$$s_2 = \tt{bdtm}$$$, not $$$\tt{pbdm}$$$
i'm having same problem just wondering why ( s1= pbdtm -> s2 = pbdm )is not valid ???
The problem statement says that we always need to make the next string lexicographically minimal.
From $$$\tt{pbdtm}$$$ we could go to $$$\tt{pbdt}$$$, $$$\tt{pbdm}$$$, $$$\tt{pbtm}$$$, $$$\tt{pdtm}$$$ or $$$\tt{bdtm}$$$. The lexicographically smallest one of these is $$$\tt{bdtm}$$$.
We cannot go to $$$\tt{pbdm}$$$, since $$$\tt{bdtm}$$$ is lexicographically smaller.
Got it ! , thanks man
Thanks you so much.. actually I misunderstood the problem statement
Problem B — Fear of the Dark
We can solve this problem using binary search as well.
Let's define a function f(w) which will return true or false for a particular radius w. True means for that particular w (w > 0), there is a path from point O to point P which is completely illuminated, and vice versa. If you observe the return of function by increasing the value of w gradually, you will notice this monotonic pattern [0 0 0...0 1... 1 1 1] where 0 means false and 1 means true. Here we can easily apply binary search to find the first 1.
Now how to write the function? Case 1: If both the points O and P lie inside any of the light of radius w, return true. Case 2: If both the circles intersect and the point o and point p lie inside any of the lights, return true, false otherwise.
Implementation (C++) 227374949
I'm still not getting one case. For which i didn’t able to solve the problem. Suppose the lanterns are so much far fron point o and p but they are closer to each other, i mean points a andb. But now if we take the distance between a and b and divide by 2, how is this can be answer. Because point o and p are not inside them, the are not covered. Can anyone explain?
Great idea for E, thanks a lot for the wonderful contest :)
You can also solve problem B by binary search. By the way, problem c editorial is great,thanks:).
I tried to solve it using binary search 247760061, but getting a TLE though. can someone please help me figure out why?
Change while to for(int i=1;i<=200;i++) and set high to 1e9 and you'll pass this question!
Thanks. It worked 248056414.
So, was that because there will be so many real values between the extremes?
And we are can get to an approximate value in < 200 iterations?
I think it's possible that the way your code is written could have some precision issues causing it to get stuck in a dead loop. In fact, we would halve the search each time, and even 100 searches would be enough to achieve the precision needed for the question.
(I'm sorry my English is not good, the above is the result of using a translator, I hope you can read it:)
Yeah, got that man.
Thanks, I was able to read through.
come on
Nice editorial
Awesome Editorial and Problem set.
Can someone help me with understanding my solution to B more clearly? I tried using binary search by answer here. I felt it was a plausible solution since if a radius (say r) is an answer then all radiis > r are also the answer. I tried implementing some solution, didnt work, maybe my impl on binary searching for real answers suck. Help/Correction appreciated!
In theory binary search should be possible here, even if I don't think it makes the problem easier to solve than the direct solution.
Problem 1: istouch() is wrong. You need to square the distance at the left-hand side (as you do in check()), or take the square root of the righthand side (hypot() is useful here).
Problem 2: isok() is wrong. You need to check four possible paths: O->A->P, O->B->P, O->A->B->P, and O->B->A->P. The first two subexpressions (
check(a,o,w) & check(a,p,w)
andcheck(b,o,w) & check(b,p,w)
) cover the first two possibilities. The third expression doesn't really work. instead ofcheck(b,p,w) | check(a,p,w)) & (check(b,o,w) | check(a,o,w) & istouch(a,b,w)
you need something like(check(b,p,w) | check(a,p,w)) & (check(b,o,w) | check(a,o,w)) & istouch(a,b,w)
(note the different places of the parentheses!)(Also, generally don't use
&
and|
for Boolean logic. Use the proper Boolean operators&&
and||
instead. But that's not causing any bugs in this case.)can you please help me with my submission too 247760061
For problem E, I was able to squeeze in what I think is an $$$O(m \times 2^m \times \sqrt{n})$$$ solution that doesn't precompute the number of programmers needed to satisfy a project: 227729256
Not sure if this was intended to pass or not!
after contest is completed. now i can understand the editorial for Problem C. Does it happen to anyone? Am it the only one who face difficulty to understand just after the contest.
227807811
Could somebody tell me what is the case I am missing out in the code ?
my logic: first expand the circle(with minimum radius) until both the starting and ending point are in some circle(boundary).
check if both points lie in a single circle, if yes, we got the answer
if not, the points are in separate circles, we need to check if there is a need to make the circles touch, or it already is touching or overlapping.
Please help me in Problem C ,I am facing runtime error on testcase 8 . Below is my code :
include<bits/stdc++.h>
using namespace std;
void solve(string& str,long long pos){ if(pos<=str.size()){ cout<<str[pos-1]; return; }
}
int main(){ std::ios::sync_with_stdio(false);std::cin.tie(nullptr); long long n; cin>>n; while(n--){ string str; cin>>str; long long pos; cin>>pos; solve(str,pos); } }
For Problem F, the editorial states that when "when you move a camera of type 2 to the first block, it can force multiple cameras of type 3 into the second block". I'm unable to see why this is true.
It seems to me that from the way we pick the camera of type 3, after a single move, it will fix all the $$$x$$$ which have $$$d_x - x > 0$$$. Because after moving the camera of type 2 from block2 to block1, we might cause several indices to have $$$d_x - x = 1$$$ (and not any value higher than $$$1$$$), which can be fixed by a single camera move.
Good question, it was one of our main points of concern while designing the solution (we weren't sure if it is necessarily to change the positions of multiple cameras of type $$$3$$$). This is because, when you move a camera of type $$$2$$$, it increases $$$d_x$$$ by $$$1$$$ on some suffix of values. But when you "move" a camera of type $$$3$$$, it actually stays in the first block (we still have to hack it before stealing the first diamond). It just has a bigger range of possible positions. So, it decreases $$$d_x$$$ on some suffix, but increases $$$d_x$$$ back on some shorter suffix (i. e. it just decreases $$$d_x$$$ by $$$1$$$ on one subsegment, not on the whole suffix). If there are multiple points where $$$d_x - x$$$ became positive after we moved a camera of type $$$2$$$, some of them might be outside that affected segment.
For 1886D - Monocarp and the Set, I have implemented the same logic as given in the editorial. We have to print the number of ways before and after the modification in the string, so first I calculated the number of ways to order the integers $$$1,2,3...n$$$. Then, while modifying the string, if we add a new $$$?$$$ in the string at index $$$i$$$, I am multiplying the previous number of ways with $$$i-1$$$. If we remove a $$$?$$$ from the string, there are two cases if the index is $$$1$$$ or not. If the index is $$$1$$$, then I am calculating the number of ways as I calculated in the beginning and if the index is not $$$1$$$, then I am just dividing the previous number of ways by $$$i-1$$$. This gives me the correct answer for test cases$1$ and $$$2$$$, but the code is failing for the $$$3$$$^rd test case.
Could anyone look at my code 228305867 to point out the issue?
In F why "if we skipped some camera which could be inserted into the first block, and chose some other camera for the same slot, they can be "swapped". " is right?
I think if we first insert the camera which $$$s_i$$$ is small and then insert the camera which $$$s_i$$$ is big,for the second block it is greater,but for the first block it is not greater than we first insert the bigger one.
BledDest
Suppose we already placed cameras of type $$$1$$$ and $$$2$$$, and try to place cameras of type $$$3$$$. Why is it always optimal to do it in non-descending order of $$$s_i$$$, and place a camera only in the first block (instead of placing it in both) whenever possible?
Suppose we fixed an optimal placement of cameras, and it differs from the one produced by that greedy algorithm. Let's fix the first (in sorted order) camera $$$i$$$ that would be placed in the first block by the greedy algorithm, but is not placed there by the optimal solution.
There should be a moment of time (some $$$x$$$ seconds before stealing the first diamond) where we would place that camera $$$i$$$ in the first block in the greedy solution. So, the condition $$$s_i \ge x + len$$$ must hold. If there's no camera of type $$$3$$$ occupying that moment, then we just place that camera $$$i$$$ there and remove it from the second block.
If there is such a camera, suppose its index is $$$j$$$. We can show that if we place the camera $$$j$$$ in both blocks, and the camera $$$i$$$ in the first block only, nothing will break: we can place the $$$j$$$-th camera in both moments of time occupied by the $$$i$$$-th camera, and the $$$i$$$-th camera in the slot of the $$$j$$$-th camera:
By repeating this process enough times, we can transform the optimal solution to the solution produced by the greedy approach, and nothing breaks.
Thanks very much!
Can anyone help me to find why is it wrong in th case 16 of the problem E: https://codeforces.me/contest/1886/submission/228496275
Obviously, the programmers that you finally choose are the biggest ones, so you should sort them decreasingly instead of increasingly before DP. Otherwise it means that you assumed choosing the smallest one, making it not optimal sometimes.
e.g.
2 1
1 3
3
Thank you so much!
Hi, can anyone explain for D, (TestCase 1, before all queries.)why the permutation 2, 1, 3, 5, 4, 6 is not possible ?
Maybe I am missing something, but the sequence is <?>?>
when you add 3, it becomes maximum so it shouldn't be a question mark, but rather a '>'
Oh, I see now. Thank you Vanjanja.
For C, I did an answer using the quadratic equation that avoids data structures, but it has a runtime error on test 8, don't know why :(
for question C you should put a hint (use a stack) as only knowing this information made me solve it
overall, good question and perfect tutorial thanks
In problem $$$C$$$, I was wondering what if we had some $$$Q$$$ queries, where each query is asking the character at queried position and length of string as ($$$N < 10^6$$$).
Roms
Another approach for problem A which is more concise 248334395