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

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

Приветствую сообщество Codeforces.

1 декабря 2014 года в 19:30 MSK состоится очередной раунд Codeforces #280 для участников из второго дивизиона. Традиционно, участники из первого дивизиона могут участвовать в соревновании вне конкурса.

Это мой первый Codeforces раунд. Надеюсь, он вам понравится.

Большое спасибо Максиму Ахмедову (Zlobober) за помощь в подготовке задач, Марии Беловой (Delinur) за переводы на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon.

Участникам будет предложено пять задач и два часа на их решение.

UPD: Разбалловка стандартная — 500-1000-1500-2000-2500.

UPD: Спасибо всем, кто принимал участие в раунде!

Поздравляю победителей:

1.alex_y

2.wingemerald

3.Eric94

4.Zpw987

5.rabbit_TR

результаты

UPD: Разбор задач здесь.

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

»
10 лет назад, # |
  Проголосовать: нравится -37 Проголосовать: не нравится

thanks MikeMirzayanov and Zlobober and Wild_Hamster for this contest :)

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

Fixed :D

»
10 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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...

»
10 лет назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

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

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

Что, 1 декабря?!!

»
10 лет назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

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

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

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

  • »
    »
    10 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +27 Проголосовать: не нравится

    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!!!

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +60 Проголосовать: не нравится

    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 :(

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        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

»
10 лет назад, # |
  Проголосовать: нравится -28 Проголосовать: не нравится

Вокруг города автора прикольные названия населенных пунктов. В России они обычно попроще, а тут прямо воображение просыпается)

Слободка. А че, хорошее название!
Старый угринов. Ну че так невежливо? Ладно, Средний угринов.
Стебник. Хочу туда, там весело.
Кто мне может нарисовать, что за звери - Пшеничники ? А курить их можно?

»
10 лет назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится -56 Проголосовать: не нравится

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

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

Автор тролль.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    не просто так спрашивал походу ) видимо в контесте будет задача на максимальную подматрицу, состоящую из единиц

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

    Мда! Несколько дней назад решал эту задачу из архива, она из Div2 то ли C, то ли D

»
10 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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?

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

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

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

      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.

»
10 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

небольшой вопросик: когда будет раунд для див1?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    В первый же день, в который я 100% не смогу зайти.

    А вообще — до НГ один будет точно (goodbye-round уже традиция). Хотя мне кажется что будет минимум два.

»
10 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

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

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 :-(

»
10 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Brace yourselves, clone accounts invasion incoming.

»
10 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Контест очень хороший для див-2, сложность идеальна! Нет вот этих задач Е с 5 решившими, которыми часто грешили в последние годы.

»
10 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Нехорошо править задачу Е без клара, хоть и правка была вполне очевидна.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    А в чем правка состояла?

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      в том, что можно вывести любую точку пути. изначально вообще было не понятно, какую именно нужно выводить...

»
10 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

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

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

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится -14 Проголосовать: не нравится

How was E supposed to be solved?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

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

      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

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    i gave Sherbina_Evgeniy -1 ... :|

»
10 лет назад, # |
  Проголосовать: нравится +38 Проголосовать: не нравится

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.

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

    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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится -11 Проголосовать: не нравится

        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.

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

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

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

    So, will it be rated?

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

What was pretest 3 in D :\

  • »
    »
    10 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +4 Проголосовать: не нравится

    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
    
»
10 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

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

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

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

Задачи слишком простые. Я не решил Е только потому, что сначала правильно прочитал условие (включая gcd( n, dx ) = 1 и gcd( n, dy ) = 1 ), придумал решение, потом придумал тесты, на которых это решение валится, но эти тесты слегка не удовлетворяли gcd, о чем я вспомнил только за 5 минут до конца.

UPD: Решение по Е, которое я придумал на 60 минуте от начала контеста — зашло. P.S. Впервые выдался такой шанс за контест решить все 5 задач, впервые решить Е во время контеста, и я его упустил =(

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Слишком простые? Думаю, что нет... По-моему, таблица результатов во втором дивизионе достаточно сбалансирована +как заметил dalex, сложность задачи Е была такой, что и халявой не назовешь, и решило не 5 человек за контест, что, как мне кажется, большой плюс для контеста.

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

Total this contest = problem B,test 3

»
10 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

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 ?

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

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    It is fair, since it is unavailable for everyone.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        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.

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

      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.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +7 Проголосовать: не нравится

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

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

      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.

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

dreamoon_love_AA is first place in div2 but unofficial :)

»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

dreamoon_love_AA is first place in div2 but unofficial :)

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

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

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

»
10 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Thanks Wild_Hamster for this nice problem :)

»
10 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Как решать C?

UPD — прочитал решение, понял что там сыграл фактор кривых рук...

»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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);

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

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

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

»
10 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
10 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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 :|

»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

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

When will rating be updated?

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

Everybody(div2) waiting for rating.

»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Was it an unrated contest?

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

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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 )

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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).

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    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. :)

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

Why is problemset page blocked by the admin?

»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Ratings are updated! :) Cheers!

»
10 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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.

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

It was a lucky contest for me....

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

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

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 <= .

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

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

  • »
    »
    10 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится
    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.

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

      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.

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

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

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

Deleted

»
10 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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 "<" ?

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

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.

  • »
    »
    10 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
    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.

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

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

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