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

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

Всем привет!

В ближайший четверг 30 мая в 19:30 MSK пройдет Codeforces Round #186 (Div. 2), автором которого являюсь я. Это мой первый раунд на Codeforces и я надеюсь что все получат удовольствие от решения задач на нём.

Спасибо Геральду Агапову (Gerald) за огромную помощь в подготовке раунда и Марии Беловой (Delinur) за перевод условий на английский. Также, хочется поблагодарить Ваню Здомского (ballon), за то что он протестировал раунд.

Разбалловка сегодня такая: 500-1000-1500-2500-2500

Good luck & have fun! :)

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

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

I hope that the contest will be rated.

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

    This is not your problem!

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

    That's why you have to respect this simple rule : "You may edit your comment only for fixing grammar mistakes or small changes. Do not change the main idea of your comment."

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

Fast announcement.

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

hope this round be successful

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

Let's get ready for fun!

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

Александрийцы, вперёд! Я надеюсь, что у Романа Furko получится нечем не хуже, чем у Сергея Нагина (Sereja). Я очень рад за вас ребята!

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

    НИчем не хуже и запятая перед "ребята".

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

      Grammar nazi?

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

      У нас сообщество филологов и лонгвистов? Главное, суть, а меня, как видно, поняли.

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

        После "главное" нужна не запятая, а тире.

        "грамотно говорить надо только специалистам в области языка" — очень популярная отговорка для тех, кто не умеет этого делать. В таком случае можно предложить Вашему работодателю выдавать Вам зарплату не точно, а примерно — он ведь не математик.

        Про "логвистов" умолчу — это, надо полагать, опечатка.

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

Будем надеяться, что этот контест не будет третим Китайским контестом, как два предыдущих!

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

    Сомневаюсь, что человек с именем Роман Фурко китаец.

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

      Я имел ввиду не его национальность, а сам контест)

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

        Обидно, когда минусуют и не знаешь как это остановить.

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

          ага, еще обиднее когда пишешь новый комментарий, и его минусуют больше.

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

            Так не пишите такие коментарии!

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

              Судя по логике этой ветки данный коммент насобирает минусов!

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

                А этот — плюсов!

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

                  Хотя скорей всего — огребу минусов за все три коммента :)

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

Lets just hope this contest goes fine and rated. :)

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

Wish this contest will be rated. BTW thanks for early announcement. :)

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

Oh MY god!!!I have taken part in three CF round...But I am unrated now(Because all of those three round have something wrong...)= =...SO I don't want to miss this one ....But ..At 23:30 on Thursday, I will on the train to Chengdu to take part in a invitation match.....WTF....Who can help me!!!!!

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

Hope this round & all participators can all be successful!

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

I hope everything will be ok this round.

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

For Furko its his first codeforces round and i hope that it will be very easy or very hard :)))

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

Надоели уже div2-раунды! Давайте нам нормальный раунд для обоих дивизионов!

Вот если взять пару задач B и C из предыдущего китайского раунда и добавить в этот в качестве div1 D и E, думаю, получился бы сбалансированный проблемсет.

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

Есть вопрос. Кто может участвовать в данном соревновании? Есть какие то ограничения?

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

THIS IS MY FIRST CONTEST IN CODEFORCES ....WISH ME GOOD LUCK T-T

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

Thinks for this round.I'm so glad it's coming soon.

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

hopefully this round will be successful! good luck everybody! :)

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

This is going be heavy loaded contest. 2177 and still counts.

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

After hard Chinese problems, I think easier European.

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

Gl && hF

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

Вопрос по-поводу системы оценки.

Если на контесте я первый раз отправил решение — AC. И второй раз отправил — AC.

И заметил, что в таблице по задаче появился +1, и соответственно снялись балы.

На системном тестировании их вернут? :(

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

    Нет, потому что учитывается только последняя попытка, прошедшая претесты. Сами посудите: например, вы отправили решение, оно прошло претесты. Потом вы поняли, что решение лажовое, исправили и переотправили. Почему вам должны возвращать баллы?

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

      Я имею в виду, что если моя первая попытка окажется правильной на системном тестировании.

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

        Нет :) Почему это должны сделать? Согласитесь, это будет нечестно.

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

        Первая попытка просто не будет тестироваться на системных тестах.

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

          Спасибо. Я этого не знал.

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

            Привык, что на ejudge засчитывается первая правильная.

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

This is the most unlucky hacking attempt, isn't it? :(

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

wasted so much time trying to find out why my brute force solution didn't work for the second problem when a very easy dp implenetation I made in the end passed all the pretests... yet another bad contest for me :(

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

how solve problem D?

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

    I was going to ask the same question!

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

    dp[i][j] = minimum cost to repair j holes from the first i holes Complexity: O(N^3)

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

      how do steps?

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

        Try every i <= k < N, dp[k+1][new_j] = min(dp[k+1][new_j], dp[i][j] + minCost(i, k)). minCost(i, j) can be precalculated in O(N^3).

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

          How to precalc minCost(i, j)?

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

          Uhn!Could you explain what is the meaning of the recursion formula and the 'minCost(i,k)'?

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

            You have currently decided what to d with the first i holes. You repaired j from them. You try to repair every interval (i,k), i <= k < N. The cost to repair this interval is minCost(i, k) which is precalculated. You end up at dp[k+1][new_j] because you have already decided what to do with the first k+1 holes and you repaired some additional holes. Also, you can decide not to do anything at this hole (go to dp[i+1][j]).

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

    dp[i][j] = minimum cost for fixing j holes out of first i holes.

    dp[i][j] = min(seg.cost + dp[i-seg.size][j-seg.size]

    where seg = {l,r,c} and all seg.r == j

    I didn't submit as I was a minute late, but I believe it to be correct.

    UPD: Nah, not correct logic, small modification required to it.

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

      My idea is the same as yours but got wrong answer on pretest4.In fact,we won't fix a hole more than one time. try this test: 3 2 3 1 2 1 2 3 2

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

    This is my idea but my code wasn't right for samples: First I define dp[i][j][k] = minimum const to fix at least k holes in j first holes using first i companies. while companies are sorted by their right points. And the update: dp[i][j][k] = min (dp[i — 1][j][k], dp[i — 1][j — (j — company[i].left + 1)][k — (j — company[i].left)] + company[i].cost)

    I saw that the difference between second and third dimensions of dp is always the same, so I omitted third dimension. And so this dp is my solution: dp[i][j] = minimum cost to fix at least j — n + k holes in first j holes using first i companies while companies are sorted.

    Is this solution right ? :-?

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

Как решать Д-шку ?

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

I hope tests for problem C are good enough to fail Java solutions which use Arrays.sort().

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

    Such test are included to pretests.

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

      Yeah. I couldn't pass test 11 on Java. I finally pass them, when rewrite solution to C++

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

      Thanks for trying to include that test, but my solution passed pretests just to time out on test 48 (Is that a hack input?).

      I guess it is my fault to keep forgetting not to use Arrays.sort() on arrays of primitives

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

        I add shaffle to my solution in Java and get TL too. Probably we need to read input data faster

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

    I think it's 100% unfair. Quick-sort is the same for every language, Java probably have more overhead, but again — I think it's unfair.

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

      Shaffle array before sort it in Java.

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

        Ok. I got it, it looks like tests are written to kill exactly Java implementation of quicksort. Good job!

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

      The default way of sorting things is not the same in every language. Modern compilers (GCC, Python, .NET starting from version 4.5, Java when sorting objects) tend to use worst-case algorithms, mostly Introsort and Timsort. However, in Java, integer sorting still uses double-pivot quicksort which is O(n2) in the worst case.

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

        So, is it way to fix it? Write your own sort?

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

          Randomly swap some items of array. And after that u can use Arrays.sort()

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

            You may want to know about Collections.shuffle routine.

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

              Yeah, according to javadoc — Collections.shuffle runs in linear time. So it's a good solution. Thanks

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

          Or, box int-s into Integer-s and use an object sorting routine (Collections.sort?). It may be slower though in the general case.

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

      submit in java 7

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

    http://docs.oracle.com/javase/6/docs/api/java/util/Arrays.html#sort(int[])

    The sorting algorithm used in Java for Arrays.sort(int[] arr) is tuned quicksort which offers very good average case performance.

    Many contestants used Arrays.sort() today for problem C and have passed System tests. I think if the solution fails, the problem lies elsewhere.

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

      My solution was using Arrays.sort() and failed pretests with TLE.

      The same solution is passing after these changes: - Use FastScanner implementation by martinezgjuan (which uses BufferedReader + StringTokenizer). - Use Java 7 (not Java 6)

      Now is passing with worst running time 951ms (no need to shuffle the array).

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

У меня в конце произошла странность. На таймере в комнате еще минута оставалась, а в общем положении уже написало что соревнование завершено.

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

I am really curious about what the pretest 4 of problem D is.

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

Тот самый момент, когда ты — тот самый Лев Илья

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

that was a great contest after ... :)

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

May someone introduce the intended method for Problem E ?

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

anybody knows why system testing is taking very long time today??

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

Problem D is really beautiful, solving it was tons of fun!!

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

Furko recpect and yvazhuxa

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

O(N3 + M) on problem D got me TLE :(

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

    It's funny. My O(N^4) passed.

    Sometimes the speedy inner loop is more important than the asymptote. I wrote carefully to eliminate 31/32 of the transitions in the dp without computing them.

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

    haidora1, I think that the cycles

    for(int n = 1 ; n <= N ; n++){
    for(int k = 1 ; k <= n ; k++){
    for(int i = 0 ; i < f[n].size() ; i++){
    for(int h = n ; h >= 0 ; h--){
    ...
    

    if f[N].size ~ M , give you O(N3 + MN2) .

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

Thank you Mr.Furko I enjoyed the contset was good although I have a low rank ^_^

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

TLE-SOLUTION passed solution why the second solution passed and the first one get TLE

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

Wow, so many AC for problem C which pass with execution time of exactly 2000 ms, which is the TL for that task. Ofcourse on the other hand some codes definitely fail by only a few ms in this case. Now I wonder — is the TL set a little too low and hence might reject some codes with TLE even with the correct idea/implementation of solution OR is the TL a bit too high and that's why it lets some weaker codes pass that actually shouldn't?

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

unrated?

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

когда появится обновление рейтинга?Furko — хороший контест.

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

So, what is the point for CodeForces to support several languages as they do if you will have problems that cannot even run within the time limits using that language, regardless of how efficient you do it. You may have the exact same code in Python and Java, but you get TLE in Python (The same happens sometimes with Java and C++). Then, why support Python? Why don't you just get serious and support languages in which problems can be done like in TopCoder? Or just increment the time limit for certain languages, whatever you feel more confortable with. That would be a lot easier for contestants! In my opinion, it is NOT fair to get a problem wrong when the algorithm is identical to others who got it right, being the code language the only differentiator.

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

    Can't agree more. The same algorithm runs in time if coded in C++, but in python it gets TLE. This happened in problem C for many Contestants.

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

    Python is easier to write correct code in than C++.

    The syntax is simpler, the edge case and corners are less likely to cause you trouble, the array bounds are checked so that errors show up right away, debugging and tooling is better, Python has a repl so you aren't always compiling-testing-compiling-timing just to try an idea, and you don't have to worry about static type declarations. C++ is a pain with cruft from legacy implementations, the syntax is verbose and cryptic, the template system is full of hidden troubles waiting to bite during a contest, and even the compiler error messages are indecipherable.

    But C++ runs about ten times faster than Python.

    So there are advantages and disadvantages to both. You are allowed to switch languages between problems. You can even pick your algorithm and then choose your language for each problem based on speed and convenience.

    Being able to choose wisely is part of competing here.

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

      I have to disagree with you there. I know Python have a lot advantages over C++ in terms of readability, testing and debugging; that's the main reason I code in Python rather than C++, or even Java that I use as my second choice.

      I believe it can be challenging enough to come up with an algorithm that works for a particular problem and also have a quite good and reasonable complexity. So, why would my solution be wrong when is as good as yours?

      I can see how almost every C++ coder codes everything in C++, but you can say that you have to "choose wisely" your code language for a particular problem, when even the easiest problem you already code it in C++. So, when do you actually choose? I believe that is not the reason.

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

      I think the main issue here is that it was not possible to get AC in Python with any solution. While I understand that you have to think about efficiency twice in python (sometimes naïve code gets accepted only in C++ while in other languages you have to think of smarter solutions), I still consider that the most important ability to learn in these competitions is algorithmic skill, not language syntaxes or quirks.

      In my opinion, is better if, for these kind of problems, Codeforces won't accept Python to avoid the misleading information that is possible to solve the problem with Python.

      In short, we (at least me) are not here to learn the syntax and tools of languages, we are here because we would like to solve algorithmically challenging problems.

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

      I think the constraints were not very well checked for the problem C. My code in Java barely passed the tests (1880ms) by even using fast custom made I/O routines and with an O(n lg n) algorithm. Had I not used the fast I/O library my code would have easily failed. And Java is not even one of the slowest languages supported. So either time limits should be loosen up a bit and maybe also increase the input constraints so algorithmically worse solutions fail even in C++.

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

      When I see n <= 10^5 and I have a O(nlog(n)) or faster solution, Python is the first choise.

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится
    Or just increment the time limit for certain languages

    So… You have a job, your boss gives you a task and you implement it in Python. Everything is great, until customers start complaining that they have to wait minutes for your software to run. But you don't see it as a problem and tell your boss: "I know, it's Python, just tell them to wait more!" Does this sound realistic?

    In my opinion, programs should be judged against real-life criteria, such as real running time and memory usage, not against arbitrarily chosen adjustments so that "different languages are equal". This is fair, and treating programs in different languages differently is not fair. If your language fails to be on par with others, then it is the language's fault, not Codeforces' fault.

    It is about using the right tool for the job. C++ and Python have their advantages, and also have their disadvantages. C++ is fast, but hard to program in. Python is easy, but slow. You consider both options (which is more important — short code or fast code?) and choose the better tool in order to achieve a better result. If you knowingly chose the inferior tool, then it is your mistake and you will get penalized for that.

    Now, here you might say that you had no idea your Python code would run so slow. But this is just a part of the learning process — you tried it and received negative feedback, and this will affect your future decisions (you will likely choose not to do the same thing again).

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

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

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

My same code got Time limit exceeded in contest but Accepted in practise...

I wonder why???

TLE code : 3800440 AC code : 3803673

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

It is really funny, IceTube has become purple and Goldensea is blue ! and I think he can't compete in Div 1

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

I had no idea about the difference in runtime between read using scanf/printf and cin/cout in C++. I always use scanf/printf in codechef and spoj but I was confident here in codeforces. I got TLE in problem C and I change cin/cout by printf/scanf and I got AC in 1 sec. Great, I will use scanf/printf here too.

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

Спасибо за интересные задачи и хороший контест. Рад был порешать.

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

It seems like many participants' solution of problem C got TLE during the contest but the exact same code gets AC after the contest! This is really unfair for the people who've faced this.

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

Any quick explanation on how to solve Problem E?

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

    Greedily, i in set A should add m-i-1 in set B. If the amount of i are more than m-i-1 's, we should add m-i-2. Before that wo should do i+1 add m-i-2. So use a stack to solve it. Complexity O(m+n). The O(n) is printing answer.

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

What is meet-in-the-middle algorithm ?

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

    I have only used this algo once, with some help from a friend. So I might not be able to explain efficiently. Still giving it a go.

    Here's a demo of the algo -

    You have a set of integers consisting of no more than 34 elements and want to find the number of subsets such that the sum of the integers in a subset is an integer N (N is a known value).

    A brute solution would be to try all 2^34 ways, which is not efficient.

    So what we do is we split the set in two equal subsets (meet in the middle algo), try to form all possible subsets for each set and record the results (the number of results is at most 2^17 for each set), then for each element in one set, run binary searches to find upper limit and lower limit for compatible results in the other set.

    I don't know if this explanation is good enough. Maybe you can take a look at this. http://www.infoarena.ro/blog/meet-in-the-middle

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

Why my code got WA on testcases 11 ?3805151

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

Can someone give me an idea for Problem C??

I was actually trying to simulate, but I think it is unnecessary... can someon eplease help?

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

    yes, actually you don't need to simulate the assignment in your code

    the idea is to select biggest 4^n numbers then biggest 4^n-1 then 4^n-2 until 4^0

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

Great contest

Really waiting for editorial, specially for brilliant problems D and E. GL & HF!

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

TLE : 3798859 ACC : 3806006 what should i do about it?

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

3806042 why am i getting runtime error? Its working perfectly on my console

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

hopefully there will be a new round this sunday for both div 1 and 2.

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

Have nice grades....Need more practice.

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

3811425 Ilya and matrix Hi, can someone refer to above submission and tell me why it is giving TLE error. I mean i have written in JAVA and used the buffered reader. I tested the same on my laptop (a core2duo machine) for a test file with data of size 1048576 and those many numbers and it completes in 500millisecs. but i always get TLE. is my reading method faulty? or the algorithm. I only have one loop.

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

    yeah got the problem. i was using Java6, changed to Java7 got accepted in seconds.

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

In C problem,why I used cmp function(write by my self) tle but didn't use can ac!!