rng_58's blog

Codeforces Round #162
By rng_58, 12 years ago, In English

Hello!

I'm Squirrel Liss. I became the hero of today's contest. The writers of the contest are snuke, hogloid, DEGwer, and rng_58. I'd like to thank Gerald for helping preparation, Delinur for translation, and MikeMirzayanov for the Codeforces system. The point values will be standard: 500-1000-1500-2000-2500 for both divisions.

I will encounter many difficulties about stones, nuts, and sequences... Please help me!

Since 07:30 PM MSK is late here, the contest will be moved to 05:00 PM MSK. Please check the schedule in your time zone in timeanddate.com: http://timeanddate.com/worldclock/fixedtime.html?iso=20130120T22&p1=248&ah=2

UPD: Announced the detail of the contest.

The top five contestants in div1 were:

And in div2:

Congratulations!

Also congratulations al13n and Komaki for solving div1 E problem.

The authors were

UPD: Tutorial was added here.

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

Comments Comments (160)
| Write comment?
»
12 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

If you could do it for 3:00 PM MSK, would be better I think :)

→ Reply
»
12 years ago, # |
  Vote: I like it +31 Vote: I do not like it

How powerful the problem setter group it is ... I guess the problem set will be extremely hard ...

→ Reply
»
12 years ago, # |
  Vote: I like it +34 Vote: I do not like it

I smell a lot of math.

→ Reply
»
12 years ago, # |
  Vote: I like it +76 Vote: I do not like it

WOW...I guess it would be a VERY hard contest...And I'm really looking forward to rng_58's problems :) so I'll take part for sure :).

→ Reply
»
12 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Looking at the problem writers, the problems must be very interesting. I definitely will participate :)

→ Reply
»
12 years ago, # |
  Vote: I like it -37 Vote: I do not like it

too early announcement!!

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    I think it was because of the change in schedule.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is not announcement. Announcement will be later.

    → Reply
»
12 years ago, # |
  Vote: I like it +7 Vote: I do not like it

This contest will be very hard...but it will be very good(I want to participate in Div1,but I will not be able to participate because my rating became less than　1700...).

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    div2 Round #161 will take place before div1 #162 try to become candidate master then you will be able to participate in div1 in round #162

    → Reply
»
12 years ago, # |
  Vote: I like it -36 Vote: I do not like it

I cant able to slove more than a problem in contest... Anyone help me plz

→ Reply
»
12 years ago, # |
  Vote: I like it -70 Vote: I do not like it

and what about money?:D

are they gonna split it?:D

→ Reply
»
12 years ago, # |
  Vote: I like it +23 Vote: I do not like it

looking forward to a topcoder admin's problem. :) I won't miss it.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    admin? you sure?

    which one?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      I think he meant rng_58 . Though I am not sure admin would be the right word.

      → Reply
»
12 years ago, # |
  Vote: I like it -29 Vote: I do not like it
Комментарий удален администрацией по причине несоблюдения правил сайта.
→ Reply
»
12 years ago, # |
  Vote: I like it +7 Vote: I do not like it

This will be the contest with the best problem set and the best plot :) . good luck & have fun !

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Хочется, чтобы Белочка Лисска почаще составляла контесты! Всем удачных взломов и повышения рейтинга!

→ Reply
»
12 years ago, # |
  Vote: I like it +20 Vote: I do not like it

And one hour after the end of the contest, January cook-off. This will be an intense, and of course, an awesome day...

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Where is the picture of squirrel? I can't see it:(

UPD. Done. As I understand from hogloid's profile picture he is the squirrel we need to help to ^_^

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

I guess that there are many kinds of animals in the statement because they are Japanese writers. I like wolves!! So I wish the problem set would contain problem about wolf!!

→ Reply
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

good luck everybody!!! Have very good solutions :)

→ Reply
»
12 years ago, # |
  Vote: I like it -34 Vote: I do not like it

salamalekum vsem jelaiu vsem uda4i nadeius etot tur ne jeral'd sostavel ato kapec potom ewo sam budet pesat' vawe krasava budet etot JEROL'D

→ Reply
»
12 years ago, # |
  Vote: I like it +40 Vote: I do not like it

It seems that over 700 people will participate this contest (because of its good timing?). It will be the div. 1 contest with the most people participating recently (or up to now?)...

→ Reply
»
12 years ago, # |
  Vote: I like it +31 Vote: I do not like it

it seem that the writers are very "meng" looking forward to

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    it's called moe~~~ so cute :)

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ? what does "meng" mean? its mean is like moe?

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        "meng" is the pronunciation of the Chinese character "萌", while "moe" is written as "萌え" in Japanese.

        → Reply
»
12 years ago, # |
  Vote: I like it -7 Vote: I do not like it

502 bad gateway !

→ Reply
»
12 years ago, # |
  Vote: I like it +9 Vote: I do not like it

could not catch the registration... what a pity!

→ Reply
»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Шарик снова с нами на раунд

→ Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

poor statement of problem c in div 2..:(

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    What's wrong with the statement? Yes, it might be hard to imagine it, but try drawing it — that should make it clearer! Edit: Besides, apparently more than 900 people didn't have a problem with it.

    → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

Very slow.Unable to hack. disappointed.

→ Reply
»
12 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Hello, Div2 !

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    I drew a 2D matrix and looked at all unreachable cells (you can either go to (x+1,y)/(x,y+1) or to (x+1,y+1) only). Then you have pretty beautiful answer.

    → Reply
»
12 years ago, # |
  Vote: I like it +77 Vote: I do not like it

Very nice problems, thank you!

Of A, B, C, D (haven't had time to try E) I especially liked D.

→ Reply
»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

why i always receive a message from this online system that 'Can't process your hack, try again' when everytime i try to upload a file to hack. Anyone could help me about this question?

→ Reply
»
12 years ago, # |
  Vote: I like it +19 Vote: I do not like it

I couldn't make any hack today , whenever I try to drag the hack screen it select the text and it's undraggable, whenever I scroll down , the screen scrolls down with me , in the previous contests the hack screen was draggable i don't know why it's undraggable today , did anyone else face the same problem ?

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    I did in this way: 1) put cursor at lowest visible textbox 2) press tab 3) press enter

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you, I'll try this next time :) but don't you think that this bug should be fixed ?

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        I think so, but I meet this bug last 4-5 rounds :)

        → Reply
»
12 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Very cool D! I didn't solve it (I know my bug), but it is real cool!

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    TAT... Just one minute or two, I could have finished my D... Being troubled with C for TOO long... TAT... Perhaps because I have not written any code for a long time...

    → Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

AWESOME PROBLEMS . Too bad i got hacked twice, but ... Nice, nice problems, though . Congrats !

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I get Invalid input for problem B hacking with 100000 1 2 ... 100000 input, but 99999 1 2 ... 99999 was OK once, on the second try it gives Invalid input too. It's weird.

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It is really shameful to taking care of special cases in wrong way. eg. for Div 2 B , in case of only 1 tree , answer should be height + 1 , but I output height. :(

→ Reply
»
12 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Hi,

Can I have some help in solving C? I keep getting WA on pretest 8 and I'm not sure why.

My algorithm is that we use the following DP recurrence

Let f(i) = best value we can get if we choose a subsequence with last ball being the i^th ball.

Then f(i) = max(f(j) + A * value[i] if color[j] == color[i], f(j) + B * value[i] otherwise and if i is the first ball)

To speed up this recurrence, for each color I store the top value gotten so far, so that I can perform the "same ball" part in constant time. I also store the top two distinct colours with best f value, so that I can do the "different ball" part in constant time. In total it is O(QN). But it seems that I have some bug somewhere :(. Please help me out:

Source Code: http://pastebin.com/fp9Uip1P

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    You got a correct idea but implemented some ... eh... unnecessary thing? (and it's wrong)

    Try this case:

    1 1
-2
1
0 -5
    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you take a look at my solution and tell me what am I doing wrong. I've been staring at my code for some time now and can't find the error. 2974130

      → Reply
»
12 years ago, # |
  Vote: I like it +31 Vote: I do not like it

The problems are interesting as usual. (Especially problem D, but I think the pretest is evil, thus we can get points easily by blind hack)

It's also interesting that all problems in DIV-I have a constraints at least N>=10^5.

By the way, why Liss is looking at grapes(but not nuts) in the picture?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    It's also interesting that all problems in DIV-I have a constraints at least N>=10^5.

    Which is quite understandable considering for TopCoder limit are rather small ;)

    → Reply
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Really loved the tasks, short statements and interesting tasks allowing many hacks and cool solutions, without much math required, awesome competition :)

→ Reply
»
12 years ago, # |
  Vote: I like it +16 Vote: I do not like it

nice problems. even the writer are Japaneses, the problems are not too mathy.

I like the problems. thanks writers. :)

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +30 Vote: I do not like it

I hadn't a time to solve E, but I've just noticed that hi, xi ≤ 10 (after half-hour thinking). IMHO, you'd better state this very important constraints in description, and not in the 'input' section next time.

→ Reply
»
12 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Spent half of the contest solving C when ball order doesn't matter...

→ Reply
»
12 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Very slow system testing:(

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

O(n) solution for C div2 fall with TL (C#)

WTF???????

http://codeforces.net/contest/265/submission/2965647

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I suppose that .Length is not O(1) and is O(N), hence your solution is O(N^2) due to that fact only.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      You're wrong, length is a class string property, and work in O(1)..

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Yes, indeed. Well that was only an assumption.

        The only other thing I can suppose is that the slowest thing of it all is outputting 10^6 numbers. Maybe Console.Writeline does a lot of overhead (specifically on newlines), which slows it down. Indeed, when I changed the output in your code to:

        string ans = "";
for (int i = 0; i < s.Length; i++)
{
    ans += res[i].ToString() + "\n";
    if ((i % 100) == 0)
    {
        Console.Write(ans);
        ans = "";
    }
}
Console.Write(ans);

        it ran a lot faster on maximum test case.

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

          Please compare these two solutions. http://codeforces.net/contest/197/submission/2295950 http://codeforces.net/contest/197/submission/2295955

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
            ← Rev. 3   Vote: I like it 0 Vote: I do not like it

            So what do you want me to do? What I used above is a small buffer to avoid 10^6 calls of Write/Writeline with newlines at some reasonable cost of string operations. Note that I haven't made one big resulting string (as in your two solutions), as it would give TLE anyway.

            → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I've just wrote Console.Write(res[i] + "\n");

          instead of

          Console.WriteLine(res[i]);

          and got AC in 1406 ms...

          I think, that contestmakers should much carefully testing authors solutions for different languages, and write in condition about features of input and output .... (i.e. it would be better to use printf instead of cout and so on)

          I've lost a lot of rating, and contest made me feel very disappointed(((((

          → Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it +2 Vote: I do not like it

Offtopic: am I the only one who can't click on the link above in cgy4ever's comment? Firefox 18.0.1, Windows 7 x64 En.

UPD: it's fixed now.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I can open it

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I can open it too. Can you open it by clicking on it?

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I could open it with no different from opening other comments.

        → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +52 Vote: I do not like it

The problem D is really interesting...but I am too stupid to figure it out... I just feel like that I lack of cleverness to solve such kind of problem which needs idea (crying)...

Anyway it's a good contest, maybe you could reduce the amount of big test in problems to reduce the running time.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Excessive modesty from a red user.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +46 Vote: I do not like it

      I don't think I deserve that rank and rating... I am just that type of programmer who just solve a lot of problems so if I see a similar problem I can solve it quickly. But if I meet a problem which is not that standard, I just, well, kind of feel like that I'm indeed a noob .

      You can see from my profiles that whenever I got a nice rank, the contest's problems are standard to some degree, if the contest require some deep thoughts about something, I always fail.

      Anyway I know it's bad to think that negatively, I'll try to solve more problems of that kind to practice my brain :).

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        When you meet a new problem and start thinking that you're a noob, your creative thinking goes down as a consequence. It's a closed circle.

        → Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

i solve C by chance :)))

i just saw the examples and i found a model =))

→ Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

What is the limit of characters in a hacking attempt ??

I try to hack the C div2 problem with a string of 10 ^ 5 'l' and 10 ^ 5 'r', ie "llll ... rrr ...." wanting to do a TLE but the result I get to send a string of size 10 ^ 4, and an attempt to hack wrong.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can always upload a generator.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I code ​​a separate program that wrote this string of size 10 ^ 6 simply copy and paste the output and send my hack. But I do not understand where it came from the string of size 16,000

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 4   Vote: I like it 0 Vote: I do not like it

        The generator i've used today:

        int main(){ for(int i=0;i<1000000;i++) { cout<<'l'; } puts(""); return 0; }

        Just upload the source file.

        → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C O(n) is giving TLE.

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    It's not O(n), couse "insert" in vector working O(n). So you insert O(n) times in O(n) cycle = O(n^2). Sorry for my english

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ok i get it

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      No you're wrong man.

      inserting in a vector is O(1) amortized, which means N number of insertion takes O(N).

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Insertions??? To any place, using res.insert(res.begin()+pos,i+2);??? Maybe you mean push_back-s are O(1) amortized?..

        If you really mean insert-s are O(1) amortized, please explain how can it be so.

        → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        To your comment does not prevent people understand the principles of the STL, I will explain more precisely. Inserts the item at the end of the vector = O (1) (amortized). What happens under the hood when we insert in the middle or beginning of the vector? Suppose that the insertion occurs at position n. Then the elements from the position before the end of n is copied and transferred to the one to the right. Total O (n).

        → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have found many participants have this error ~~~~~ for (int i = 0; i < s.size(); ++i) ~~~~~ and I think the correct is ~~~~~ int len = s.size(); for (int i = 0; i < len; ++i) ~~~~~ you can find the reason.(forgive my poor English).

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't understand what is wrong with my algorithm in question C div 2 each time we push the value of "k" to a vector and calculate the new "k" and "d" and this runs forever..and finally we will sort the vector.but my problem has been hacked!!Can everyone help me with this? 2967715

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    |s|<=10^6 and for this you need tu calculate 1/2^(10^6) and there precision will lost.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why 1/2^(10^6)??? the order is linear and ..... sorry I think i haven't gotten what u mean :(

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh, I've gotten!what a bad mistake!:(( So, in this case, what is the algorithm to solve this??

        → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        1/(2^(10^6)) isn't in float or double

        → Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

What's wrong with system testing ? It took a single contest time. I just want to try my solution but I have to wait the systest that very long.

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

My first contest in the first division and I solved two problems. Looks pretty nice to me :).

→ Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Hi All,

I want to know how the solutions are hacked during the contest because I think the solutions of other candidates are not visible till the end of the contest.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    You need to lock your submission on the overview page before you can see and hack other solutions. By locking them you won't be able to resubmit again, and your submission must pass pretests for you to be able to lock it.

    → Reply
»
12 years ago, # |
  Vote: I like it +62 Vote: I do not like it

A great revenge :)

Separately, thx to DEGwer for the div.2 C problem — very interesting.

→ Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Лично Мне понравилось всё только тестировалось долго(

→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Why ivan.metelsky's A got TLE?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -28 Vote: I do not like it

    Задача С ужасная: идеи никакой не нужно и как-то несерьёзно, что TL зависит от оператора вывода и компилятора.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Почему же, идея в том, что нельзя было вычислять середины отрезков и складывать в массив пары <координата, номер камня>, потому что длина строки — миллион. И тл там больше зависит от работы контейнеров stl, по-моему.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it -16 Vote: I do not like it

        нет, один и тот же код на gnu c++ заходит а на ms c++ tlится. это ненормально, по-моему.

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Как раз скорее разница в контейнерах у них. На одной из олимпиад у нашей команды не зашло решение на gcc, но проходило (как впоследствии выяснилось) на msvc. Просто нужно понять — компиляторы разные. И нужно знать их особенности.

          → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +17 Vote: I do not like it

          ItsLastDay выше всё сказал абсолютно правильно. Было бы странно, если бы любой код под обеими компиляторами работал одинаково, не так ли? Например, знаете ли вы, что в g++ по умолчанию вектор при реаллокации увеличивается в два раза, а в msvc++ — в полтора?

          → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it -16 Vote: I do not like it

        да елки палки! была уже статья про использование stl, статистика и все такое. Там наглядно показано, что stl- это хорошо, ничего там не тормозит. А если кто не использует reserve/resize — так это их проблемы. а задача реально безидейная, а AC зависит от выбора компиля. Сам на это наткнулся.

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          А что за статья? Про вектор на сколько я помню было в комментах много обсуждений, что хорошо, а что нет. И что их все-таки лучше не юзать, когда есть возможность.

          → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
          ← Rev. 3   Vote: I like it +21 Vote: I do not like it

          AC зависит от выбора методов ввода/вывода, уж сколько раз твердили миру, что cin/cout == тормоза, а endl — еще дополнительные тормоза, т.к. он флашит поток. Может, для кого-то будет уроком.

          P.S. Твое решение с '\n' вместо endl: 1078 мс (2974799) и с быстрым вводом-выводом: 437 мс (2974853)

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it +4 Vote: I do not like it

            И это по твоему идея данной задачи?))))) Я кончено понимаю, что накосячил, выбрав endl, cout и т.п.... Просто если опустить все эти мелочи по сути, то задача простецкая. А оптимайз высосан из пальца. ИМХО

            P.S. по поводу топика погорячился. Там рассказывалось про stl'евские пары.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 years ago, # ^ |
                Vote: I like it +5 Vote: I do not like it

              Для A абсолютно нормальная задача. А то, что кто-то не знает о скорости ввода/вывода — ну что ж, вот оно, самое время узнать

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                12 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Это была С))

                → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                12 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Тут дело скорее в компиляторе, а не в скорости ввода/вывода в C++ в целом. На GNU C++ нужно было постараться, чтобы получить TL по этой задаче просто из-за того, что неправильный способ вывода выбрал.

                По крайней мере моя посылка с cin/cout, endl и без выключения синхронизации с stdio уверенно заходит.

                → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Не очень понятна точка зрения. Обжечься на таком же моменте с более сложной задачей тебе было бы менее обидно? o_O

              → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Ладно, предлагаю на этом закончить спор. В конце концов каждый останется при своем. А по задаче — на то воля автора.

              → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have experienced the same problem -TLE in my java solution. We should use StringBuilder instead of println all numbers individually

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Div2 C i implemented a binary tree, and for the solution simply printed the inorder. This gave TLE . I'm not able to understand why

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Probably because the task was made so a solution using most binary trees (which are generally efficient asymptotically, but slow in real time) would get TLE. The idea itself was incredibly simple (2 stacks), so the time limit was probably out of reach with a binary tree structure.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    if(i == strlen(s)) — probably, strlen is computing on every step, which results in quadratic time.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Yes, that was the issue :-/ Feel so stupid. :|

      → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Someone explain me please, how to solve the problem "Good Sequences" (D div2 and B div1)?

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 4   Vote: I like it +4 Vote: I do not like it

    Let's compute d[x] — the length of the longest sequence with the last element (you don't need it's actual value) divisible by x.
    Suppose you already have some sequences, and you have array d as the information about them. And what you want is to know what sequences can be extended if you add number r at the end of them. Those sequences must end on some value, which is divisible by some (> 1) divisor of r. So to update the answer you just iterate over all divisors of r (that can be done in sqrt(r) time).
    Actually, you can ignore any non-prime divisors of r, however, that is not necessary.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      In fact it can be done in O(nlogn) time using a preprocessing with the sieve of Eratosthenes.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 2   Vote: I like it -8 Vote: I do not like it

        Well, in fact, one can even put all needed primes into his/her source code. ;-)
        UPD. ...and this will make his/her solution a bit faster disregarding the same asymptotic complexity.

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          But it doesn't change the complexity. In fact sieve works in O(nloglogn). But you must always check divisiors of r (and it takes O(logr) pessimistically). That's why the whole complexity is O(nlogn).

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            The sieve of Erathostenes can be optimized to O(r). Checking of prime divisors takes O(number of primes <= sqrt(r))=O(sqrt(r)/log(r)). (If r is a large prime or a multiple of 2 primes close to sqrt(r), for example.) But there are at most lg(r) distinct prime divisors (actually, even less — for the given constraint r <= 100000, it's at most 7 as opposed to ceil(lg(100000))=17). So that'd give a total complexity of at least O(n sqrt(r)/log(r)).

            → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Sorry for stupid question, but can author/admin publish test #5 of Div.1 C?

Or, can somebody tell what is incorrect in 2974379? (Unfortunately, it's rather cumbersome (russ. громоздкое) :( )

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    There is int overflow in 3 places in your code. values[i]*a and values[i]*b aren't necessarily fit into int.

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone help me? Something strange has happened.

My solution on A got TLE at the contest, but when I submitted the EXACT SAME code after the contest, it got accepted with the time of 717ms! (TLE:2964261 / AC:2974157) What happened?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Compilers are different. This solution gets TLE on MS C++ and AC on GNU

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      I didn't notice that. Thank you very much.

      → Reply
»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Blue again :) ! I really liked the problems :) ! And the plot was very cool too ! Thanks a lot for this great contest :)!

→ Reply
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Anyone knows why scala is so slow on codeforces? It's supposed to be a fast language.

→ Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I wrote editorial slides about the problems Div1 A and Div1 B(Div2 C and Div2 D). (But in Japanese)

http://www.slideshare.net/DEGwer/escape-from-stones-16092976 http://www.slideshare.net/DEGwer/good-sequences

I will write editorial in English soon.

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Div 2 E,Can Someone explain why we need to put 2 overall max values + 1 color max values to change the state for eg. 2966487 why can't it be done in 1 overall max + 1 color max...

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You need max in the same color and max in other color. So, if overall max is in this color you need another (second) max.

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice squirrel!!

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B (Div 2), with this test case:

3

1 10 1

The problem statement says that finding the minimal time to eat all nuts so the answer should be 16 (first tree -> third tree -> second tree), but the answer of tutorial is 24 (first -> second -> third). Or I don't understand this problem correctly ? Sorry for my bad English. Thanks!

→ Reply