SRM 631 : A new arena

Remember when I wrote blog posts periodically? Remember when I actually had energy to have an explanation ready just by the end of the match? Remember when editorials weren't super late? It was a nice time for sure.

Participated in Topcoder SRM 631 . It was a special match because earlier this week the Web version of the Topcoder arena was released (in beta). There is actually a thing in which if you use the arena in SRM 631 or 632 and fill a survey you can maybe, if you are super lucky, maybe, win a ticket to the TCO. So I decided to use it in these matches. The new Arena currently lacks many features. And I have the impression that there were some few wasted opportunities in regards to how it was designed. I will focus this post on what I experienced about the new arena. If

Registration

I was very busy in the morning finishing the first part of SRM 630 editorial (log in required, which is terrible). I've had a very bad streak with my editorial work. First I was actually solving the problem in SRM 629 quite fast, even figured out div1 medium by myself and all, but the div2 hard got me stuck for too long, so long that SRM 630 started. I made the foolish decision to finish 630 before taking back to work in 629., thinking that at least then only one editorial will be late. That was a very bad decision because it turns out that div2 hard and div1 medium were both the same problem. One with a very easy solution that I couldn't understand for over a week, not helped by a paper that made me feel dizzy when reading it...

The short story is , I was busy and distracted so when it came time to register for the match , I forgot to use the web applet (I was already using the Java one, because I needed to test the SRM 630 problems and the web applet doesn't have practice or plugins). Lucky because it turns out that people who tried to register using the web Arena had issues.

One of the Use Cases I had in mind regarding the web arena was the ability to register to the match from a mobile device. You cannot run the Java Arena in Android or iOS. Unfortunately, my attempts to load the arena in Android Firefox were futile and I didn't have time to unfreeze the Google Chrome Android app so I could test it.

I really hope that whatever issue is making it so hard for the web app to load in mobile browers (or maybe just Mobile Firefox) is eventually not a problem. Will make sure to report once I have more info.

The match

I opened the web arena and looked for a way to enter my room. In the competition room, you meet this:

It actually took me a while to find the problem links. They are in the right. The web arena actually shows you the problem names before you open the problem. This has interesting consequences. Remember that the submission score starts to drop the instant you open a problem, so in topcoder matches we tend to try to solve one problem at a time and usually it is best to start with the easiest (lowest score) problem first. Some problem names are very descriptive , however, so maybe if a problem hints you up that the solution will be too easy or too hard for you the problem names are useful information. Or maybe disinformation if the problem name is not that good. Also, in some cases the problem name can give you a hint of who is the writer of the problem...

I don't really like that you need to click "Unopened" to open the problem. It is just not intuitive. I would have preffered an [open] link/button and some test below problem name to indicate if you already opened. Optimal would be to show the problem score, decreasing real time.

I open the div1 easy problem, remember that I am in low energy mode. It took me a while to read the statement. In this problem, you have to turn a board containing either Black or White cells into a board such that, for each column, the maximum number of consecutive cells (in the column) of the same color is `N/2`. A step consists of picking a row and either painting all white cells black or all black cells white. Note that this is the same as painting the whole row white or black. Return the minimum number of moves. I was trying to solve this problem when I noticed something was missing : The constraints. Turns out that the problem statement didn't display them... This is the kind of bug that we could have caught before the match if there was a practice feature - Just saying.

So I needed to open the problem in the Java arena to read the constraints (If the maximum `N` is 8 the problem is straightforward, if the maximum `N` is 1000 it would be very difficult to make it run in time, Constraints are everything). Logging in the Java arena forces the web arena to close. Logging in the Web arena causes the Java arena to freeze. Both arenas need a constant connection, and I was hoping the web one didn't (maybe make it so having a constant connection enables chat and real time score update but is optional).

On the bright side, having to open the problem in the Java arena meant that the Greed plugin would generate test code for me.

How to solve div1 250

The constraints were: Matrix is size `N times N`, `N ` is even, `N <= 50`.

I think the key here is to understand how the columns work. There can only be at most one group of more than `N/2` consecutive cells of the same color in a single column. If no such group exists, we can ignore the column. So we end up with a problem in which each column has a group of at least `N/2 + 1` that we need to cut. The cool property here is that at least 2 rows will be shared by ALL of these groups. Even in an extreme case, if there were 2 groups in two columns, one group was topmost and the other bottommost and the number of consecutive equal colors was `N/2+1` in both columns; even in this case, the two groups would share two rows. It is nice that there will always be two shared rows, because we can always just paint one of them white and the other black and it will be enough to "cut" all the columns. In short: We can always solve the problem in 2 steps. So we only need to worry about two special cases : a) If the board is already correct then the result is 0 steps. b) Maybe the board can be solved in a single step, pick one of `O(n)` rows and paint either completely black or completely white and check if the board is correct. This leads to an `O(n^3)` algorithm.

class TaroJiroGrid:
 def getNumber(self, grid):
    n = len(grid)
    # result is at most 2
    res = 2
    
    def goodGrid(g):
        def goodColumn(i):
            last = '!'
            x = 1
            for j in xrange(1, n):
                x = x + 1 if g[j][i] == g[j-1][i] else 1
                if x > n / 2:
                    return False
            return True
        
        return all(goodColumn(i) for i in xrange(n))
    
    if goodGrid(grid):
        return 0
    
    for i in range(n + 1):
        for color in ('W', 'B'):
            ngrid = [ grid[j] if i != j else color * n for j in xrange(n) ]
            if goodGrid(ngrid):
                return 1
            
    return 2

So I still had to open the web arena, paste the code and submit... But first I wanted to test in the arena. I noticed something cool, unfortunately the screenshot wasn't saved for some reason. Each example had a checkbox next to it. Then there was a [Test All] button. So you can test multiple examples at once. Thus killing one of the main reasons most people use plugins... Unfortunately, when I tried to do this I had an error that EXACTLY ONE example must test. Apparently this is a bug.

The rest

I opened div1 500. Seemed difficult. Then I went to eat. Came back and Tried to chat in the arena, but scrolling text in the chat box turned out to be very difficult. I hope this gets fixed.

I wish the new arena didn't forcefully require a constant connection. It is very annoying to log back in when your internet has a small hiccup... Also hope that whatever makes me unable to use it in mobile gets fixed (either the browser or the arena, will research more later).

Random screenshot with some glitches:

Some of the glitches are my fault : I force a minimum font in the web browser. Some seem to have been caused by slow internet or something.

SRM 629: A mistake

I think reading the problem statement is half the batte. Or actually, understanding the problem statement is half the battle.

Div1 250: The one with a rectangular hole

You have a rectangular hole of some possibly large dimensions. Also some boards that you can use to cover the rectangle. The boards are rectangles themselves. They may be rotated and overlap. But all of their corners must lie strictly outside the whole. Also the sides of the boards must be paralel to the sides of the hole. I put emphasis in all because I spent most of the match with the ridiculous assumption that only one of the corners must be outside the hole. This assumption makes no sense to be made because the statement is quite clear. I have no idea what happened, but this other variation of the problem seems very difficult, might even be impossible with the given constraints :/. Also note that the corners do not need to be put in integral coordinates, the statement doesn't mention this explicitly but an example needs this. Of course, you return the minimum number of boards needed to cover the rectangle. There are up to 50 boards.

So the trick to this problem is to notice that with the corner constraint, then all boards must be put in sequence either horizontally or vertically . Overlaps are not helpful. With this knowledge, we can first try horizontally and then vertically. As easy as swapping the dimensions of the rectangle, so we first try with W = holeW, H = holeH and then with H = holeW, W = holeH. The idea is that each board's height must be strictly larger than the hole's height (H). Then the board will cover a part of the width. Just find the top X possible widths, if those widths can cover the whole width W, then you have a result `t`. Note that when choosing each board's width and height we need to pick a good rotation...

import itertools

INF = 10**9

def minimumNumberInf(holeH, holeW, boardH, boardW):
    res = INF
    for (W,H) in ( (holeH,holeW), (holeW,holeH) ):
        # all vertical
        def correctWidths():
            for (wr,hr) in zip(boardH, boardW):
                best = -1
                for  (w,h) in ( (wr,hr), (hr,wr) ):
                    if h > H:
                        best = max(best, w)
                yield best
    
        widths = sorted( [ w for w in correctWidths() if w != -1 ] )
        
        if sum(widths) >= W:
            r = next( t for t in itertools.count(1) if sum(widths[-t:]) >= W )
            res = min(res, r ) 
    return res


class RectangleCovering:
 def minimumNumber(self, holeH, holeW, boardH, boardW):
    r = minimumNumberInf(holeH, holeW, boardH, boardW)
    return -1 if r >= INF else r

Because of the interpretation mistake, I took way too long to solve this problem. I also started the match a bit late so I didn't have time to read div1 500 either :/