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

Linux Mint - Good Surprise

It's been a time since I became orphan of Gnome 2. I was a big fan of everything there, and I don't like the way Gnome 3 and KDE are going to, with 'modern' user experience and interface, It's really annoying for me, so I decided to experiment the Cinnamon, along with Linux Mint. It was definitely an great surprise, It does almost everything our good'n'old Gnome 2 did, with cool themes and windows, rolling smooth and without apparent bugs. I don't see myself using a different graphic desktop environment so far. 

Google Code Jam - Qualification Round 2013

Hello, I'm writing now laying in my bed, after some hours struggling with the contest problems, so, I'll be direct.

Problem A - Tic-Tac-Toe-Tomek
This problem turned out to be a 4x4 version of a Tic-Tac-Toe problem, it implementation it's quite simple, I managed to spent a lot of memory creating a bunch of sets, you only have to watch out about the order to check the possible outcomes, misunderstand the order to check incomplete games and draw games can manage for a wrong solution, a poor O(N^2*log(N)) works:

Problem B - Lawnmower
This problem is also simple, but requires a little attention for a fast solution. Analyzing some possible outcomes for the lawnmower routes, you can cleverly figure out that for an position '[i][j]' inside the matrix, if this position has an block with a higher height both above and below, and some other position in it's sides has an height higher than the value in position '[i][j]', the field is invalid. This rule can be applied in the 'inverse' form, considering higher values in it sides, and one possible value above or below, the code runs comfortably in O(N^3):

Problem C - Fair and Square
Here comes the trouble, the first time I read the problem, I just got scarred about a case with astronomic values (10^100). Then I noticed simpler cases with lower constraints (10^14), I pre-computed the possible values for this fair and square numbers up to 10^14 and then, sought their bounds with binary search, I think there's pattern within these numbers that I unfortunately couldn't find, so, I'm looking forward to see the 'non-brute-force' solution for this problem:

Problem D - Fair and Square
To be honest, I'm reading this problem statement right now, something involving maximum flow and dynamic programming pass by my neurons. I'm thinking about a breadth-first-search storing the actual states of the 'graph', this solutions clearly won't fit in the large input limits, unfortunately I only have spare thought now, maybe next time;

Latin American Summer School

Hello, I'm here today to write about the Latin American Summer School for the World Finalists of the ACM/ICPC. The goal of the school was to train the teams for the World Finals, but it was open for non-finalists teams too. As I didn't managed to get a team to go with my university so I got a remaining spot in a team from Universidade Federal de Campina Grande. We stayed for two weeks in Campinas, which is by the way, a lovely city.

The school worked as follows, we arrived at 8 o'clock for a breakfast and then for a 3 hours class, then after a lunch, a 5 hour contest to train our skills on the given subjects. I've enjoyed and learned a lot there, the infra-structure of Unicamp is amazing, so we had classes and contest in a good environment. I'd like to thanks Unicamp and the organizers of the event, as well the professors which were Fidel Shaposnik in the first week and Jakub Radoszewski in the second one, and of course, my team mates from UFCG.

Here are the links for the training held in the first week, the second week ones will be posted soon, as the professor used a different contest environment:

http://ahmed-aly.com/Standings.jsp?ID=3595
http://ahmed-aly.com/Standings.jsp?ID=3608
http://ahmed-aly.com/Standings.jsp?ID=3644
http://ahmed-aly.com/Standings.jsp?ID=3655

SRM 563 - The redemption

Hello again, it's been a time since I took part in a official SRM (the last one was SRM 559), and it was held in an atypical afternoon here in Brazil, I've just moved, and my home is a mess, I registered early and went to the kitchen, when I got back to computer, the round was about 5 seconds to start. 

Starting to talk about the problems itself, I started opening 250, it was an really easy problem, different from the last rounds when the easy problems weren't so easy (solvable in a few minutes). The problem asked whether given 2 strings S and T if it's possible to mix to copies of string S so the string becomes equals to T, as the problems asks for only two copies of S, then it's solvable in O(N) being N the length of string S:

Until the submission for problem 250, the arena was working normally, even with the problem with the examples combo box which doesn't keep track of your last tested example and always get your first example  tested by default (in the arena older versions it didn't happened). Then, opening the problem 550, I received the annoying message 'you can only see one problem at time' (I don't remember the message at all but it's something like this), than I had to log off to open the problem again, while coding, there were times when I had to wait more than a minute for a compilation, which made my submission way lower than it should be.

The problem starts talking about a game with two coins in a board, consisting of empty cells '.', obstacles '#' and, you 4 options of plays, move both coins for north, south, east or west, making a move you change both coins to a single direction, if any coin move to a cell with an obstacle, it simply doesn't move. The goal of the game is to move only one single coins out of the board. My solution was an Breadth-First-Search though the graph, using a state of the number of moves, and the location of both coins, simulating the goal of the game:

I'm yet thinking of a state for a dynamic programming solution for problem 1000, it'll be in a edit when available.

I ended up with an +109 rating and becoming green again, I'm pretty happy with good rating after a bad score record.

Considerations and Tutorial of TopCoder SRM 532

Hi everybody;

Today's SRM was quite exciting, the problem set was tricky but nice, an easy 250, and not too difficult but with some tricky test cases 500 and a harder than usual 1000 which until now I didn't thought in any possible "in-time" solution, I guess it's because I'm really bad in dynamic programming.

I'll write a brief tutorial about this round problems which I was able to solve, in the contest time, I just solved the 250 one, who was quite easy, but in less than 5 minutes in practice room, I solved the 600 problem without issues.

250:

Reading the statement carefully, it's easy to notice that the approach is:
Find the Maximum and Minimum values of the array, theses values are the minimum possible bound for the set; then check all the values between this whole set who's not in the array;

My solution in the actual contest is ridiculous expensive but here is an O(N * log(N)) solution:

In the 600 the idea is quite simple get all the 'non-rusty' chain links, and then, get the most profitable prefix and suffix. It can be done straightforwardly, but the trick starts with possible chains as '9.9' where the link can be both the best prefix and suffix, as we have only two end points "prefix and suffix" we can brute force this two possibilities which I called 'prefixBeforeSuffix' and 'suffixBeforePrefix', which ended up in a O(6*(N*3)) solution, running smoothly under Topcoder time limits.