Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
for _ in range(int(input())):
x, k = map(int, input().split())
if x % k != 0:
print(1)
print(x)
else:
print(2)
print(1, x - 1)
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
for(int i = 0; i < t; i++)
{
int n;
cin >> n;
string s;
cin >> s;
int ans = 1, cur = 1;
for(int i = 1; i < n; i++)
{
if(s[i] != s[i - 1]) cur = 1;
else cur++;
ans = max(ans, cur);
}
cout << ans + 1 << endl;
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
char x = '0';
for (auto& c : s) {
if (c == '?') c = x;
x = c;
}
cout << s << '\n';
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
for(int i = 0; i < t; i++)
{
int n;
cin >> n;
string s;
cin >> s;
vector<int> bal(n + 1);
for(int j = 0; j < n; j++)
if(s[j] == '(')
bal[j + 1] = bal[j] + 1;
else
bal[j + 1] = bal[j] - 1;
if(bal.back() != 0)
cout << -1 << endl;
else
{
if(*min_element(bal.begin(), bal.end()) == 0 || *max_element(bal.begin(), bal.end()) == 0)
{
cout << 1 << endl;
for(int j = 0; j < n; j++)
{
if(j) cout << " ";
cout << 1;
}
cout << endl;
}
else
{
cout << 2 << endl;
vector<int> ans;
int cur = 0;
while(cur < n)
{
int w = (s[cur] == '(' ? 1 : 2);
do
{
cur++;
ans.push_back(w);
}
while(bal[cur] != 0);
}
for(int j = 0; j < n; j++)
{
if(j) cout << " ";
cout << ans[j];
}
cout << endl;
}
}
}
}
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 MOD = 998244353;
int main() {
int k;
scanf("%d", &k);
vector<int> a(1 << k);
forn(i, 1 << k){
scanf("%d", &a[i]);
if (a[i] != -1) --a[i];
}
int ans = 1;
for (int st = k - 1; st >= 0; --st){
int big = 1 << st, fr = 0;
vector<int> na(1 << st);
forn(i, 1 << st){
int mn = min(a[2 * i], a[2 * i + 1]);
int mx = max(a[2 * i], a[2 * i + 1]);
if (mn == -1){
if (mx >= (1 << st)){
--big;
na[i] = -1;
}
else if (mx != -1){
na[i] = mx;
}
else{
na[i] = -1;
++fr;
}
continue;
}
if ((a[2 * i] < (1 << st)) == (a[2 * i + 1] < (1 << st))){
puts("0");
return 0;
}
na[i] = mn;
--big;
}
forn(_, fr) ans = ans * 2ll % MOD;
for (int i = 1; i <= big; ++i) ans = ans * 1ll * i % MOD;
a = na;
}
printf("%d\n", ans);
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution 1 (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
int t;
scanf("%d", &t);
while (t--){
int n, k;
scanf("%d%d", &n, &k);
vector<int> a(n);
forn(i, n) scanf("%d", &a[i]);
vector<int> pr(n + 1), su(n + 1);
auto check = [&](long long x){
forn(_, 2){
priority_queue<int> cur;
pr[0] = 0;
long long cursum = 0;
forn(i, n){
cur.push(a[i]);
cursum += a[i];
while (cursum > x){
cursum -= cur.top();
cur.pop();
}
pr[i + 1] = cur.size();
}
reverse(a.begin(), a.end());
swap(pr, su);
}
reverse(su.begin(), su.end());
forn(i, n + 1) if (pr[i] + su[i] >= k) return true;
return false;
};
long long l = 1, r = accumulate(a.begin(), a.end(), 0ll);
long long res = 0;
while (l <= r){
long long m = (l + r) / 2;
if (check(m)){
res = m;
r = m - 1;
}
else{
l = m + 1;
}
}
printf("%lld\n", res);
}
}
Solution 2 (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
int t;
scanf("%d", &t);
while (t--){
int n, k;
scanf("%d%d", &n, &k);
vector<int> a(n);
forn(i, n) scanf("%d", &a[i]);
vector<pair<int, int>> xs(n);
forn(i, n) xs[i] = {a[i], i};
sort(xs.begin(), xs.end());
forn(i, n) a[i] = lower_bound(xs.begin(), xs.end(), make_pair(a[i], i)) - xs.begin();
vector<int> lstpr(n), lstsu(n);
forn(_, 2){
set<int> cur;
forn(i, n){
auto it = cur.insert(a[i]).first;
if (it == cur.begin())
lstpr[i] = n;
else
lstpr[i] = *(--it);
}
swap(lstpr, lstsu);
reverse(a.begin(), a.end());
}
vector<int> pr(n + 1), su(n + 1);
vector<int> prv(n + 2), nxt(n + 2);
auto check = [&](long long x){
forn(_, 2){
int cnt = 0;
prv[n + 1] = n;
nxt[n] = n + 1;
pr[0] = 0;
int mn = 1e9;
long long cursum = 0;
forn(i, n){
if (mn < a[i]){
pr[i + 1] = cnt;
continue;
}
nxt[a[i]] = nxt[lstpr[i]];
prv[nxt[a[i]]] = a[i];
prv[a[i]] = lstpr[i];
nxt[prv[a[i]]] = a[i];
cursum += xs[a[i]].first;
++cnt;
while (cursum > x){
mn = min(mn, prv[n + 1]);
cursum -= xs[prv[n + 1]].first;
prv[n + 1] = prv[prv[n + 1]];
nxt[prv[n + 1]] = n + 1;
--cnt;
}
pr[i + 1] = cnt;
}
reverse(a.begin(), a.end());
swap(lstpr, lstsu);
swap(pr, su);
}
reverse(su.begin(), su.end());
forn(i, n + 1) if (pr[i] + su[i] >= k) return true;
return false;
};
long long l = 1, r = 0;
for (int x : a) r += xs[x].first;
long long res = 0;
while (l <= r){
long long m = (l + r) / 2;
if (check(m)){
res = m;
r = m - 1;
}
else{
l = m + 1;
}
}
printf("%lld\n", res);
}
}
another solution for F. my code
you can speed up the 'cal' function by using binary lifting
My solution for D, based on some observations.
First of all check whether it is possible to make any coloring at all. This can be checked by just checking the balance of the whole string. If it's 0(basically equal number of '(' and ')') then coloring it is always possible, either as an RBS or as an reversed RBS or both. Only thing left to check is the number of colors.
For this we can start pairing up the brackets(since there are equal number of brackets of both kind). We start by pairing the first '(' with the first ')' and color them based on a condition that if ')' comes before '(' then its reversed otherwise normal. This pairing will always result in either an RBS or an reversed RBS(try it out!).
For example suppose we had colored this set: (()((())))
and when pairing them according to this algorithm we had paired the first '(' with the first ')' even though for an RBS that is not the correct pairing. But still as a whole the string is an RBS!
I haven't yet figured out a proof for this observation and will appreciate any and all inputs, but I found this a much simpler solution to code for D.
https://codeforces.net/contest/1837/submission/207216020
Keep a running sum of the string: "(" is +1, ")" is -1. Mark anything positive as 1, mark anything negative as 2. It's that simple.
Is the D question simpler this time?
very much
$$$O(nlogn)$$$ is possible for F. We just iterate over all possible splits of array and try to greedily balance the sums between prefix and suffix. My solution
Could you pls explain why it's nlogn? It's not obvious to me that your inner "while" loop does constant (maybe amortized?) number of iterations.
Both while loops will be called at most $$$O(n)$$$ times:
First one exchanges greatest element in multiset $$$ms$$$ with smallest one in $$$ms3$$$. Such moment that $$$ms3$$$ has smaller element than the greatest in $$$ms$$$ happens only whenever we expand prefix (which will only happen $$$O(n)$$$ times). It is quite obvious to see that there will be at most one such exchange after expansion of the prefix, so making it a while loop is quite redundant. Here's a accepted submission with an if statement instead of a while loop.
Second while loop is easier to analyze since we may notice that it always increases $$$ms$$$ size by one and we are never decreasing it. Since $$$ms$$$ size is bounded by number of elements in input array, then again we get at most $$$O(n)$$$ calls.
In the tutorial for problem E, there is a statement that says:
If both or neither of the teams are from 1 to 2^k, then the answer is immediately 0.However, it seems that the correct statement should be:
If both or neither of the teams are from 1 to 2^(k-1), then the answer is immediately 0.or I didn't understand that part.
Thanks.I agree with your insight.
Problem F was qutie educational! I solved it with a binary search too, but instead of a bs over the answer, I used some segment trees to simulate like a frequency sort (using something similar to coordinate compression), then I binary seach on the amount of elements I take from the left $$$x$$$ and $$$k-x$$$ from the right, and similar to the editorial, the prefix sum from the left increase and the prefix sum from the right decrease, so we look for a balance (let those values be close as possible). Complexity: $$$O(n\log n \log n)$$$ (fast enough jeje) Solution
I managed to solve F using ternary search and binary search on segment tree. I had to make some hacky optimization to fit it in TL (3992ms)
207420100
my solution for D:
it is easy to check whether it is possible to make any coloring.
if the answer is yes,check whether it is possible to coloring using 1 color;
if it can't,the answer is 2.
an easy way to coloring is:
first,cut the string half from the middle
coloring all '(' in the left side using color 1.
coloring all ')' in the right side using color 1.
coloring all others using color 2.
Why does it work?
if it is possible to make coloring,it can be showned that the counts of '(' on the leftside equals to the counts of ')' on the rightside.
prove:consider that
the counts of '(' on the leftside = a.the counts of '(' on the rightside = b.
the counts of ')' on the leftside = c.the counts of ')' on the leftside = d.
than a+b=c+d=n/2 (that is,the total count of '(' equals to the total count of')' )
a+c=b+d=n/2 (that is,the total count of the leftside equals to the rightside.)
so a=d&b=c.
it means that the sequence of color 1:"(((())))" with (a) '(' and (d)')'
the sequence of color 2:"))))((((" with (b) ')' and (c)'('.
it's easy to showned both sequences is beautiful.
a+c=b+d=n/2 (that is,the total count of the leftside equals to the rightside
How? And Why?
Great！
I think the tight limitation in problem F is unnecessary. My $$$O(n \log^2 n)$$$ solution got TLE on test 23.
In Problem F why the approach in which we remove maximum (n-k) elements and then minimizing the sum of k elements is not valid
We are finding some $$$min(max(a,b))$$$. Minimize $$$a+b$$$ does not necessary give the optimal answer. Take an example of $$$5 + 8 = 13$$$ and $$$7 + 7 = 14$$$, even though the sum is higher, we get a better result
Thanks for the reply, can you provide a test case for that where it is not valid.
Answer should be 4, but if you remove the max element the best you can do is 5.
Hey, can anyone tell me why my solution for question F is incorrect. I first found the k smallest element in o(nlogn ), then I put these in original order. I precalculated the sum of array and took a variable h=0; Then I iterated for n times the array , in which I did h+=a[i] and found minimum=min(minimun,max(h,s-h)); It should be done in o(nlogn). Here is my code
Greedy doesn't work. See above for a counter test case
Is C question was only on observation??
You can write F in $$$O(n~log^2~n)$$$ — 208816454
Also the solution works fast (1590ms)
the third test case in problem C is incorrect
1??10? given this pattern would not 111100 be a better answe because the cost is 1 (just reverse the whole string)
instead we have 111101 as the correct answer where the cost is 2
the cost is still 1 reverse the substring (0, 4)
Can someone please explain how the answer of E for test case
3
-1 7 -1 8 2 -1 -1 5
is 4. Here team 2 and team 4 are going to play together in first round, so team 4 for will be eleminated quarter finals. So shouldn't the answer is 0?
I made the same mistake as you: each term $$$a_i$$$ is the team that has seed i, not the seed that the team i receives.
If I take int ans = INT_MIN; why the answer is wrong ?
include <bits/stdc++.h>
using namespace std;
int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; for(int i = 0; i < t; i++) { int n; cin >> n; string s; cin >> s; int ans = 1, cur = 1; for(int i = 1; i < n; i++) { if(s[i] != s[i — 1]) cur = 1; else cur++; ans = max(ans, cur); } cout << ans + 1 << endl; }
}
.