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

Автор chrome, 12 лет назад, По-русски

Доброго времени суток, %username%!

Завтра Сегодня в 19:00 MSK состоится Topcoder SRM 649.

Предлагаю обсудить задачи после контеста!

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

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

Can't connect to the arena..

"A connection to the server could not be established"

»
12 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +9 Проголосовать: не нравится

How to solve Div. 2 500?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

How to solve Div 1 Easy?

  • »
    »
    12 лет назад, скрыть # ^ |
    ← Rev. 3  
    Проголосовать: нравится +2 Проголосовать: не нравится

    For a string to be uncertain, letters in different positions in the original string have to match in the final string. If the letters are more than K apart, you don't have enough deletions to make them match. So, based on this, if there are two equal letters at most K apart, such as

    axxxxxa

    You can delete all of the Xs and one A; there is no way to tell if you left the first a or the second a. If there are no equal letters at most K apart, return Certain.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

850 seems so easy in hindsight u.u

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

How to solve div1 550 ?

»
12 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

DAAAAMN!!! I would have won that TC if it weren't for that mistake

parts = k + 1;
eaten += 2 * parts - (k + 1);

->

eaten += 2 * parts - (k + 1);
parts = k + 1;

I got 2nd fastest solve to 550 and it would have been fastest solve to 850 (worth 587 pts) :( (I wouldn't go hacking if I would have been first :P)

Though I finally found that mistake and ended up on 14th place which is also very good, but being 1st in TC is one in a lifetime opportunity :<

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Time limit of Div 1 Medium was a little tight. I lost a few minutes optimizing some constant on it :(

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

How come, the answer Div 2 500 for the case,

N = 45, K = 5

is 11?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +53 Проголосовать: не нравится

I am the writer of this contest. I started to prepare problems 34 hours before the contest begin. Because of time limit in real life, I can't make appearance of my wolf character in the statement...

By the way, it was cool that there is no misjudge in spite of preparing time. The tester and admins are great:)

  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Lol, 34 hours is a very little amount of time to prepare 6 problems :d. What do you exactly mean by "preparing"? Did you really wrote 6 statements, 6 model solutions, 6 test sets in one day :o?

    And aren't TC admins afraid that someone will someday fail to prepare everything in time? Do they have some spare problems?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +50 Проголосовать: не нравится

Try to guess why this code gets AC.

On the example testcase s = "aa", K = 2 it returns "Certain".

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain the example test case and some other test case for Div 2 500 ?

5 2 Returns: 4 One optimal solution: {5} -> {2,3} -> {1,2} -> {1,1} -> {}. We used two splits: once when splitting the sequence of 5 carts into 2+3 and the second time when splitting the sequence of 2 carts into 1+1.

I don't understand how from state {1,2} transition in to {1,1}. It talks about split but doesn't the split of 2 should result {1,2} -> {1,1,1} ?

Not sure what I am misunderstanding in this question ?

»
12 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Hello, I have two general questions related to the Div 2 500 point problem (CartInSupermarketEasy).

Question 1: I looked through the solutions of all of the top finishers in Div2 and I noticed this: 90% of them solved this problem using top-down recursive memoization. The remaining 10% solved it using bottom-up iterative DP. Is there a reason for such an overwhelming preference for recursive memoization in this case? When I ran the timer (see below), the iterative solution performs a bit faster.

Question 2: Something seems to be totally off with my timings. When I ran my solution on my computer using max input (100,100), it took 13.4 seconds, which shouldn't pass by any means. (The recursive solution was even worse: 15.5 secs). However, when running this same solution in TopCoder (practice), it passes the (100,100) test in 47 ms. I have noticed similar behavior in the past. I am using Visual Studio (CL compiler).

Thanks!

  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Question 1: I think that memoization is easier to code and understand, and still fast enough.

  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Q2: Actual clock running times depend on hardware, but I have an idea of what could be the cause. Are you using a testing plug-in that downloads the sample cases and tests your code against them, all in one run? If so, you may be recomputing dp(100,100) once per each test case.

    • »
      »
      »
      12 лет назад, скрыть # ^ |
      ← Rev. 4  
      Проголосовать: нравится 0 Проголосовать: не нравится

      I actually figured out what the problem was, I was running my Visual Studio in Debug configuration. Once switched to "Release" configuration, the problem was solved. It's still strange that this was causing the program to run x300 time slower, as I usually don't see such a discrepancy, even when running in Debug. Another neat thing I noticed while analyzing my program is that replacing std::min/std::max functions with min/max that I wrote, sped up the program by a factor of 3.

      UPD: And here is an article confirming my observations: std::min causing three times slowdown