Блог пользователя pratikmoona

The Festival of Holi
Автор pratikmoona, 13 лет назад, По-английски

Hello fellow coders!

Today, 8th of March, 2012 is also the colorful festival of Holi in India. The reason why I say colorful is because it is played with colors (both wet and dry). This link might help you visualise the festival.

Anyway, the reason I am posting this is because I noticed the new codeforces banner for Women's day,

It just so happens that traditionally all colors for Holi are made using colored flowers and for a second I thought that Codeforces is also celebrating Holi.

Anyway, Happy Holi to everyone here!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +31
  • Проголосовать: не нравится

Whiz-it! (An app-development competition)
Автор pratikmoona, 13 лет назад, По-английски
Some of you might be interested in this:

Полный текст и комментарии »

  • Проголосовать: нравится
  • -21
  • Проголосовать: не нравится

How to find the Vertex Cover of a Vertex-Weighted bipartite graph?
Автор pratikmoona, 13 лет назад, По-английски

I recently learnt about Konig's theorem which states that finding the vertex cover in a bipartite graph is equivalent to finding the maximal matching.


It's simple to edit the hungarian algorithm or any other matching algorithm if it is an unweighted graph. But how do I do the same when it is a "Vertex-Weighted" graph?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

Geometry Problem
Автор pratikmoona, 13 лет назад, По-английски
could anyone please tell me the error with my code? It is giving wrong answer.

QUESTION: http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&page=show_problem&problem=3109

CODE: http://paste.bradleygill.com/index.php?paste_id=290688

The question is from an ACM-ICPC regional.

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Google Code Jam Round 1A : Problem A
Автор pratikmoona, 14 лет назад, По-английски
Problem A of the recently held CodeJam Round 1A has the following official analysis. I however coded an O(1) solution.


Did anyone else do this directly like this?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

Room Ranking and Contest Stats
Автор pratikmoona, 14 лет назад, По-английски
I was thinking that its perhaps now time that we add room rankings and some other contest statistics for every contest and user. Now that we regularly have 1000+ users participating in the contests, and that rooms are divided according to division, I think its time we started giving importance to room rank as well. This will also act as a boost for Div 2 participants who (often) cannot perform well in regular rounds.

Also, statistics like, percentage of users solving a certain question, etc, could also be included for each contest. It is quiet interesting to go through these stats on Topcoder.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

Quiz Blog! Q # 1
Автор pratikmoona, 14 лет назад, По-английски
I plan to start a weekly Quiz blog here. I hope many of you are interested in Quizzing. Some general info:
  1. A new question would be put up every week (I hope! :P)
  2. The first three people to answer the question would be declared winners
  3. There are no prizes, just your pride at stake :D
  4. Please put the answer as "revisions" in the comments
  5. Google will be your best bet when you get stuck
So, this is the first question. An easy one for today.

Connect the following three images:


Полный текст и комментарии »

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

Round 55 (DIV 2)
Автор pratikmoona, 14 лет назад, По-английски
Here I am sharing how I approached and solved the problems of the recently held Round 55 (DIV 2)

A. Word
This was an extremely simple problem. Simply count the number of upper case latin letters. If that is strictly greater than number of lower case letters convert the word to upper case other wise convert it to lower case. 
Complexity: O(wordlength)

B. Fortune Telling
For this problem all you need to do is store the smallest odd number of petals and also the sum of all the petals. It is quite obvious that only if the number of petals is odd the result would be "Loves". So if the sum is even print sum - smallest odd, otherwise print the sum.
Complexity: O(n).

C. Title
This was a very nice problem. My approach was to first flag all the letters which have already appeared. Notice, that we have to output the lexicographically smallest palindrome. So, start from the middle of the letter and iterate one side...
If you get a '?' stop and check if the corresponding position on the other side also has a '?'. If yes, then fill both with the lexicographically biggest letter which hasn't appeared yet in the word and also flag that letter.
Once you have exhausted all the letters and there are still '?' left then simply fill them with 'a'.

Now simply iterate over the word again and see if there are any question marks left, if yes copy the values in the corresponding block on the other side. At the same time check if at any time the two opposite values match or not. If they do throughout then it is a valid plaindrome which is also the lexicographically smallest palindrome.

Here is a slightly messy implementation of the same: http://codepad.org/Fr7NYqYT
Complexity: O(wordlength + k)

D. Team Arrangement
This was in my opinion was the toughest problem. However once you get the logic, its pretty obvious. However, it was a slightly challenging implementation for me as the structure of the data to be stored was sort of complex.

The basic idea was simply that if we have to find the preference list of a number 'p' then two things might happen:
Case 1: p is the most skilled in his team and thus he chose the team. In this case we know that all the members of the teams coming after p's team are less preferred than p's team mates. Let p's team mates be 'm' and 'n' such that m > n.

To get the lexicographically smallest preference list, we will divide all the programmers into two lists. The first list will contain all members (ai) from teams which were chosen before p's team such that ai < m. It will also contain m and n.

The second list will contain all the left over members.

The separation can be done in O(n) time. Now all we need to do is sort the first list, print it, sort the second list, print it!

Complexity: O(nlogn)... It can be reduced to O(n) also but the constant will be pretty high and will give almost the same result as O(nlogn).

Case 2: p is not the leader of the team. Then you just have to output all number except 'p' from 1 to 3 * n.

As for the last problem, I do not have a solution. I do not have much experienced with implementing graphs unfortunately.

Please point out any optimizations to the above or mistakes which I might have made in the above.

Полный текст и комментарии »

Разбор задач Codeforces Beta Round 55 (Div. 2)
  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится