awoo's blog

Educational Codeforces Round 149 Editorial
By awoo, history, 19 months ago, translation, In English

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)
  • Vote: I like it
  • +63
  • Vote: I do not like it

Comments Comments (36)
| Write comment?
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

another solution for F. my code

→ Reply
»
19 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the D question simpler this time?

→ Reply
»
19 months ago, # |
  Vote: I like it +10 Vote: I do not like it

$$$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

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
      ← Rev. 3   Vote: I like it +10 Vote: I do not like it

      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.

      → Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
19 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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.

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why does it work?

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        a+c=b+d=n/2 (that is,the total count of the leftside equals to the rightside

        How? And Why?

        → Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Great！

    → Reply
»
19 months ago, # |
  Vote: I like it -16 Vote: I do not like it

I think the tight limitation in problem F is unnecessary. My $$$O(n \log^2 n)$$$ solution got TLE on test 23.

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain why 207472463 is getting TLE in java, but same logic in C++ works fine 207473463

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The IO you are doing is slow; instead of Scanner, try BufferedReader,instead of System.out, Use PrintWriter.

    → Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the reply, can you provide a test case for that where it is not valid.

      → Reply
      • »
        »
        »
        »
        19 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it 
        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.

        → Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Greedy doesn't work. See above for a counter test case

    → Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is C question was only on observation??

→ Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You can write F in $$$O(n~log^2~n)$$$ — 208816454

Also the solution works fast (1590ms)

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the cost is still 1 reverse the substring (0, 4)

    → Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    11 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
9 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

isn't $$$E$$$'s complexity $$$O(k \cdot 2^k)$$$?

oh nvm I see what's going on there

→ Reply