Summer Training Camp

It's been a time since I don't post anything here, I've been participating actively in competitions, but seeing so more elaborated editorials floating around makes me less motivated to write. Within a few hours I'll be leaving for a 2 weeks training camp in Campinas, the second largest city in São Paulo. I'm looking forward to have a good time there and improve my coding skills, as well as posting updates about what's going on there.

SRM 594

Last Thursday's SRM was a rather unusual round, I don't know yet whether I made an improvement in my coding skills or both 250 and 500 problems were easier than usual and 1000 was harder than usual, with big constraints and xor operations, so will write the ones I managed to solve.

LittleElephantAndBallsAgain - 250

Given a string composed of 'R', 'G' or 'B', the problem asks for the minimum number of border removals to make the string with only one kind of character. As I'm in a dynamic programming moment, I ended up with a dp solution, stating the minimum value of a left removal or a right removal, as my code follows, but there's ways easier to code solution. Imagine that the string is composed of only non sequential characters ("RGBRGB") the obvious answer is (|string.length| - 1). Using a string ("RGBBBRG") as an example, i'ts clear that the best option is to remove both the prefix "RG" and the suffix "RG" to make a string containing only 'B' characters. With this in mind, it's clear that the best answer will be always (|string.length| - |length of the longest sub string with equal characters|).

My solution complexity: O(n^2)
Best solution complexity: O(n)

LittleElephantAndIntervalsDiv2 - 500

Given a sequence of |M| white balls and |N| intervals of the sequence to be painted of black of white, the problem asks the return the number of different sequences after |N| paints. With low constraints (N < 10 and M < 100), a complete search was clearly feasible. But with and clever idea, you can see that there's a finite number of balls to be painted, counting the number of balls that can be painted, we know that for them, there are 2 possible outcomes, paint black or white, resulting as (2^(|balls possibly painted|)).

My solution complexity: O(2^n)

Best solution complexity: O(n * log(n))

About SRM 585

Hello, competition is over and ratings started to change, I increased + 72 points, make me closer than ever to DIV 1. I'm quite excited.

LISNumberDivTwo:

The problem was pretty straightforward, it asked for the number of contiguous strictly increasing sub sequences. I unfortunately waste so many time coding a simple solution for this problem, thus, I managed to earn only 236.31 in a simple problem as this one.


TrafficCongestionDivTwo:

This problem required more analysis. The statement asks for the minimum number of 'cars' to be inserted in a complete binary tree, such that each car has a path (a paths can be empty) and no car paths intersect and each vertex must be visited by a car. As the problem statement illustration suggests, the optimal solution is to make from bottom to top, each card has a path of size 2, leaving a leaf note to a 1 step higher node and then to another leaf.

EnclosingTriangleColorful:

This problem is a tricky one, I managed to solve if in contest, but with a very unfeasible solution O(2^4 * (M - 2)^3 + (N log(N)). I'm trying to get a better solution that will be posted here.

Closer

Hi, I'm currently writing this post while finish some details in my tomorrow's presentation and watches the gazettE's last DVD. It's been a busy month, I didn't post anything about programming and even broke my compromise to solve at least 1 'medium' problem a day.

I really hope to be more active here in July, along to warm-up to the Brazil regional which will'be held in September, and probably to post about other topics besides programming competitions;

Feature

Hi, as everybody already know, Google Reader is gone, I'm replacing it with bloglovin' :) (I wasn't suppose to post it, but they obligate us to make a post with they 'follow me' url :()

Follow my blog with Bloglovin

Faceboook Hackathon São Paulo 2013

Hi, I've been very busy currently, so my posts are getting delayed too, I took part in this event about a week ago (04/05), but only today I got time to write about it (actually I don't have time, I should be doing school homework).

It was pretty much amazing, definitely a great experience, I'll write a little about how was this experience. It wasn't my first time in the big city, but I had never went to the neighborhood where Facebook's office is situated (Vila Olimpia). I went with a friend and he never traveled alone to São Paulo, so I made the role of guide. We leaved Taubaté about midday by bus, 2:45 o'clock and we arrived at Brazil's biggest bus station (Terminal Tietê), as the metro station is integrated with the bus station, It were easy to go around. As we arrived earlier, I had an idea to look for a place to buy new headphones, and take a look at a very cool 'sightseeing' place, Avenida Paulista. Summarizing, we walked about 40 minutes seeing everything around, I didn't found the headphones I wanted, and we arrived with 30 minutes of delay at the office.

Going to what really matters, it was an amazing experience, we built Nextrip, an app which suggest a place for your next trip, taking in relevance the places which your friends liked to visit, and other variables, the other competitors did an amazing job, and our app wasn't close from the winner one, unfortunately I forgot the name of the app, but they used graph search to make you able to choose which group of friends will see what you post (more info on Facebook Hackathon page) . Apart of this, the environment of Facebook's office is amazing, it's a very comfortable and cozy place, where you can work relaxed and in a good mood, all the engineers were helping us all the night out, and they all were super cool.

I really hope to be there next year.

Anxiousness

Hi. I'm very anxious for tomorrow, the 'Segunda Maratona Mineira de Programação' will happen. Originally the competition is only for universities in Minas Gerais state, but I asked for the event organizer to make us an exception to take part as an invited team, and he accepted, then, it's virtually our last 'real' training for the ICPC regional in September.

Wish us luck, I hope to be able to post the problem set and a possible editorial here as soon as possible