hadi's blog

By hadi, 7 years ago, In English,

There'll be an online contest at ZJU Online Judge on Sunday.

The problems are usually very nice and a bit hard, so I thought you may like to participate :-) You can find the ranklist for the previous contest in these series here.

You can see the time and date in your region here.

Happy learning and solving!

Read more »

 
 
 
 
  • Vote: I like it
  • +16
  • Vote: I do not like it

By hadi, 7 years ago, In English,

There'll be 10 training contests running at http://acm.hdu.edu.cn/contests/contest_list.php from 2012-07-19 to 2012-08-23, which will contain more than 40 universities of China.

If you like to participate in these contests, you should provide a problem per team. The problems should be at Topcoder Div 1 medium or hard level (or you can take regional problems as reference), and it will be tested by a special commitee member. Deadline for providing the problem is July 15th. The problem should contain 5 files: Problem Statement, Test Input, Test Output, Solution, and Solution Sketch.

All teams from all countries are invited to participate. Problems will be in English.

If you want to get more information or you want to participate, please contact acm [at] hdu [dot] edu [dot] cn.

NOTE : Notice that I am not affiliated in any way with the organizers, and the above information is the summary of what they answered in several emails :-) I just thought you might find these contests intresting.

NOTE 2: The Link to Problems from Previous Year.

Read more »

 
 
 
 
  • Vote: I like it
  • +29
  • Vote: I do not like it

By hadi, 8 years ago, In English,

I set another practice contest for tomorrow evening.

The number of problems is 4, and the duration is 2.5 hours.

The link is http://acm.hdu.edu.cn/diy/contest_show.php?cid=15610.

Everybody is invited to participate :-)

To see the time and date in your timezone, click HERE.

Links to the previous contests:

Read more »

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

By hadi, 8 years ago, In English,

I set another practice contest for tomorrow evening.

The number of problems is 4, and the duration is 2.5 hours.

The link is http://acm.hdu.edu.cn/diy/contest_show.php?cid=15476.

Everybody is invited to participate :-)

UPDATE: It was postponed for tommorow. To see the time and date in your timezone, click HERE.

Read more »

 
 
 
 
  • Vote: I like it
  • +11
  • Vote: I do not like it

By hadi, 8 years ago, In English,

There'll be a practice contest at http://acm.hdu.edu.cn/diy/contest_show.php?cid=15449 today. Duration is 2.5 hours and number of problems is 4. Everybody is invited to participate :)

Read more »

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

By hadi, 10 years ago, In English,
I participated in the beta round #7, and my performance wasn't good and I dropped some rating points.

My first mistake was in problem B, in which I wasn't careful that "erase" parameter can be any integer. I think my solution failed for "erase -1". Well, this didn't cost me too much, as I figured it out in about 10 minutes and got it Accepted.

My second mistake, and biggest mistake was in problem C. I'm very weak in number theoretical problems (currently), and I didn't realize that this is a standard Diophantine equation, which had a very standard algorithm to solve. After some struggling, I searched the internet for some help. At last, I ended up in Shygypsy's tools, which had the code for problem. But it didn't work for negative numbers, and I wasn't good enough to figure out how to do the % operator for negative numbers. After much time spending on this problem, and writing too much unnecessary code, I could get it Accepted in 1:43.

Then I tried to solve problem D, but probably 17 minutes wasn't enough for me. It wasn't a hard problem. Palindrome prefixes can be detected in O(n) using KMP (or probably using hashing), and the rest can be done using a simple DP. Well, the solution wasn't difficult, but probably I didn't have enough self-confidence to solve it.

I have lack of self-confidence, maybe because I have lack of practice :-) I will most probably participate in next match, and I hope to gain some rating points.

Read more »

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

By hadi, 10 years ago, In English,
A good grasp of (discrete) probability is often necessary to do good at programming contests. Last year, while reading a book about the great mathematician Paul Erdős I read about a probability puzzle posed by Marylin vos Savant in a magazine. The puzzle is:

"
Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice?"

UPD. The above statement has some errors. See SkidanovAlex's comments.

Read more »

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

By hadi, 10 years ago, In English,
Sometimes you face a string processing problem for which you have the correct idea, but implementing it might not be so easy. In some of these cases, you can find a much easier to implement algorithm using hashing. These algorithms don't always give correct answer, but their probability of giving wrong answer is very low.

 The simplest example is string matching, where you have to find a string inside another string. Well, you can use the KMP algorithm, which is fast enough, and easy to implement if you have enough practice. There's an alternative using hashing: Rabin-Karp algorithm. You probably should know it so you can invent more powerful algorithms for more difficult problems.

Read more »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

By hadi, 10 years ago, In English,
Some days ago, I tried to solve Binary Palindrome. The problem seemed difficult at first and I had no idea how to approach it. As a start, I wrote a simple program to calculate the result for small inputs, and ... I saw a pattern! I guessed what the result could be, and after some tries I could get it Accepted!

I don't know if other people also solve problems by guessing or not. But this wasn't my first. Some others were:
  • Difficult Choice: I wrote an O(N^3) DP locally, and looking at dp table I found a pattern, and invented an O(N^2) algorithm without knowing the logic,
  • Cartoon: I wrote an O(N^2 * K) solution which didn't pass the time limit. Then I guessed an optimization like Knuth's optimization, and happily it worked!
There are some other problems which I solved using guessing too. Well, it sometimes works! Have you also tried something like this before?

Read more »

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

By hadi, 10 years ago, In English,
Problem: Imagine you want to buy some cookies. Each cookie i has a price Pi, an "enjoyable value" Ei, and a limit value Li. If Li is equal to -1, there is no limit on how much cookies of kind i you can buy, otherwise you can buy at most Li units of it. Maximize sum(Ei * Ci), where Ci is amount of cookies of kind i you buy, spending exactly D dollars. (This is a bit simplified version of ZJU #3164)

Read more »

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

By hadi, 10 years ago, In English,
Today I participated in my first codeforces contest. The problem-set was quite easy.

Here are how I solved the problems:

Problem A: The answer is "NO" if and only if n is either odd or equal to 2, otherwise you can decompose it as (2, n-2).

Problem B: The answer is "Yes" if and only if sum(minTime) <= sumTime <= sum(maxTime). You can construct a list in this case easily using a greedy method.

Problem C: Straightforward implementation. I used C++'s std::map to implement this problem.

Problem D: O(N^2) dynamic programming. DP state is index of last chosen envelope, and loop over for the next envelope.

I didn't do bad (I became 15th), but I expected better. In fact I could be 3rd if I was a bit careful and read the problem-statement of the last problem more carefully and got it in my first submission at 0:26. I missed that envelope size must be strictly larger than the card, and thought equal is also okay. I got the submission result about 25 minutes later, and lost lots of penalty time.

The lessons to learn are:
1. Read problem statement more carefully,
2. It's okay to waste another minute to check everything once more before submission,
3. Don't just wait for submission result, re-read the problem statement and your code once more.

I hope to do better in next contests, which I expect to have more difficult problem-sets.

By the way, congratulations to the winner of the contest, Xazker, who is also red at topcoder.

Read more »

 
 
 
 
  • Vote: I like it
  • +13
  • Vote: I do not like it

By hadi, 10 years ago, In English,
Some days ago I came across a nice problem: Fat Hobbits . The problem's input is a directed acyclic graph G = (V, E)  with additional property that if (u, v) is in E and (v, z) is in E then (u, z) is also in E, i.e. it has transitive closure, and asks for a maximum size subset of vertices IND such that if v is in IND and u is in IND, then none of (u, v) and (v, u) are in E.

Problem seemed difficult for me at first, but finally I could solve it by modeling it as a min-cut problem. The problem can be easier solved once you know Dilworth's Theorem and how to prove it.

From time to time you will see problems which can be solved using max-flow min-cut algorithms. To see some more problems, see topcoder tutorial Maximum Flow, Section 2 and also these lecture notes. I also remember some more from other online judges: Dual Core CPU, Intervals, and many more which I don't remember right now.

You'd probably ask how can you detect if a given problem can be solved using Max-Flow? I also can't detect many such algorithms, but probably the answer is: Either by experience or by guessing. After you see many problems which can be solved using max-flow, you can easily invent some new max-flow formulations for some other problems. If you can't do this, you can probably guess a formulation and try to prove or disprove it, since most of formulations aren't strange. Guessing is an art, a beautiful art :-) But try to prove your guesses, otherwise you might waste your time with debugging wrong solutions.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By hadi, 10 years ago, In English,
Hi,
 I am irancoldfusion@topcoder. Codeforces seems great :-) I like that people can blog in it, and I like that I have more time to solve problems than in topcoder.
 I haven't competed much in programming competitions in 2009-2010, in fact I've become 'unranked' in topcoder some weeks ago, which means I haven't participated at topcoder for more than 6 months. But I am thinking of starting to compete in competitions again, because it's one of the few things which make me feel "really" good. Some of the other such things that make me happy are: being with and thinking about my dear wife (yes, I got married 5 months ago :-), learning new things, and probably some kinds of music.
 I hope I can compete in most of next matches. I guess I have to miss the next match because it is the same time as a university class :-(
 I hope I can become a Marshall someday :-)

 Below you can see me fighting with a huge lion in China ;-)

 

Read more »

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it