Saturday, October 26, 2013

SRM 595

I just finished the editorial for SRM 595: http://apps.topcoder.com/wiki/display/tc/SRM+595. Don't forget to vote.

It is a good moment to talk about the match.

During the match

Lately I am using the standard strategy: easy problem first, then medium, leave hard for when writing the editorial. My only twist is that I force a 5 minute break after every 25 minutes spent working on a problem (So it is the pomodoro technique applied to SRMs, giving it a try).

I opened 250, at first it seemed harder than it actually was. It turned out to be quite simple. But I did take longer than I hoped for. I actually had an unforeseen delay. I have been doing testing on the very unstable, cutting edge Greed plugin 2.0 alpha, and forgot to change it back to 1.5 before the match. I actually thought it would work all right, and it did, until I tried to submit and it was actually having issues there. Well, it was simple to change back to 1.5 but it did delay me for a bit.

I was actually lucky here because from the start I decided to use 1-indexed arrays to fill the colors. It is very rare I do this, but in this case it saved me from a potential bug because .size() in STL structures is unsigned (Which is VERY stupid, really, this is the worst good in ALL of the STL design). Apparently this issue hit many coders during the match.

I opened div1 500, and I tried to solve it. I wwas having issues because my idea of an approach was to cut the string in two, count the number of valid substrings in one half and the other and then combine the parts. This logic was more complicated than first picking the first substring and then counting the others, which I could only find later in the match. I spent all the coding phase trying to get it to work.

Challenge phase was a bit fruitless. But I was glad to find my code for 250 was one of the cleanest and not bugged.

Comments about the problems / editorial

Div2 easy: A bit harder than usual but a good pick.

Div2 medium: I don't see the need of making this a different problem than div1 easy (ok they are the same problem but with different constraints). I like to make fun of Java, and usually pick it only when I already plan to write c++ and python code and try to make the Java code as overloaded with tons of code as possible, just so that Java looks bad ^^.

Div2 hard: Ok problem, a bit too standard, but I think that's a good thing for div2 hard.

div1 easy: Ok for the slot

Div1 medium: It was a interesting one, I wish I solved it.

Div1 hard: Amazingly cool. When I first read the explanation rng_58 sent me (Which is almost exactly the same as the "short summary" in the editorial) I was a bit confused: WHAT TRIANGLES? WHAT IF THEY OVERLAP? IT DOESN'T MAKE SENSE. I had to spend all this day thinking about it and reverse-engineering his code. But once I noticed exactly what method to split by triangles is used, it is a very cool problem, refreshing, actually.

I intended to finish this editorial in 24 hours to save as much time as possible for a school assignment, I failed, as I actually took 50.5 hours, too bad.

2 comments :

Vijay said...

I read Div-1 500 point problem after the match and I think I got it in mind. I read the editorial and it confused a lot, more because it was too verbose and too much in detail than needed for this level. I just liked the code in there.

vexorian said...

I updated it trying to remove verbosity. But it has to be like like this because people that can't solve the problem by just looking at the short summary on top and the code probably need some guidance on how to calculate the needed integers.