Blog

Congratulations to the new Studio champion – abedavera

Posted by on Wednesday , November 13th, 2013 at 9:21 pm

It has been announced! The new TCO Studio champion is Junius [abedavera], from Indonesia. Congratulations!!!

Looking good, brotha!

(more…)

Mod Dash final final results :)

Posted by on Wednesday , November 13th, 2013 at 9:01 pm

Spoiler alert, supercharger won!

There were not many changes in the last round.

Most competitors had passing submissions for the first easy problems. This meant that whoever was the fastest won the points but the number of points were relatively low. The submissions for the hard problems with few submissions had the potential to change the structure of the leaderboard but did not.

This is the final standing:

 

So the final winner is supercharger.

Congratulations!! Great work.

 

Alogrithm Finals Medium Problem PackingSquares

Posted by on Wednesday , November 13th, 2013 at 7:40 pm

PackingSquares

(by vexorian)

Problem Statement

Manao is given a sequence of squares numbered from 0 to N-1. The i-th square has side length equal to 2^a[i].In the beginning, there is only an empty plane. Manao will process the squares one after another, in the order in which they are given. He will pick a parent object for each of the squares and then move the square onto its parent object. The parent object can be either the plane or one of the already processed squares. Each square must lie entirely within (or exactly cover) its parent object. Also, the children of an object must not intersect the other children of the same object.Given an int[] a, return the minimum possible covered area of the plane that satisfies the above conditions.

Notes

The answer will always fit in a signed 64-bit integer.
For the purposes of this problem, the square is defined as the set of interior points, i.e., the edges are excluded.

Constraints

a will contain between 1 and 50 elements, inclusive.
Each element of a will be between 0 and 30, inclusive.

 

Analysis

We say a square has size x if its side length is `2^x`. A square of size x has space equivalent to 4 squares of size x-1.

If we set a square as a parent to another square k, the space available in the first square may no longer be available for squares larger than k. It is also not always better to assign the largest possible child square, because the order might stop us from filling the parent square with smaller ones. A good strategy that is guaranteed to work is needed.

In reverse

A very useful idea is to consider the squares in reverse order. Consider a square i and ignore all squares that come before it. This means that this square cannot have a parent (yet). We should imagine square i forcefully in the plane. Since we have already processed squares with indexes larger than i, there will also be some squares currently in the plane – that were not assigned a parent yet, but we should assume that when we processed the squares with index larger than i, we did so in the optimal way.

(The image shows that some of the squares in the plane may already contain some children, but the example of children squares is possibly not optimal).

If assignments of children to the higher indexes were optimal, we shouldn’t modify them. The only way to modify them would be to move these children to square i, that would definitely not be a good idea, as the children already do not use any space. This would only decrease the space available inside square i.

So the only allowed move is to assign some of the squares that currently do not have a parent to become children of i. In this case our objective is to reduce the area of squares without parents to make it the least possible.

  • The maximum amount of area we can save up is `4^x`. We cannot save more than that. Now imagine if there was another square of size x without a parent. We could assign this other square as the single children of square i. This move is optimal because it reduces the maximum area possible.
  • If there are no squares of size x, then we can open up 4 spaces available for squares of size (x-1). If we can fill these spaces with those squares, that would be optimal. Or we can try to fill with as many such squares as possible. Then there will be some remaining t spaces of size (x-1) that were not used. We can multiply t by 4 to get a new number of spaces for squares of length x-2. And we can repeat this process until all possible spaces are used, giving priority to larger squares.

This strategy yields the optimal way to assign parent-less squares to become children of i. We have already shown that we should leave the other parent-children untouched if we assume that the assignments we did for indexes larger than i were optimal. Thus the assignment for all indexes from i to n-1 is optimal now. When we solve for i-1, we can use the same strategy, and so and so until we reach the very first index: 0. This shows that the strategy should always yield a correct result. 


Code

MAX_BITS = 30

class PackingSquares:
 def leastArea(_, a):
    # we initialize the number of squares of each size that do not have a parent
    q = [0] * (MAX_BITS + 1)
    for x in reversed(a): #visit the squares in reverse order
        t = 1 #initially, there is a single square of size x
        for y in reversed(range(x+1)):
            m = min(t , q[y])   #Assign available space to new children
            t -= m
            q[y] -= m
            t *= 4              #remaining space multiplied for 4 for the next, smaller size.
        q[x] += 1 # add the new square to the plane
    #Return the total area used by squares without parent:
    return sum( 4**j * q[j] for j in range(len(q)) ) 

#NewFaces at #TCO13

Posted by on Wednesday , November 13th, 2013 at 7:12 pm

In the last months I’ve been running interviews to Studio members coming out to the surface by their outstanding performance and skills improvement, new faces. It’s funny how things work, on this TCO we receive two new first timer finalists: kelvinwebdesign and iMadReactions.

There are other active Studio members here. We have the supper happy soul of CoralBlue. I finally met someone that can be crazier than me (in a happy way)! From Bulgaria, we have jivkoss who won a trip with the TCO video contest. Also, picachui, one of the top wireframe designers.Interesting thing, MonicaMuranyi is here too but she is competing at Mod Dash, how cool is that?

And finally, ChristinaLi, she came to visit us, such a great girl. It’s glad to meet new faces and have them joined to the wave!

You can’t miss the opportunity to know more about them:

ChristinaLi, mahestro, iMadReactions and kelvinwebdesign

CoralBlue and jivkoss

Algorithm Finals to Start – Live Video!

Posted by on Wednesday , November 13th, 2013 at 5:24 pm

Here we are at the finale of the algorithm track that started with 1,000 or so coders. The top 8 are preparing their environments as I type. You can watch in the arena, via the live streaming video, starring past TCO champion John Dethridge and follow misof’s live play-by-play blog on Google Drive. Get the story from one that knows from the inside, what it like. You will be able to see the problem statement in the forum and the problem analyses on this blog once the match starts. Also follow

After the final we will  have a short pause and then start the awards presentations. The winner of the algorithm and marathon tracks will be announced then.

[Update: we will not publish the problem statements and analyses at the start due to technical difficulties. But we will publish them soon after the match.]

This is it – the Mod Dash is over

Posted by on Wednesday , November 13th, 2013 at 3:05 pm

The last problem proved to be a hard nut to crack as well.

Very little submissions and the competitors didn’t look very confident. Some of them were relieved that the “hour” is over.

This is the partial standing.

 

We know all the the results at the award ceremony.

supercharger has the most chances to win but moulyg can him catch especially if his 4th submission passes which will bring him a cool 100 points.

But he also needs chance for that to happen. Akinwale is also in a good position with a 1st on the 6th problem.

Considering that the 4th and 6th problems were not trivial, I would not be surprised if we get some failed submissions.

 

Like they say, the devil is in the details 🙂

Mod Dash Round 3 last problem

Posted by on Wednesday , November 13th, 2013 at 2:57 pm

Looks like the 5th problem was a really tough one and the trend is starting to look like yesterday :(.

No competitor was able to submit a solution in the 10 minutes time they had available.

On a side note I noticed a lot of glitches. It seems that the pdf from Monica Muranyi is always opening after one minute of “thinking”. I don’t know how much of a difference it makes but it must be really frustrating.

 

The 6th problem seems to be easier (but apparances sometimes deceive). The competitors have to add a products detail page like the following:

 

Mod Dash Round 3 – problems 4 and 5

Posted by on Wednesday , November 13th, 2013 at 2:47 pm

Problems are getting harder and hard. For the 4th only moulyg managed to submit.

From what I have seen from looking at the screens of the competitors there are a lot of indentation errors. Please please use 2 spaces instead of tab (4 spaces).

The 5th problem requires the implementation of a search box functionality.

Mod Dash Round 3 – problem 3 standing

Posted by on Wednesday , November 13th, 2013 at 2:35 pm

Everyone submitted for the first 2 problems.

The standing looks like the following:


The 3rd problem proved to be more difficult with “only” 4 submissions. Anyway this is a record compared with the previous round :).

In this problem the requirements were about adding a listing of featured products:

 

Mod Dash Round 3 – Problems 1 and 2

Posted by on Wednesday , November 13th, 2013 at 2:20 pm

The problems this round are definitely more “approacheable”.

The first problems required competitors to add a map to the contact us page.

The 2nd problem required the addition of the About page.

With all the submitters sending their solution for the first problem and almost all having already sent it after 5 minutes it looks like the difference will be made by speed and by attention to details. Although the requests seem pretty straightforward it is easy to miss something small and lose the all the points.

Here is the standing at the middle of the 2nd problem: