SRM 643

div1 250: The one with factorization

Factorize `2 <= N <= 10^18`, but half of the vector containing the sorted prime factors is given to you as the input. (The even-indexed ones) For example, 18 = 2*2*3, the prime factors vector is {2,2,3}, which means that the input will be 18, {2,3}, get it?

Factorization is supposed to be a hard problem. And for `N <= 10^18` it is, specially given the constraints, not so much the 2 seconds execution constraint, but the 256 MB memory constraint, the available time to code stuff and the lack of being able to save useful stuff in hard drive before running each test case... I mean, the *n*x* factor command can certainly factorize some large numbers, but you are supposed to do things the manual way here rather than reuse code..

So factorizing `N` is out of the question, maybe that's why it has to include some factors in the input. My first instinct was to think, well, just divide `N` by the known prime factors, the remaining value `n` shall be small enough to factorize, right? This is false. Just imagine `N` equal to 2 multiplied by a large prime number close to `10^18 / 2`. The large prime number would be a bit too large to do the `O(sqrt(N))` factorization by trial division algorithm we normally use.

Second idea was to do some ad hoc things. If there is only one prime factor provided, it means the number of prime factors is either 1 or 2, these are both easy cases to solve (result is either `{"primes"[0]}` or `{"primes"[0], N/"primes"[0]}` ). But this doesn't help. Cases in which the input has more than one factor can still lead to a rather large `n` after dividing: `999999999999999896 = 2 * 2 * 2 124999999999999987`.

So the solution is based in the following logic: The very last prime number in the factorization can be rather large `O(N)`, large, but if it is really so large, it will be the only such large number in the factorization. If this number is in an odd position, it will be ignored, and the resulting `N` after dividing by the known factors will be large because it includes this prime number. So the idea (which may not be 100% correct) is to just do trial division up to the `sqrt(2000000000)` and then, if there is still a number after dividing that much, what's left ought to be a prime number, right? I have no idea how good this is.

typedef long long int64;
#define long int64
struct TheKingsFactorization
{
    vector<long> getVector(long N, vector<long> primes)
    {
        long n = N;
        for (long p: primes) {
            n /= p;
        }
        //for (long p = 2; p * p <= 2000000000LL; p++) {
        for (long p = 2; p * p <= n; p++) {
            while (n % p == 0) {
                n /= p;
                primes.push_back(p);
            }
        }
        if (n > 1) {
            primes.push_back(n);
        }
        sort(primes.begin(), primes.end());
        
        return primes;
    }
};
#undef long

I suspect there will be many challenges in the challenge phase. I prepared up some cases, it's unlikely I'll get to use them, because Petr is in my room. Finished typing this as the coding phase ended. Let's see what happens.

SRM 640 : Do I still have write access here?

It's SRM 640, that means there have been 140 SRMs since SRM 500, remember SRM 500? It was fun.

Div1 250: The one with Trees

You have a bunch of stars with different colors. Use Ribbons to connect the stars, so that the ribbons and stars make a tree (connected, no cycles). Only some specific pairs of stars may be connected. Return the minimum number of ribbons connecting two stars with equal colors we should use.

So... isn't this the very definition of the minimum spanning tree problem? You need to find an undirected tree, with a minimum sum of used edge costs. Just make an edge cost 1 if the two stars it connects have the same color.

So just implement Prim's or Kruskal's Minimum Spaning Tree algo. I went for Kruskal because I am odd.

class ChristmasTreeDecoration:
 def solve(self, col, x, y):
    n = len(col)
    # I like python for things like this, create a list of edges (c,u,v) c is cost
    edges = [ ( int(col[i-1] == col[j-1]), i-1, j-1) for (i,j) in zip(x,y) ]
    
    # Precarious union find thingie 
    parent = range(n)
    def getParent(x):
        while parent[x] != x:
            (x, parent[x]) = (parent[x], parent[parent[x]]) 
        return x
    
    # Kruskal:
    total = 0;
    for (cost, u,v) in sorted(edges):    #sorting edges by cost
        if getParent(u) != getParent(v): #distinct components
            parent[getParent(u)] = v     #connect them
            total += cost                # add cost
    return total

After coding this and realizing it is super short and elegant I starred at the screen for a while. Skeptical that this was so easy. 250s lately are harder than this. I also doubted for a while if my getParent(x) function is bugged or not. Normally I use a stack to move all x to have parent[x] = the super grand parent. But this seems to work fine.

Div1 550: The one with bipartite graphs

You are given `n_1,n_2,a,d`, `n_1,n_2 <= 1000000000` return the maximum number of edges in a graph with `n_1+n_2` vertices, where each vertex has degree of at least `d` and the maximum bipartite matching is `a`.

So yeah... this problem exists. I am sure there has to be some sort of solution.

Div1 1000:

Another problem that probably has a solution. My hunch is that this one is rather easy once you do plenty of math.

Challenge phase

Nothing to report.

Let's see if that 250 survives.

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.