### awoo's blog

By awoo, history, 14 months ago, translation,

1837A - Grasshopper on a Line

Idea: BledDest

Tutorial
Solution (awoo)

1837B - Comparison String

Idea: BledDest

Tutorial
Solution (BledDest)

1837C - Best Binary String

Idea: BledDest

Tutorial
Solution (Neon)

1837D - Bracket Coloring

Idea: BledDest

Tutorial
Solution (BledDest)

1837E - Playoff Fixing

Idea: BledDest

Tutorial
Solution (awoo)

1837F - Editorial for Two

Idea: BledDest

Tutorial
Solution 1 (awoo)
Solution 2 (awoo)
• +63

| Write comment?
 » 14 months ago, # |   0 another solution for F. my code
•  » » 14 months ago, # ^ |   0 you can speed up the 'cal' function by using binary lifting
 » 14 months ago, # |   +3 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.
•  » » 14 months ago, # ^ |   +1 https://codeforces.com/contest/1837/submission/207216020Keep a running sum of the string: "(" is +1, ")" is -1. Mark anything positive as 1, mark anything negative as 2. It's that simple.
 » 14 months ago, # |   0 Is the D question simpler this time?
•  » » 14 months ago, # ^ |   +9 very much
 » 14 months ago, # |   +10 $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
•  » » 14 months ago, # ^ |   0 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.
•  » » » 14 months ago, # ^ | ← Rev. 3 →   +10 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.
 » 14 months ago, # | ← Rev. 2 →   +1 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.
•  » » 14 months ago, # ^ |   0 Thanks.I agree with your insight.
 » 14 months ago, # |   +5 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
 » 14 months ago, # |   0 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
 » 14 months ago, # | ← Rev. 2 →   +5 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 middlecoloring all '(' in the left side using color 1.coloring all ')' in the right side using color 1.coloring all others using color 2.
•  » » 14 months ago, # ^ |   0 Why does it work?
•  » » » 14 months ago, # ^ |   0 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.
•  » » » » 2 months ago, # ^ |   0 a+c=b+d=n/2 (that is,the total count of the leftside equals to the rightsideHow? And Why?
•  » » 9 months ago, # ^ |   0 Great！
 » 14 months ago, # |   -16 I think the tight limitation in problem F is unnecessary. My $O(n \log^2 n)$ solution got TLE on test 23.
 » 14 months ago, # | ← Rev. 2 →   0 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
•  » » 14 months ago, # ^ |   0 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
•  » » » 14 months ago, # ^ |   0 Thanks for the reply, can you provide a test case for that where it is not valid.
•  » » » » 14 months ago, # ^ |   0 1 4 3 2 3 2 4 Answer should be 4, but if you remove the max element the best you can do is 5.
 » 14 months ago, # |   0 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
•  » » 14 months ago, # ^ |   0 Greedy doesn't work. See above for a counter test case
 » 14 months ago, # |   0 Is C question was only on observation??
 » 14 months ago, # | ← Rev. 2 →   0 You can write F in $O(n~log^2~n)$ — 208816454Also the solution works fast (1590ms)
 » 12 months ago, # |   0 the third test case in problem C is incorrect1??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
•  » » 12 months ago, # ^ |   0 the cost is still 1 reverse the substring (0, 4)
 » 8 months ago, # | ← Rev. 2 →   0 Can someone please explain how the answer of E for test case3-1 7 -1 8 2 -1 -1 5is 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?
•  » » 7 months ago, # ^ | ← Rev. 2 →   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.
»
4 weeks ago, # |
0

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; }
}