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

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