Wednesday, July 8, 2009

SRM 444 + answers to previous questions

Here's the SRM 444 screencast: AVI from narod.ru.

Summary: this screencast may seem a bit "slow motion". Somehow it took me much more time than usual to solve the problems (which I think were nice although probably too heavy with "standard" ideas, and I couldn't understand the problem statement of the easy problem for quite some time) - heh, it's strange to be sleepy at 3pm - but it's of course ACRush's superb performance that we should blame for the 500+ point margin :) Good job!

I wonder if there exists a non-exponential solution for the medium problem. Intuitively, it seems like with only one kind of block there might be some matching-style algorithm to solve it, but maybe the intuition is wrong. A reduction of an NP-complete problem to this problem would also be of interest, though :)

And here are the answers for the questions posted previously on this blog:

1) Why did the SRM 442 screencast interrupt in the middle? Imagine that you've coded the solution and submitted it almost without testing. Then, you realize you're not sure whether you should exchange i with j in one place in your code. You do that change, and see the code still pass all sample tests. You compile it in the arena, and find a test where it seems to break. You then change indexes back and compile in the arena again to see that the old version works on that test case. After all these changes, you realize that you don't remember which of the two versions you actually have submitted! How to find that out? Easy! Stop the screencast, open the recorded video and find the submission time :)

2) How to find last 10000 digits of x=a/b in base 31? First, if b ends with 0, then a also must end with 0, and we can remove both those zeros without changing the answer. Let's repeat that until the last digit of b isn't 0. Then, how to find the last digit x0 of the answer? Obviously, when multiplied by the last digit of b, it should give the last digit of a. But exactly one digit will satisfy that equation since 31 is prime! Then, we subtract b*x0 from a, and we can find the next-to-last digit x1 of the answer from the fact that multiplied by the last digit of b it should give next-to-last digit of a-b*x0 (the last digit of a-b*x0 is zero). We can repeat this process k times then. The final note is that one doesn't need to calculate a-b*x0 completely, as we only need the last k digits of it during the future process, and thus each step of the algorithm takes O(k), with the entire algorithm taking O(k^2).

Here's sample code that assumes a and b are given as arrays of digits with 0-th item representing the least significant digit (so the numbers are 'reversed'):
 1: int start = 0;
2: while (b[start] == 0)
3: ++start;
4: for (int i = 0; i < k; ++i) {
5: int x;
6: for (x = 0; x < 31; ++x)
7: if (x * b[start] % 31 == a[start + i])
8: break;
9: res[i] = x;
10:
11: // Subtraction
12:
int carry = 0;
13: for (int j = start + i; j < start + k; ++j) {
14: carry = carry + a[j] - b[j - i] * x;
15: if (carry < 0) {
16: int ncarry = (carry - 31 + 1) / 31;
17: a[j] = carry - ncarry * 31;
18: carry = ncarry;
19: } else {
20: a[j] = carry;
21: carry = 0;
22: }
23: }
24: }

16 comments:

  1. nice bro,fools like indians will definitely benifit from this,esspecially from the state of tamilnadu

    ReplyDelete
  2. I have trouble solving the TopCoder problems sometimes and cannot find the correct solution. Why doesn't the great Petr give a solution for each problem after the match he attends? Although I can see your code, a bit more explanation will surely be more helpful~~~ This may bring your blog even more popular than today, I think.

    ReplyDelete
  3. 2Cyker Way:
    I believe the wiki editorials written at the TopCoder website are a very good source for such explanations:

    http://www.topcoder.com/wiki/display/tc/SRM+442

    (you can guess the URLs for other matches :))

    I want writing here to be interesting for me, and I can't say I always want to write explanations for SRMs.

    ReplyDelete
  4. Hi Petr

    I implemented the suggestion you made during Chat Sessions. I can get the thinking part for most of the question but couldn't get it into working code . when I see the editorial I get to see the same approach , even after reading the code I try 2 -3 times still can't implement the solution on my own.

    What is your suggestion , ( little specific) to improve my situation

    ReplyDelete
  5. Hi Petr! I notice you haven't posted the screencasts to the last two SRM's. Are you still recording during the competition or have you stopped? I (and many more I believe) loves to watch them.

    Cheers

    ReplyDelete
  6. Hi . Ur blogs are really great & helpful . Can u suggest me some ways & books to enhance my programming skills..

    ReplyDelete
  7. Привет!

    Скажи, пожалуйста, какая версия языка C# разрешена на TopCoder'е? Можно ли использовать C# 3.0 with LINQ? Не смог найти на оф. сайте такой информации, хотя для C++ окружение прописано чётко.

    Заранее благодарен за ответ.

    ReplyDelete
  8. 2Anonymous: I've been recording the screencasts, but was short of free time to update this blog. I'll do that soon.

    2Qbit: No, you can't use LINQ. I believe it's C# 2.0.

    ReplyDelete
  9. 2Hemant Verma:

    Maybe try solving a lot of easys in the TopCoder practice rooms?

    ReplyDelete
  10. i want to read your thesis, please can you upload it?

    ReplyDelete
  11. The medium problem you cite seems equivalent to packing 2x2 squares in a grid polygon, as any grid polygon can be represented with a number of 1 blocks inside its bounding box.

    This last problem was proved NP-complete by El-Khechen et al..

    PS: Thanks for your screencasts!

    ReplyDelete
  12. 2Ricky:
    http://77.41.63.3/blog/thesis/main.ps

    It's in Russian, though.

    2Mariano:
    That's a fantastic link! I wonder how did you find it :)

    ReplyDelete
  13. thanks Petr, i understand russian

    ReplyDelete
  14. It seems that the school problems are same all over the world : )
    Had the same problem in Siberia, but probably in 7th/8th grade

    ReplyDelete