Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
t = int(input())
for i in range(t):
n = int(input())
x = list(map(int, input().split()))
if n > 2 or x[0] + 1 == x[-1]:
print('NO')
else:
print('YES')
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int l, r, L, R;
cin >> l >> r >> L >> R;
int inter = min(r, R) - max(l, L) + 1;
int ans = inter - 1;
if (inter <= 0) {
ans = 1;
} else {
ans += (l != L);
ans += (r != R);
}
cout << ans << '\n';
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (adedalic)
fun main() {
repeat(readln().toInt()) {
val (n, k) = readln().split(" ").map { it.toInt() }
val a = readln().split(" ").map { it.toInt() }.sortedDescending().toIntArray()
var score = 0L
var rem = k
for (i in a.indices) {
if (i % 2 == 0) {
score += a[i]
}
else {
val needed = minOf(rem, a[i - 1] - a[i])
a[i] += needed
rem -= needed
score -= a[i]
}
}
println(score)
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const string vars[] = {"BG", "BR", "BY", "GR", "GY", "RY"};
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int t;
cin >> t;
while (t--) {
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
char s[5];
cin >> s;
a[i] = find(vars, vars + 6, s) - vars;
}
vector<vector<int>> lf(n), rg(n);
for (int o = 0; o < 2; ++o) {
vector<int> last(6, -INF);
for (int i = 0; i < n; ++i) {
last[a[i]] = (o ? n - i - 1 : i);
(o ? rg[n - i - 1] : lf[i]) = last;
}
reverse(a.begin(), a.end());
}
while (q--) {
int x, y;
cin >> x >> y;
--x; --y;
int ans = INF;
for (int j = 0; j < 6; ++j) {
if (a[x] + j != 5 && j + a[y] != 5) {
ans = min(ans, abs(x - lf[x][j]) + abs(lf[x][j] - y));
ans = min(ans, abs(x - rg[x][j]) + abs(rg[x][j] - y));
}
}
if (ans > INF / 2) ans = -1;
cout << ans << '\n';
}
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
const int N = int(1e7) + 43;
int lp[N + 1];
vector<int> pr;
int idx[N + 1];
void precalc()
{
for (int i = 2; i <= N; i++)
{
if (lp[i] == 0)
{
lp[i] = i;
pr.push_back(i);
}
for (int j = 0; j < pr.size() && pr[j] <= lp[i] && i * 1ll * pr[j] <= N; ++j)
lp[i * pr[j]] = pr[j];
}
for (int i = 0; i < pr.size(); i++)
idx[pr[i]] = i + 1;
}
int get(int x)
{
if(x == 1) return 1;
x = lp[x];
if(x == 2)
return 0;
else return idx[x];
}
void solve()
{
int n;
scanf("%d", &n);
int res = 0;
for(int i = 0; i < n; i++)
{
int x;
scanf("%d", &x);
res ^= get(x);
}
if(res) puts("Alice");
else puts("Bob");
}
int main()
{
precalc();
int t;
scanf("%d", &t);
for(int i = 0; i < t; i++) solve();
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (auto& x : a) cin >> x;
vector<int> p(n + 1);
for (int i = 0; i < n; ++i) p[i + 1] = p[i] + a[i];
map<int, int> cnt;
long long ans = 0;
for (int len = 0; len <= n; ++len) {
for (int i = 0; i <= n - len; ++i) {
int s = p[i] + p[i + len];
ans += len;
ans -= 2 * cnt[s];
ans -= (s % 2 == 1 || !binary_search(p.begin(), p.end(), s / 2));
cnt[s] += 1;
}
}
cout << ans << '\n';
}
}
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;
const int D = 10;
const int INF = 1e9;
typedef array<array<int, D>, D> mat;
mat mul(const mat &a, const mat &b, bool fl){
mat c;
forn(i, D) forn(j, D) c[i][j] = INF;
if (fl){
forn(i, D) forn(j, D){
c[j][i] = min(c[j][i], min(a[j][0] + b[0][i], a[j][i] + b[i][i]));
c[j][0] = min(c[j][0], a[j][i] + b[i][0]);
}
}
else{
forn(i, D) forn(j, D){
c[i][j] = min(c[i][j], min(a[i][0] + b[0][j], a[i][i] + b[i][j]));
c[0][j] = min(c[0][j], a[0][i] + b[i][j]);
}
}
return c;
}
struct minqueue{
vector<pair<mat, mat>> st1, st2;
void push(const mat &a){
if (!st1.empty())
st1.push_back({a, mul(st1.back().second, a, true)});
else
st1.push_back({a, a});
}
void pop(){
if (st2.empty()){
st2 = st1;
reverse(st2.begin(), st2.end());
st1.clear();
assert(!st2.empty());
st2[0].second = st2[0].first;
forn(i, int(st2.size()) - 1)
st2[i + 1].second = mul(st2[i + 1].first, st2[i].second, false);
}
st2.pop_back();
}
int get(){
if (st1.empty()) return st2.back().second[0][0];
if (st2.empty()) return st1.back().second[0][0];
int ans = INF;
forn(i, D) ans = min(ans, st2.back().second[0][i] + st1.back().second[i][0]);
return ans;
}
};
mat tran[D];
void init(int d){
forn(i, D) forn(j, D) tran[d][i][j] = INF;
for (int i = 1; i <= 9; ++i){
tran[d][i][i] = i;
tran[d][i][0] = i;
}
tran[d][0][d] = 0;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
for (int i = 1; i <= 9; ++i) init(i);
int n, k;
cin >> n >> k;
string s;
cin >> s;
minqueue q;
forn(i, n){
q.push(tran[s[i] - '0']);
if (i - k >= 0) q.pop();
if (i - k >= -1) cout << q.get() << ' ';
}
cout << '\n';
return 0;
}
finally it is released.!!!
In D, also you can use bellman-ford after construct a graph: 276620074
can you explain your construction of graph?
The implementation / logic of F makes me feel I am the dumbest man on planet.
Same, it is very unintuitive for me how you can just add the cumsums; This implementation makes a lot more sense to me: 276838911
can someone explain to me what is wrong with my solution of problem C : 276692116
It is actually causing Overflow, check your output. You can see negative value. When we add positive numbers, we can never get negative values, unless you got memory overflow.
yeah, in accumulate i had to write 0ll instead of just 0. Thanks.
I faced something like this... maybe using Long Long can fix it.
Hello ..
Can anyone tell me that for problem D , why this solution is giving wrong answer https://mirror.codeforces.com/contest/2004/submission/276820238 or can anyone suggest some test cases where this failed
You can actually find the failing test yourself.
Checker's output says "wrong answer 248th numbers differ — expected: '3', found: '-1'". That means you only need to add something like "if (test_id == 248) then print(all input)" to your code (and don't print anything else so that the output is not too large). The verdict will still be WA but at least you'll get to see the problematic test.
damn, i was actually looking for something like this thanks
It says 248th number, and not 248th testcase. So we don't know which testcase number it really falls under :(.
Then you could replace test_id == 248 with query_id == 248
you are considering wrong combination of string to search. i.e) if temp1 is RY and temp2 is BG then your first combination would be RB which is not possible
Take a look at Ticket 17471 from CF Stress for a counter example.
finally the text editorial is here, still waiting for rating recalculation :(
can anyone tell why this solution for problem D is giving tle ?
youre using maps and sets a bit too much probably
ig time complexity is O(q*4*log(n)) which should not give TLE
ohh yeah, you just have to add & before st "for(auto st:mp[a[x]])", i just added the & and it passes 276829023. by adding &, you iterate over the elements by reference which is much faster.
change auto st to auto& st
why did problem E get so much hate and backlash ? the problem is actually really nice and high quality even tho there were 10+ videos that leaked the solution first hour which had nearly 5k views combined that doesnt take from the quality of the problem i honestly found it really interesting and gives a new way of approaching problems atleast for me
I said the same in original Contest post. and guess what, heavily downvoted. I would say it again. E was a nice problem.
i think they are missing the core idea tbh i always underrated trying to prove facts from realizing a pattern but this problem proves that sometimes looking at the pattern and trying to build intuition then proving it (proofs for this problem are really easy and i 100% believe most experts+ will be able to reason enough to prove the pattern) actually is a valid idea and sometimes solves even hard problems
ik this is off topic but wow dude how did you go from grey to purple in less than a year? as someone who's given about 5 contests it looks lowkey impossible for someone like me
it also looked impossible for me after 5 contests but after 60 u will realize its not
In the editorial for problem F, it is written that: "It can be shown that it doesn't matter which of these actions we take".
Please mention in the editorial how it can be shown. I have an intuition for this, but I don't have a rigorous proof.
i dont get this part aswell if u understand it please explain it below here
A rigorous proof would be something like that:
Consider the prefix sums of an array, and denote $$$s$$$ as the sum of all elements in it. An array of positive integers is palindromic if and only if its prefix sums are "symmetric" with $$$\frac{s}{2}$$$ as the center (i.e. if an integer $$$\frac{s}{2} + x$$$ exists in the array of prefix sums, then the integer $$$\frac{s}{2} - x$$$ should also exist, and vice versa). If there is a pair $$$(\frac{s}{2}-x, \frac{s}{2}+x)$$$ such that only one of these elements exists in prefix sums, this pair violates the condition, and we need to "fix" every such pair.
Now consider what our actions do to the array of prefix sums. When we merge two adjacent elements, we delete a prefix sum. When we split an element, we add a new prefix sum between the existing two. Every such action can "fix" one of the violating pairs $$$(\frac{s}{2}-x, \frac{s}{2}+x)$$$: merging two elements deletes one element from a pair, and splitting an element adds an element into the pair. So, if we have a pair that violates the condition, it doesn't matter whether we fix it by split operation or merge operation — we will still spend one operation to fix this pair.
Any idea why this submission for Problem D is going TLE? As per my understanding, the time complexity for this should be O(q * 6 * logn) which should be within limits I guess. Thanks in advance!
https://mirror.codeforces.com/contest/2004/submission/276826924
Ok I see, issue was with 1., deep copying of vector. 2. Solves it. So dumb, it was going to be the first time I solved a D in div 2!!
1.vector<int> nodes = colorToNodes[all_colors[j]];
2. vector<int>& nodes = colorToNodes[all_colors[j]];
I thought of applying dfs for D but will it give tle?
probably yeah
Yes. If you're checking every possible index, then time complexity will be approximately O(N*Q) because in the worst case, let's say, you will be getting the same x and y each query, and every other string will be suitable. Then, for each query you will be checking N-2 elements. Rounding up, it is N*Q
It will be o(nq) so yeah
Can someone tell me why my code here isn't necessarily correct? 276831391
I understood the idea quite well, as you essentially need to check if there exists a city in between x and y, as well as if the closest two cities not in the range to x and y respectively, but I'm not certain why my above submission is WA, while this submission 276831747 is.
Thanks in advance :D
Take a look at Ticket 17468 from CF Stress for a counter example.
I see, I understand what I was doing wrong now. In my head I thought I was checking the two possible city locations, but I guess my code didn’t reflect that :/. Thank you very much!
Idk how the B task was for you guys. But for me, as a beginner, it's very tricky.
To be honest, I was also confused by this problem. I tried to solve it by math first, but decided to just write brute force.
Hello ...
https://mirror.codeforces.com/contest/2004/problem/D
Could anyone tell why this is giving TLE for Problem D and how could i improve .