ACM ICPC Naga 2014 – Problem F: Diameter of a Tree

Dr. Manalastas, the author of this problem, is my friend in Facebook. Since my second year in college, I have seen him as someone who I should have a picture with. Our coach before spoke too highly of him that every time I see him on campus (he is also a professor at Ateneo de Davao’s graduate school), I feel that there is a light that surrounds him, an aura of a genius. I quickly moved on with my “man crush” feelings for him when I knew of Dr. Steven Halim. I even have a picture of us two! No homo, though.

I opened with that paragraph since I saw a Facebook post of Dr. Manalastas about this next problem. He revealed that the solution to this problem is by using Floyd-Warshall All-Pairs Shortest Path (APSP) algorithm. This algorithm is very slow and it has an O(n^3) runtime! This should only be used when you actually need shortest paths of multiple pairs, if not all of them. As you will read along the problem statement, you would realize that there is a better approach to this problem, which is by using the Breadth-First Search algorithm. But no matter what his solution here is, he is still much smarter than me.

Edit: In the Facebook post of Dr. Manalastas, he also mentioned a student who also has the same solution as mine.

(All the problems in the contest are compiled in a PDF format found here)

Continue reading →

2014
09/28
POSTED BY
CATEGORY
Naga 2014
UVa Problems
TAGS





Leave a comment

ACM ICPC Naga 2014 – Problem E: Center of Hull

At first, I really feared computational geometry problems. If I am faced with one, I would immediately tell my teammates that this problem is very hard and that we should not try it. One time, I saw a graham scan code that I seriously did not understand. I just put it in our team notebook. In the competition, there was one convex hull problem! I tried to solve it with the code that I did not understand, and our solution got accepted. And as time goes by, convex hull problems keep appearing in ICPC Philippines contests that instead of getting afraid, I get bored as I see them.

Maybe convex hull problems are the problems that are interesting for Dr. Manalastas, but as time goes by, his convex hull problems are becoming boring. It is like he is trying to modify the problem like adding this kind of constraint or adding that kind of specification, but the problem boils down to how you prepare your hull. The stuffs that he adds in the problem are plainly easy. Personally, I don’t regard myself as good at those kinds of problems, but I always find the convex hull problems of Dr. Manalastas very easy.

So, if this continues, I suggest that all the teams who wants to join ICPC contests in the Philippines should get ready to solve a simple or a slightly modified convex hull problems, like this next problem: Center of Hull.

(All the problems in the contest are compiled in a PDF format found here)

Continue reading →

2014
09/27
POSTED BY
CATEGORY
Naga 2014
TAGS




Leave a comment

ACM ICPC Naga 2014 – Problem D: A Perfect Tournament

Some problems require you to think about the problem more (usually with the use of a pen and a paper) than to actually write a solution. These kinds of problems usually are math problems, especially combinatorics. They can be written easily in code by just assigning some variables based on an equation or by figuring out what the pattern of the sequence is. Most of your time is spent on thinking about the pattern or solving for the equations.

This is why, in my opinion, a team should composed of a coder, an algorist and a mathematician. The coder concentrates on writing the codes, the algorist focuses on finding an efficient algorithm for a problem, and the mathematician figures out the math stuffs. In this way, the people in a team concentrates on different topics, giving the team a very wide coverage of knowledge for the contest. I hope that coaches would realize this. My coach before indirectly insisted that everyone in the team should focus on writing the codes. She chose the teams based only on the students’ capacity to write codes.

Problem D: A Perfect Tournament looks very easy since the statement is only one page and you only need to answer a yes or no question. But to answer that question, you would need to know how to get the answer, especially if you don’t know some mathematics. Like me.

(All the problems in the contest are compiled in a PDF format found here)

Continue reading →

2014
09/27
POSTED BY
CATEGORY
Naga 2014
TAGS




Leave a comment

ACM ICPC Naga 2014 – Problem C: Ordering Zee

This next problem reminds me of my Data Structures and Algorithms class. After the discussions on the recursion topic, we were asked to write a recursive function that prints out a string that would look like a complete binary tree of depth N. It was so hard that my classmates did not get it on time. I barely got it; my recursive function is as dirty as a garbage can. I was so lost that time that I really swore to hate all the recursion problems that would come across.

Well, I realized that I could not do that. There are a lot of things that branched out of recursion: dynamic programming and recurrence relations, functional and reactive programming to say the least. I practiced and solved a lot of recursion problems, sometimes to no avail. One day I saw a recursive problem, and suddenly a solution just snapped into my mind. I immediately coded the answer and it was correct. That is when I thought once again, practice is the only thing you can do to train your mind on different data structures and algorithms.

Problem C: Ordering Zee is about converting a single-dimensional array into a two-dimensional array using a technique called Z-ordering.

(All the problems in the contest are compiled in a PDF format found here)

Continue reading →

2014
09/26
POSTED BY
CATEGORY
Naga 2014
TAGS



Leave a comment

ACM ICPC Naga 2014 – Problem B: Scrabble (R)

Another Philippine ICPC contest is currently ongoing: ACM ICPC Northern Luzon Multi-provincial Programming Contest. This blog series could have been at least helpful to the contestants of the said contest, but I was too late to decide whether I should make this blog series or not. But I know this series will become useful again in the near future, just like my unfinished ACM ICPC Manila 2013 series. Come to think of it, I haven’t posted my solutions to the problems in the ACM ICPC Naga 2013. I should do that after this series.

The next problem is another ad hoc problem. I think what the problem setters would have wanted is to arrange the problems in ascending (easiest to most difficult) order. I actually like this problem, despite its difficulty. You know that one easiest problem in an Asia Regional contest — this problem is the closest to that kind of problem. I did a little Google to stalk on the author of this problem: Joel Reyes Noche is actually an associate professor at the Department of Mathematics, Ateneo de Naga University. He was also a problem setter last year for two problems: one we have not solve in the contest proper.

As the title of this blog post suggest, the next problem is all about the game Scrabble.

(All the problems in the contest are compiled in a PDF format found here)

Continue reading →

2014
09/26
POSTED BY
CATEGORY
Naga 2014
TAGS




Leave a comment

ACM ICPC Naga 2014 – Problem A: Flood Alert

So I plan to write another blog series about a competition. I actually chose to write my solutions on the problem set in the National Olympiad in Informatics – Philippines (NOI – PH). But they had prepared their own editorial and solutions beforehand and uploaded them right after the contest ended. So it is useless for me to post my own solutions to their problems. They know better than me. But if you really want to look at their problems, solutions, and the editorial, the links are here:

  • Problems: https://www.hackerrank.com/contests/noi-ph-finals
  • Editorial: http://noi.ph/2014/Editorials-NOI_2014_Finals.pdf

Luckily, there was another recent contest in the Philippines: ACM ICPC Philippine National Programming Contest. For those who are not familiar, NOI is for high school students and ICPC is for university students. Interestingly, as what I have seen, the problems in NOI is much more difficult than the problems in ICPC. Well, I experienced Philippines’ ICPC myself before (2010, 2011, 2013 Manila, 2013 Naga) and although I could not get a perfect score, I can still solve everything at home after the contest. The NOI is really hard; there were some problems that I could not solve without the help of the editorial.

The above paragraph is just to set your expectations in this series, especially when I start with a very, very disappointing problem. We start with the first problem: Flood Alert.

(All the problems in the contest are compiled in a PDF format found here)

Continue reading →

2014
09/26
POSTED BY
CATEGORY
Naga 2014
TAGS


Leave a comment

ICCF 2014 – Problem D: Levenshtein Distance

If you are an experienced competitive programmer, seeing the title will fend you off this blog post. Maybe some competitive programmers might think that “hey, maybe this is a trick, the problem is about something else”, but no it is not. This is really solving for the Levenshtein distance of two strings, an uber classical dynamic programming problem. What’s more unexciting is that the problem statement formally defined the distance. They gave out the descriptive definition and a definition of a recursive function. There are still other things that will disgust you about this problem. Read on, but I warned you.

The last problem: Levenshtein Distance (you can now download the problem statement here)

Continue reading →

2014
09/16
POSTED BY
CATEGORY
Competitions
ICCF 2014
TAGS

Leave a comment

ICCF 2014 – Problem C: Least Number of Moves

I can still remember my first ICCF participation. I was not given the chance to participate in the ICCF Open Programming Competition since I was not good enough back then. I was instead “forced” to participate in the Quiz Show where we bagged the third prize. After that, I practiced real hard, solving n UVa problems every week until I was addicted to it. I joined the next year in the 9th ICCF programming competition. Although we were in the first place, it was too sad we did not solve the first problem.

I brought up that sad memory because this next problem is so much alike to that problem. The past problem asks you if a sliding 8-puzzle configuration is solvable or not. I honestly think that this can be solved using BFS, though I have not tried solving the problem. Sometimes it is very tiring to code a solution if you cannot assess whether it is right or wrong. I don’t know why, but the ICCF committee does not release the judges’ I/O. They should release it after the competition to know if there is something wrong with their I/O. Oh well.

This is their third problem: Least Number of Moves. (you can download the problem statement here)

Continue reading →

2014
09/16
POSTED BY
CATEGORY
Competitions
ICCF 2014
TAGS

Leave a comment

ICCF 2014 – Problem B: Lambert’s Cosine Law

The second problem they gave again requires a little bit of knowledge in Physics and Linear Algebra. But since this only involves vectors, I think basic algebra and high school physics is enough. This made me think that this year’s ICCF problem setters focus more on mathematics. Come to think of it, a lot of their problems in the past also involve maths. This is something good to note when coming to this contest. So next time, the contestants should prepare their advanced mathematics (Linear Algebra, Number and Set Theory, and Analysis are the basic three).

This problem made me excited the most. I think problems which involve more on solving problems on paper rather than coding a lot of lines are the problems that excite me. This problem, for example, took most of my time solving something on paper. The code, which you will see later, composes only of variable declaration, input and output, and variable assignment. The code, for most people looks easy, but the underlying concept might be difficult for them.

I will now present to you the second problem: Lambert’s Cosine Law. (you can download the problem statement here)

Continue reading →

2014
09/16
POSTED BY
CATEGORY
Competitions
ICCF 2014
TAGS

Leave a comment

ICCF 2014 – Problem A: Sorting Vertices

After a long hiatus, I have found a new reason to post Java codes. Just a while ago, the 12th Iligan City Computing Fair (ICCF) – Open Programming Competition has ended. And yet again, my alma mater, the Ateneo de Davao University, bagged the first place for the nth time (I lost count, sorry haha). This time, the teams are inexperience and composed of a first year and a second year students. Our aim was through the easy (so we thought) questions of the ICCF, the new members of the Ateneo Programming Varsity would be oriented as how a real contest is hosted.

But in contrary to our thoughts that the problems are so easy, the difficulty of the problems this year coincide with their theme: “Next Level. Power Up!”. The four problems are still doable for three hours, but I don’t think they gave thought of putting at least one easy problem. All the problems are two-starred and three-starred (out of five), in my opinion. The results fare very poorly: only four teams solved one problem each. But overall, I think this year has the best problem set of all the ICCFs I have attended. Kudos to the problem setters!

Since the problems were so exciting, I immediately solved the problems as soon as I have received the problem statements. I want to share it to all the contestants so that they can prepare for the next programming contests to come.

We start with the first problem: Sorting Vertices. (you can download the problem statement here)

Continue reading →

2014
09/16
POSTED BY
CATEGORY
Competitions
ICCF 2014
TAGS

Leave a comment