Wild_Hamster's blog

Codeforces Round #280 (Div. 2)
By Wild_Hamster, 10 years ago, translation, In English

Greetings to the Codeforces community!

Regular Codeforces round #280 for participants from the second division will take place on 1 December, 19:30 MSK. Participants from the first division are able to participate out of the contest.

It is my first round on Codeforces. Hope you will enjoy this round.

I want to thank Max Akhmedov (Zlobober) for help with preparation of this round, Maria Belova (Delinur) for translation of statements and Mike Mirzayanov (MikeMirzayanov) for great Codeforces and Polygon systems.

Participants will be given five problems and two hours to solve these problems.

UPD: Scoring is standard — 500-1000-1500-2000-2500.

UPD: Thanks to everyone, who participated in the round!

Congratulations to the winners:

1.alex_y

2.wingemerald

3.Eric94

4.Zpw987

5.rabbit_TR

standings

UPD: Editorial is here.

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

Comments Comments (125)
| Write comment?
»
10 years ago, # |
  Vote: I like it -37 Vote: I do not like it

thanks MikeMirzayanov and Zlobober and Wild_Hamster for this contest :)

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

Fixed :D

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

I had a lot of school's exams in this week and I didn't practice for coding...

But i like to join the contests...

God please help me...

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

    Well I have a philosophy test tomorrow but it seems like I don't have much any time to prepare =P

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

    Same I many exam today. I study right now. English is bad subject,i fail exam

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

If I am correct, this is the first time a wild hamster has prepared a codeforces round.

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

    I bet, "It is my first round on Codeforces."

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

What about the scoring system, dynamic or regular/normal... ?

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

    I bet, "Scoring will be announced just before the round starts."

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

      "UPD: Scoring will be announced just before the round starts."

      What a prediction.

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

    Is Down vote became a tradition in CF, just asked a simple question and got so many Down votes... Really Unexpected... :(

    UPD: Scoring will be announced just before the round starts.

    This line was added to announcement after my post, and some so called smart didn't get that while pressing down vote.

    You may be so smart but Don't think some one that much stupid!!!

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

      The question about the scoring system appears every time the new round announced. Obviously, the community is quite bored with that tradition.

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

    In my opinion, announcing scoring system is not important, as it will be clear when the contest begins. Knowing problems' score before contest starts doesn't help you solve problems much. An announcing contest blog should introduce something about problem setters so that everybody will know them :D

    P/s: A lot of comments in this blog got downvotes, but I hope your guys will upvote my comment. Please. don't downvote, please :(

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

      Heh, just want to mention that i know few guys saying "i have some other things to do in the evening... I'll find time to participate in CF, but only if there will be no dynamic scoring" (as you may guess, they don't like dynamic scoring for some reason). And maybe someone else have some other strange preferences:) But announcing of problem values for a normal scoring does not helps a lot — because it is often completely meaningless and does not describe relative problem difficulty — like in round 275, when both B and C had 1500, but B was solved by ~10 times more users than C.

      For me it seems meaningless to update blog in last minutes before contest — one may just enter contest few minutes later and he'll see values there:) But i don't know why scoring distribution isn't published a long time before contest — they just don't want to, or it is really decided just a few minutes before the start.

      P.S. It is risky to ask about upvotes:) Well, i'll upvote you, as you wish, pushing one button takes much less time than even typing of this message and it is an easy way to make a kind gesture:) But why do you care about upvotes? I can't understand point behind it. Contribution score is even more useless than rating, isn't it?

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

        Yes. I agree! Contribution is not as important as rating on Codeforces. It was made only for fun, and to make the forum more active, I think. But it will be a bit unhappy if my blogs, comments got downvote. Why? It means that people seems to hate me :( The last sentences on my above comment is quite simple: There's a fact that a lot of other comments got downvotes, and I don't want my comment to get dislikes.

        Sometimes, I try to find the answer of the question: "Which type of blogs, comments have most upvotes?" This question is not for coders, but it's an interesting and non-easy question. :D

        Ok. Asking about upvotes is risky, I won't do it anymore :D

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

Ivano-Frankivsk wooohooo :-)))) best wishes, hope for great round.

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

    all right, maybe I've gave too much emotions to that post, sorry ;(

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

      Are you talking by yourself?

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

        hopefully no..

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

        In fact, it'd be strange if he couldn't talk by himself, but needed someone else's help even with talking :D

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

1 December 1918 – Transylvania unites with the Kingdom of Romania, following the incorporation of Bessarabia (March 27) and Bukovina (November 28), thus concluding the Great Union

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

    It`s wrong to be proud of your country?! Because i received so many downvotes.

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

I have a general question. Hope you can answer: Why is always the scoring announced just before the round starts? Is there a specific reason?

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

    It was asked before or here, but always without the answer...

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

      I can answer this question. I was an author for several rounds, and every time the complexity of the problems was not precisely clear. But since there is always a lot of more important work to do right until the contest, we usually agreed to the score distribution shortly before the start, after other work was done.

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

The surprise is not only this contest but also we have another one after just 2 days :)

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

I'm afraid it won't be rated. Servers are slow for me for about one and half hour and the contest didn't start yet :-(

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

    It seems to be better, for last half an hour, we will see...

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

I'm afraid it will be delayed for 10 minutes :)

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

Brace yourselves, clone accounts invasion incoming.

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

I think there will be a lot of fails on C while system testing! Good Luck!

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

What's the meaning of problem D? @.@

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it -14 Vote: I do not like it

How was E supposed to be solved?

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

    Notice that answers for a[i] and a[i]%(x+y) are same. After it we can find answer in the range of 0..1 second with help binary search. I mean we find exact time, when happened last hit. And we will determine who is made it. Sorry for my English.

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

      Hey I wanted help with E actually. I edited my initial comment, typo.

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

    Vanya's character shoots every 1/X seconds and Vova's every 1/Y seconds. Let's make time pass more slowly by a factor of X*Y. Now Vanya's character shoots every Y seconds and Vova's every X seconds. Using binary search you than calculate when a monster dies, and checking if what characters shoot at that time is trivial.

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

      for problem D I didn't use binary search, instead I tried to see what can happen in one second? Well, in one second we can have as many as x + y hits in the worst case. So you can have an array of size x + y where in position i you store who actually makes the ith move. For simplicity my array was 2 dimensional of size [x + y][2] because it's possible that both players can make a hit on the ith move. After one second, the same things happen so you don't need any additional information about for example the fourth second because it's the same as the information in the first second. Now to answer the queries you just take the query move ai and then output myArray[ai%sizeOfmyArray]

      complexity is O(x + y) to create the array

      and O(n) to answer the queries

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

    WTH ??!!! first you ask about D ... people answer your question and you change D to E???

    i gave Sherbina_Evgeniy -1 ... :|

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

Sorry for failure in last minutes, I'll investigate it. It seems it works good almost all the contest, but failed the end. Sorry again.

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

    Good evening!

    I've sent 2 solutions for C just in case. I thought that it's logical, that the second try will be ignored. Why the first try is ignored? It has passed the tests and would've given more points. Is this normal behaviour? I've missed it...

    01:28:17 Попытка игнорирована [претесты] → 8919160 01:53:40 Полное решение [финальные тесты] → 8921562

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

      Suppose that you've submitted a problem, and it passes pretests. Later you find bug in your solution, fix it and resubmit. It still passes pretests. Would you be happy if the second solution is skipped?

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

        It should not be skipped, probably both solutions should be tested, and the best one should be chosen...

        Ok, maybe this is done to avoid overloading of system testing with a lot of submitions which pass the pretests.

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

    This is not the first time to fail in last seconds by the way.

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

    So, will it be rated?

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

What was pretest 3 in D :\

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

    Test:

    8 6 10
1
2
3
4
5
6
7
8

    Answer:

    Vova
Vanya
Vova
Vova
Vanya
Vova
Both
Both

    May be answer in your program:

    Vova
Vanya
Vova
Vova
Vanya
Vova
Both
Vova
    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You are right. I counted both together shooting as 1 shot instead of 2. How stupid of me! -.-

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

Last 20 minutes, unable to hack. Anyone else on this boat? :-)

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

    Yup , also got the test file generated and couldn't hack in final 5 minutes.

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

Total this contest = problem B,test 3

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

Codeforces is temporary unavailable (last few minutes before the end) is that fair ?
what about the case of one solved problem correctly and didn't get the chance to submit it before the end of contest by 1 minute
what about the case of hacking someone solution and the system down before hack ?

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

    Worse yet, unable to read other people's code in an attempt to hack them. Yup, same boat.

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

    It is fair, since it is unavailable for everyone.

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

      Not if someone else started hacking before the system failed to deliver. Then it is unfair since only people who planned to hack earlier got the privilege to do so.

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

      think before write something. everyone has different strategies in contest time. how come a red coder says its fair? just cant blv my eyes

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

      some people read all the problems first then sit to solve, some do it one by one. its completely non-sense to say it was fair.

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

        Please don't misunderstand me. I think the only reason to ask "Is it fair?" that makes sense is to question the fairness of the organisers of the contest. I personally believe that the staff of Codeforces is dedicated to prevent any mishaps. But if it is accidental, of course it is not fair in that sense that different participants are affected unequally. It just doesn't make sense to me that the organisers' actions are to blame in such situations.

        And please, don't color-discriminate people. I was only expressing my thoughts.

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

      i solved the problem D in time, but could not submit it in time. It might be fair for div1 coder like you, but don't mock at tiny coder like us, at list my thought goes this way.

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

      It is "fair" in that the circumstances are the same for everyone, but it isn't "fair" in that different people are affected differently.

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

      I think the definition of "fair" should involve "follows the initial premise". Simple example: if, an hour into the contest, an announcement was posted that in order to speed up the testing, all submission results will be random (with some distribution), it would not be fair (by common sense, it's just fucking around, "fair" has no meaning), even though it affects everyone equally. In that sense, unexpected fails can't be considered fair.

      That's not to say I disagree — it actually was fair, since the fails aren't exactly unexpected anymore... and anyone who jumps into contests without checking what they involve takes the risk on himself.

      Still, the question to ask here is not about fairness. It is fair, and it sucks. And contests should be fair and fun.

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

dreamoon_love_AA is first place in div2 but unofficial :)

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

    I guess dreamoon won't be first place when he gets into div2.

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

If I view someones code for Hacking, but if I don't click on Hack It! then does CF deduct any score?

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

How the user rank 201 in official standing solve two problems at same time ? :D

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

Thanks Wild_Hamster for this nice problem :)

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

Hi,

I think there might be something wrong with app context for executing C# code. In problem B, my numbers were printed with "," comma separator, while answers were expected to be printed with "." separator. I wasn't using any formatting, i was using just: Console.WriteLine(decimal);

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

    In Russia ',' is usually used instead of '.', but anyway, it's incorrect servers' setting.

    P.S. I've just checked, for java submissions, dot is used.

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

Could anyone help me understand why 8922945 and 8922927 with identical code but different compilers give different answers on the test #1 in C?

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

For the question B, I was getting wrong answer on pretest1. I changed long double to double in my code . And it got accepted!! Can anybody explain me how did it work ? My Code for the same

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

My solution for D is the following http://codeforces.net/contest/492/submission/8923198 It gives Memory Limit Exceeded for test 17.

If I do not store the elements in an array I passes all the tests (http://codeforces.net/contest/492/submission/8923768), but based on the input size the array should be max 400 KB. When reviewing test 17 with this modification I get a smaller memory usage with 100 MB.

I think this is not caused entirely by the array but because of the flushing of PrintWriter in Java. Do you guys have any suggestions/recommendations?

EDIT: I just checked and the output buffer and input buffer should be 8 MB each. I have absolutely no idea what the problem could be :|

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

Rating is too Late.........?

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

When will rating be updated?

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

Everybody(div2) waiting for rating.

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

Was it an unrated contest?

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

Hi, I'm wondering what the best way is to test an algorithm that I couldn't quite finish after the contest is over. I entered a virtual contest, but that doesn't indicate what was wrong with a submission either. Any way to just play with the problems for training purpose?

Also: Is this the best place for questions like this?

Best, Esuhi

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

    Just go to contests tab and click on "enter" instead of "virtual participation" and you can submit all the problems in practice mode. (Though you may have to wait until the virtual contest is over before you can do that :p )

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

    Try the "register for practice" button on the contest dashboard. If you don't see it, you're already able to submit (and see tests).

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

    Edit : Looks like I replied few seconds late. :)

    Yes, you may have to wait for some more time for that. Usually the contest problems are added as "Practice" problems in the problem set archive, tagged by contest id etc. Currently I see that submissions for practice problems are blocked temporarily by admin. Once its unlocked by admin, you can submit/test your solution there and test cases (system tests) will be run against your solution for the verdict. Hope this answers your question. :)

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

Why is problemset page blocked by the admin?

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

Ratings are updated! :) Cheers!

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

Was I the only one that "misread" problem D and thought the swing timer doesn't reset every time they kill a monster? There is nothing in the problem statement that says otherwise, until you run it on the first test.

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

    Well, you are right. At first sight, I also was in a dilemma.

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

    That was my first understanding as well. But I saw that it would not work for the provided input. BTW, How can one ask for clarification? Is that possible on Codeforces?

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

      Yes, you can ask for clarification on the problems list page.

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

    this is exactly where I got stuck

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

It was a lucky contest for me....

And the best contest in codeforces so far.... :D

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

Hi. Can someone explain to me why at the C problem , I get runtime error if I use the compare function

bool cmp( const pair<long long ,long long> &x, const pair<long long ,long long> &y) { return (x.b<=y.b); }

but accepted when I use < instead of <= .

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

    I think your compare function must be transitive.

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

    Compare must not be true for both (a,b) and (b,a) at the same time — most STL operations involving comparison functions check this with an assertion, which explains the RE.

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

http://codeforces.net/contest/492/submission/8914525 Can someone explain where am I wrong , can't figure out from the failed system test case for problem C

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it +6 Vote: I do not like it 
    vector < pair < int, int > > v(n);
long long ans = 0, add = cmp - sum, here;
ans += here * v[ptr].first;

    You multiply long long by int which makes the result of multiplication lower than intended, therefore the answer is less than it's supposed to be.

    EDIT: But I'm right! You just have to switch all ints to long longs and your solution will pass! I just tested it: 8928368. This is absolutely same as your submission except I changed all ints to long longs

    EDIT2: Ok, this is not even funny, why am I getting downvoted for trying to help? And people wonder why I have trust issues.

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

      Its not that line. here is a longlong so the result of the multiplication is still a longlong. I'm going to guess the culprit is cmp = avg*n*1LL — since multiplication is left-associative, it multiplies avg by n before converting the result to longlong.

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

Waiting for editorial. Can anyone please explain how to solve E?

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

Can anyone explain why this submission for problem C is giving RTE on test case #11, and why is this code getting accepted? All i have changed is in the comp function: "<=" comparison to "<" ?

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

Sorry if this isn't the right place to ask clarifications.

For Problem C) I checked the editorial and my java solution appears to be correct. All I am doing is a sort and then a O(n) linear calculation, but my code is timing out in 1000 sec for the worst case test. (10000 items). Test for 1000 items is 92 ms, so it appears 10000 is probably > 920 ms but my code looks right. 8920114

Can anyone clarify? This is really puzzling. I don't know if I should switch to C++ because of this.

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

    1. You use LinkedList, which has not random access, so you sort in O(n2). Try using ArrayList, instead of LinkedList

    2. Java Scanner class is really slow. For example, see submission 8953230, class FastReader.

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

      I saw somewhere that it is possible to improve performance of Scanner by upto 7 times by using the next() method and doing a type.parse (like Integer.parse) than to do a nextInt() as it takes out regex processing. So it looks like the FastReader is using this idea as a wrapper.

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

        I suggest you reading source code. It doesn't use Scanner, it uses BufferedReader

        → Reply