awoo's blog

Educational Codeforces Round 114 Editorial
By awoo, history, 3 years ago, translation, In English

1574A - Regular Bracket Sequences

Idea: BledDest

Tutorial
Solution (BledDest)

1574B - Combinatorics Homework

Idea: BledDest

Tutorial
Solution (awoo)

1574C - Slay the Dragon

Idea: BledDest

Tutorial
Solution (Neon)

1574D - The Strongest Build

Idea: BledDest

Tutorial
Solution (awoo)

1574E - Coloring

Idea: Roms

Tutorial
Solution (Roms)

1574F - Occurrences

Idea: BledDest

Tutorial
Solution (BledDest)
  • Vote: I like it
  • +122
  • Vote: I do not like it

Comments Comments (70)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks :)

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

nice editorial, love the problems, appreciate it

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E, we only have to keep track of same-colour cells with an even number of cells between them?

What about differently coloured cells with an odd number of cells between them? Doesn't that force a strip of width two as well?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Same colour is just a special case like adjacent cells, mentioned to arrive to the checkerboard intuition which works both for same colour and opposite colour cases without distinguishing them.

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

      @maxplus can you explain Problem E. I am new to CP. Like for input 2 2 7 1 1 1 1 2 1 2 1 1 1 1 0 1 2 -1 2 1 -1 1 1 -1

      o/p: 3 1 0 1 2 3 6 why 1 1 1 gives 3 as o/p . Initially the matrix is empty so there are 2 ways to fill it, either 0 or 1. then the answer should be 2 right. Similarly for 2 1 -1 whey o/p is 3. 2,1 wasn't filled yet, so it can filled in 2 ways with 0 or 1.

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

        When the $$$2 \times 2$$$ matrix is empty, there are actually $$$6$$$ ways to fill it such that every square will add to $$$2$$$. Here are the options:

        Options

        So when we set the cell with coordinates $$$(1, 1)$$$ we get only first $$$3$$$ options out of the above.

        → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I guess * The row and columns containing the cells of same color with even number of cells between them; can be confusing, so you're right, it's lines containing cells that correspond to both (contradicting) checkerboard line colourings that should be tracked.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    OK, I implemented my own version and I think the code is a bit more self-explanatory. If anyone has trouble understanding Roms' implementation (as I did), then maybe looking at mine (129556708) will help.

    → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it -44 Vote: I do not like it

.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E. What is cntx[] in Roms's solution and why are we (--res) only if it [0,1] or [1,0]. Shouldn't we always (--res) because same starting position shared between p2[n-ur] and p2[m-uc]?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    cntx to the whole board as cntr to a row. If there is at least one strip, there are no colourings alternating nicely both vertically and horizontally so none are subtracted, and if no cells are coloured then there are two "shared" colourings.

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

      Thank you. Got it: cntr and cntc keep parity info for each col and row. While cntx keep parity for all board — how many of them correspond to their (virtual) color and how many doesn't. But what information does it provide us — why should we (--res) in case all {correspond} or all {notcorrespond}? It tells us if there can be shared state in the start — the position from which we can shift either vertical lines or horizontal. If there points in both {correspond} and {notcorrespond} positions — there cannot be such common starting position.

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a way of solving problem D with a trie?

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

    Yes, I solved D with Trie and DP (unfortunately I couldn't complete it during the contest).

    Here is the code

    The idea is put all the banned set into a trie. Then iterate through every possible prefixes. For each prefix, we will find the maximum possible suffix so that they will not form a banned set.

    For example we have a prefix of length $$$i$$$, there are 6 items for slot $$$i + 1$$$, current node has 3 children numbered $$$3$$$, $$$5$$$, $$$6$$$. So we may choose $$$4th$$$ item for slot $$$i + 1$$$ and choose whatever we want from slot $$$i + 2$$$

    The idea is simple but one should be careful while implement

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    As far as I can tell, I think I did it using a traverse of a trie structure without the structure itself. Take a look at my solution if you want to.

    129399828

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    you can check my implementation

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I saw everyone using PriorityQueue for D, can anyone explain that approach.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    People used a funky priority_queue based Dijkstra implementation! A very clever approach in my opinion.

    Each vertex is a build and each build is a vertex. However, these vertices aren't stored anywhere in memory but rather, they are procedurally generated. Two vertices (builds) are joined by an edge if and only if you get one of the builds by degrading exactly one item in the other build.

    Then, just implement a Dijkstra on these builds and remember to skip the neighbours of a vertex if the vertex is not banned, since the neighbours (degraded builds) can only be worse, as noted in the editorial.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    The idea is basically to store the build in the priority queue, and we use custom comparator so that builds in PQ are sorted according to their total strength. We add the strongest build first to the PQ (in this case, the last item in each slot). When PQ is not empty, check if its top is not banned, if so then we get the answer. Otherwise we iteratively swap an item in some slot for the one that is the previous one by power and add to PQ.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In D part,i did simple brute force approach with some sort of memorization. But to my extreme surprise the code got accepted.

129377465

By the way one of the best contest for me. This contest boosted my rating to a great extent.

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

    lol its giving TLE for me though. My submission : https://codeforces.me/contest/1574/submission/129585401. Update : yeah i got it why im getting TLE

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

      What was the reason for TLE in your case?

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

        for (; max[ind]>=0; --max[ind]) { solve(ind+1, max, pos, set); } this loop makes the worst case complexity to O(10^(5n)).

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

          I'm also getting TLE #6, but I haven't found the issue. Here's my code

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

            Oh, sorry man, I cant understand the operations which u have made since I dont know Java that much!!

            → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

great short approach for D

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody please explain why we do

if (ur.size() == 0 && uc.size() == 0)
    res = sum(sum(p2[n], p2[m]), -2);

and

if (cntx[0] == 0 || cntx[1] == 0)
    res = sum(res, -1);

in E? Thanks in advance.

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

    I do not understand what the variable names mean exactly but based on what I've written in my solution, the first bit of code should be the embodiment of the following train of thought:

    if there are no forced stripes (horizontal or vertical) and no rows or columns have any cell coloured in them (they are not set in place) then
the possible number of colourings is:
Assume there are horizontal stripes, that gives 2^n different colourings.
Assume there are vertical stripes, that gives 2^m different colourings.
But the two cases above share two colourings, which is the checkerboard pattern and the anti-checkerboard pattern, which have to be subtracted from the total.

    The second bit of code I couldn't decipher, but it's likely something similar.

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

    ur == used in rows; uc == used in columns. It keeps indexes of rows and columns that already used — ones that have 1's and 0's written in one of their cell.

    Now every possible permutation can be achieved in one of two ways: either by left-right shift/move of horizontal lines or by up-down shift/move of vertical line. And every shift is creating doubled-lines in that direction — except starting position end ending. They are identical (if we consider starting position — a permutation that looks like a chessboard, and ending position — 2^n or 2^m positions, when all rows or all columns are shifted (inverted chessboard)). This means that every vertical shift creates position unachievable by horizontal shift and vice versa. Except starting and ending positions — if we shift non vert (or all vert) — thay will be the same like if we would shift non (or all) horizontal. If both of ur and uc them is empty — we haven't written any numbers — both starting and ending positions are achievable, so we should substruct 2. If there at least one cell with written 1 or 0 — we wouldn't have same starting and ending position. We could maximum have only one of those 2 positions — corresponding to written number and its cell.

    cntx is variable that keeps count of <black & white> 'parity'. If you'll imagine an m*n chess board with black square in upper left corner (that is {1,1} coordinate), than you can say that cntx[0] is counting how many 0s you placed on black cell and 1s on whites. cntx[1] is counting how many 0s you placed on white and 1s on black. If there some 1s (or 0s) on both black and whites — there cannot be same starting and ending position. We should not decrease result by on. But if all 1's are on same color and all 0s on other — there could be match for one position — this position is both contained in sum(res, p2[m — uc.size()]) and sum(res, p2[n — ur.size()]), so we should substruct it.

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

      Sorry for asking noob question. I still don't understand why the total permutation is 2^n+2^m-2 (like the way to count up to a total of 2^n+2^m, then subtract 2 cases that is identical). Could you please explain in more detail with example.

      Now every possible permutation can be achieved in one of two ways: either by left-right shift/move of horizontal lines or by up-down shift/move of vertical line. And every shift is creating doubled-lines in that direction

      Thank you.

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

        I don't know what to add. If you imagine a chess board of m*n — any permutation is achievable either by moving some horizontal "zebra-lines" 1 square left (or right — it doesn't matter, they are indistinguishable) OR by moving some vertical "zebra-lines" 1 square up (or down — doesn't matter). There 2^n variants of horizontal shifts — each line either shifted or not. And 2^m verticals — same logic.

        If you observe 2^n horizontal shifting — there 1 "starting" position when none is shifted, and one "ending" position — when all shifted and chess board becomes inverted — they correspond to "starting" and "ending" position in 2^m vertical shifts. So those 2 should be substructed.

        Case with cntx and -1 is much more interesting :)

        → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D please help! Can someone explain me this statement, "The optimal answer can be one of only two types. Either it contains the last item of each slot. Or it's some banned build with one item swapped with the previous one.

I couldn't understand the 2nd part how the answer can be part of banned build with one swapped with previous one ?? Thanks in advance

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

    Suppose (b1,b2,b3,...bs) is a banned build.Then one of our possible candidate for the best possible build is (b1,b2,...bi-1,...bs), given bi>1.This build is adjacent to one of our banned build so if not banned too will be a potential candidate.

    → Reply
»
3 years ago, # |
← Rev. 6   Vote: I like it +9 Vote: I do not like it

I actually used $$$BFS$$$ to solve problem $$$D$$$. This might not be the fastest solution to implement, but I think it's easy to understand. Here's my idea.

The state of the $$$BFS$$$ is the array $$$b$$$, which is the index of items chosen on each slot. The value of the state is the sum of the chosen items. We start with all index maxed out for each slot and manually calculate the sum of all the last index as the value. Every time we transition to another state, we decrease one of the $$$b[i]$$$ by $$$1$$$, iterating $$$i$$$ from $$$1$$$ to $$$n$$$. Thus, the value would only be affected by one of the slot. To maintain the value, we need to remove the previous value and add the current value, i.e. the value would decrease by $$$a[i][b[i]]-a[i][b[i]-1]$$$ ($$$b[i]$$$ here is before we decrease by $$$1$$$). By using $$$BFS$$$, we will get the states in descending order without skipping any states. We should use max heap for the $$$BFS$$$ because we prioritize the higher sum. We would stop when the current state is not banned and output it as the answer.

Complexity Analysis: Since we would directly stop when it is not banned, the number of states visited would only be $$$O(M)$$$ at most. Since we use a priority queue and assuming we check a visited state using set/map, the complexity would be $$$O(N^2MlogNM)$$$.

My code: https://codeforces.me/contest/1574/submission/129387703 (Note that I used a slightly different value definition, which is the difference of the current sum with the maximum sum, but the main idea is still the same)

Edit: I miscalculated the complexity. Big thanks to maxplus for pointing this out.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Thank you so much, I was having the same approach but I was struggling very much implementing , you makes it looks so simple

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Glad to help!

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Sorry just wanna ask, I'm wondering why "Glad to help!" got so many downvotes. Is it insulting or negative in any way?

        → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +13 Vote: I do not like it

    Isn't it $$$O(N^2 M log N M)$$$? Although at most $$$M + 1$$$ states are extracted from priority queue, for each of them $$$O(N)$$$ children are processed in $$$O(N log N M)$$$ each.

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

      I see, my bad I think you're right, sorry I will fix that.

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

      I am thinking perhaps one could improve this solution's complexity by using hashing perhaps? Although in this problem, the N is small so it still passes the time limit.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        With hashing we'll process each child in $$$O(N)$$$ since worst case we need to create each of them, so $$$O(N^2M + NMlogNM)$$$ (in your solution you'll need to provide pq with a custom comparator so that it can ignore state). $$$N^2M$$$ is hard to shake off because it's also the space complexity independent of lookup algorithm. Instead of hashing we could visit children in such a way that each gets exactly one parent — we can stop generating children after we encounter the first not maxed slot, same complexity.

        If we use hashing, replace priority queue with queue, update best answer instead of terminating on the first not banned state and skip states whose children can't improve the answer, $$$O(N^2M)$$$.

        If we update hash in $$$O(1)$$$, update current best answer before placing a child into the queue and skip useless children (that aren't better than current best answer), we get $$$O(NM)$$$ but it becomes hard not to notice that only banned states are placed into the queue and we don't need queue at all.

        One also has to be careful with updating the best state if he wants to avoid $$$N^2$$$ (in the solution from the editorial too): if we assign it each time it gets improved, it can be up to $$$NM$$$ updates of length-N array.

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

          Nice! Thanks for the insight. I learn a lot even when my code have already got Accepted.

          → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will anyone help me in upsolving C problem. I find that the editorial is giving TLE. Please help me

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

    You may notice that test#5 has n = 2*10e5 took 1,7 secs. Test #6 has n = 2*10^5 size too (thought we don't know how big is m in both), but we can see that "a" now is not a bunch of 1s and 2s {1 2 1 2 1 2 1 2 ...} but big numbers like 873579811631 — which means they will took your algorithm longer to digest.

    Take a look at "fast input output c++" topic. Google it.

    And be sure to take a look at this.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Even though I have used binary search to find the heroes in question 1574C — Slay the Dragon it is giving TLE. Pls can someone check why is it giving so? my code is : 129554543

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

    Your input/output is too slow. This is caused by using iostream (cin/cout) with stdio (printf/scanf) synchronisation. Add the following lines to boost the speed considerably.

    ios_base::sync_with_stdio(0);
cin.tie(0);

    Beware, however, that this makes it dangerous to use cin/cout alongside printf/scanf.

    I submitted your code with these two lines and it works within the time limit (129564251), albeit still a bit slow.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey, can someone please explain Geothermal's approach to question D: https://codeforces.me/contest/1574/submission/129399246

It runs in approx 400 MS and my pq method is running in ~2900 MS: https://codeforces.me/contest/1574/submission/129568774

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

    A banned build is hashed into a pair in Geothermal's code. Your code just push the whole build into the heap, obviously it's much slower.

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

      https://codeforces.me/submissions/Ashishgup# see this, he simply uses set

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

        Yes, but he is not moving them through PQ.

        What is impressive — is his strange "recurse" function with quick return shortcuts. And strange line < ans &= (i + 1 == c[idx]); >

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

          yes :'), did you get his approach?

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

            Yes, he is doing kind-of-dfs until he finds allowed build where all except current node are ones. Than he goes one node up and trying do the same. He is looking into same node that stupid-bfs does, but in different order. Thought bfs has chance of early exit, so it might not visit every blocked build, and this approach does not.

            → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the problems. Regarding problem C: how does the last paragraph explain that achievable m values form a range? Could someone clarify? I am thinking of different proof: Consider a string of form C...CB...BA...A that has maximum possible value of m (as in editorial A <= B <= C). Then take A or B and put it between some 2 letters C. This decreases number of equal adjacent pairs by 2. If one needs to decrease number of pairs by odd number, just put the A or B at the beginning of the sequence. It will decrease number of adjacent pairs by one.

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

someone please explain graphical approach of D.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In B,

"Now build the string for m=0"

How to prove that we can always build for m = 0?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    This means we have to try to build the string with no repetition, for ex if we are given input as 5A 2B 1C and we try to build the string for m = 0. the string should look like this A__A__A__A__A as you can see we have 4 empty spaces but not enough B's and C's to make a string with no same adjacent letters.

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

Using banned builds to get good build is crazy idea[problem:D]

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

I have a different solution for D.

It's based on the fact that if you have two arrays a and b of lengths n1 and n2, you can build the largest m+1 sum pairs (out of n1*n2 pairs) using binary search. You can do this sequentially for every array or use divide and conquer to find all largest m+1 possible builds. One of them must be the answer as only m builds are banned.

Here is the implementation.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D. I have implemented the solution in the editorial, however, I'm getting TLE #6. Can anyone please take a look at my solution and figure out the reason for TLE? Thank you.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You never update your visited set

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

      OMG! So silly mistake. Thanks!! Giving a long break in competitive programming has shown itself.

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

How can we solve problem F using FFT?

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

If someone found the editorial solution of E trickier to understand, probably this might help.

Convention:

  • Stripe:- Band of alternate 0 & 1, eg: 0101010101.... or 1010101010...
  • RowStripe0: A stripe that starts with 0, and forms the row of the grid. Eg: 010101...
  • RowStripe1: A stripe that starts with 1, and forms the row of the grid. Eg: 101010...
  • Similarly, ColStripe0, ColStripe1
  • n: number of rows, m: number of columns
  • chess pattern: grid with chessboard pattern(first cell white)
  • anti chess pattern: grid with inverted chessboard pattern(first cell black)

Observations:

O1: A valid grid consists of either

  • Combination of n RowStripes: 2^n ways
  • or Combination of m ColStripes: 2^m ways
  • chess & anti chess patterns can be obtained by both 1) & 2)
    • # ways to form valid grids, when all cells are empty = 2^n + 2^m - 2

O2: As we can see we can segregate the answer into two-part,

  • Grids which are formed by RowStripes
  • Grids which are formed by ColStripes Thus, from now on, we treat them separately.

O3: Partially filled grid.

  • Say column c has some cells already filled.
    • Case 1: c has cells filled according to the chess(or anti chess) pattern only
      • Then, column c can have only one possible configuration. => # ways to form valid grid with ColStripes = 2^(m-1)
      • If such k columns are already filled => # ways to form valid grid with ColStripes = 2^(m-k)
    • Case 2: Column c has cells corresponding to both chess and antichess pattern
      • Then, we can't fill the cell c neither with ColStripe0 nor with ColStripe1 => # ways to form valid grid with ColStripes = 0. c is thus a bad_column
  • Similar derivation if some row r is filled
  • Collission case:
    • If the grid was completely empty then there were two collisions, as explained in O1.3
    • If the grid was partially filled
      • Case 1: If grid filled with either chess (or anti chess) pattern => Subtract 1 from final answer
      • Case 2: If grid is filled with both patterns => No subtraction is required, as chess or anti chess pattern cant be achieved together.

Code

  • C1 Mark columns that are already filled

    • For each column maintain whether it is filled in ColStripe0 pattern or ColStripe1 pattern

  • C2 Similar to C1, mark rows that are filled

  • C3 maintain bad_rows, bad_cols, empty_row, empty_cols

See implementation here: 130091893

(Solution was inspired by tourist's submission: 129358674)

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For the tutorial of problem E, how to understand "If there are two cells of same color in the same row with even number of cells between them then there is the vertical strip (because there are always two adjacent cells with same color between them)?" Can someone help me with an example？Thanks.

In my opinion, there is obviously a counterexample: 1 0 0 1 0 1 1 0 There are no vertical strips?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

On problem C:

Why we should only consider those 2 cases? Any proof on this?

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

    For the second case maximum $$$a$$$? One way might be to look at the two possible cases for $$$a<x$$$, $$$s-a\ge y$$$ and $$$s-a<y$$$ and the costs for each case, and costs against one another.

    → Reply