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

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

Всем привет!

Мы приглашаем вас принять участие в Codeforces Round #198, который начнется в пятницу, 30 августа в 19:30 MSK . Авторами задач являются я и Linh (ll931110). Мы также являемся авторами Codeforces Round 191 (Div. 2). В тот раз участники были довольны задачами раунда. Мы надеемся, что этот раунд будет как минимум не хуже предыдущего.

Linh придумал задачи D2-C/D1-A и D2-E/D1-C. Я придумал остальные задачи. Мы надеемся, что во время раунда вы потратите больше времени на обдумывание решений, нежели на написание кода. Хочется добавить, что задачи раунда не будут требовать от вас написания сложных алгоритмов. Вместо этого, все они требуют креативности, сложных рассуждений и терпения. Да, главный герой раунда — Iahub, как и в прошлый раз.

Я хочу поблагодарить DamianS, Gerald и Aksenov239 за тестирование раунда. Без них работа по подготовке раунда была бы намного сложнее. Также, спасибо Delinur за перевод задач и MikeMirzayanov за отличную систему Codeforces и Polygon.

Желаем вам высокого рейтинга и удовольствия от решения задач!

UPD1 Будет использоваться динамическая разбалловка в обоих дивизионах

UPD2 Спасибо всем, кто участвовал. Я надеюсь задачи вам показались интересными. Кажется, мое предсказание, что вы будете больше обдумывать задачи, нежели писать код, подтвердилось.

Мои поздравления победителям.

Division 1

  1. yeputons
  2. KADR
  3. ftiasch
  4. Myth5
  5. huzecong
  6. R_R_
  7. Gabaum
  8. James
  9. ifsmirnov
  10. niyaznigmatul

Division 2

  1. Azat_Yusupov
  2. angel_of_monkey
  3. molamola.
  4. iseriohn
  5. Mato_No1
  6. silver__bullet
  7. TheDude
  8. Nero
  9. khuebeo
  10. uc-nuts

UPD3 разбор (English)

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

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

can't wait to find out who's the main character in the problem statements :D

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

You call positive feedbacks yelling at you about that u couldn't manage to avoid naive solutions' passing E.

Seems legit.

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

Err... Spend more time on paper... Does that mean this round we should draw sth, like round 195? by the way,thanks for ur hard work!

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

Our teacher said that this test is made by XHXJ,really?

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

Is this an individual contest? How to know if a contest is team or individual?

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

I was dreaming for months a contest like this: no complicated algorithms, spend more time writing on paper than typing on PC.

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

Good luck every one:)

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

GooD Luck :D

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

GL && HF!!!

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

Tasks will be sorted by difficulty in increasing order, will they?

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

Как решается DIV-1A ?

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

    Возьмём две точки: i и j (a[i]<a[j]). Понятно, что из всех перестановок после i сразу идёт j только в (n-1)! случаях. То есть разность (a[j]-a[i]) должна войти в ответ с коэффициентом 2/n (когда мы из i идём в j и наоборот). Также для выхода из нуля (a[i]-0) будет взято с коэффициентом 1/n.

    Таким образом мы узнаём, с каким коэффициентом будет входить каждое из a[i]-тых в ответ.

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

    Нужно посчитать такое: (сумма всех путей)/n!. Любое расстояние abs(a[i]-a[j]) будет встречаться в сумме всех путей ровно (n-1)! раз. Еще добавляем сумму всех a[i]*(n-1)! — сколько раз каждая точка будет следующей после нуля в начале пути. Имеем (сумма всех abs(a[i]-a[j])+сума всех a[i])*(n-1)!/n!. Факториалы сокращаются, в знаменателе остается просто n.

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

How to solve B div2?

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

Problems are little bit hard for div2 contesters, but I have to say, very interesting problems.

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

Спасибо авторам за сложный и интересный контест!

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

Couldn't completely write NlogN of LAS for problem-D in time, because realized it in last 5 minutes. So sad =( And fchirica was correct, implementation was easy.

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

    You can use Patience_sorting.
    Here is my code which passed the system test

    set st;
    set::iterator it;
    for(int i=0; i<n; i++) {
    st.insert(a[i]);
    it=st.find(a[i]);
    it++;
    if(it!=st.end()) st.erase(it);
    }
    cout<<st.size()<<endl;

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

div 2 problems difficulty A D D D E !!

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

why doesn't the system testing start ? :-/

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

I hacked more than 10 'A' solutions with this test case:

1 1 1 2000000000

»
11 лет назад, # |
  Проголосовать: нравится -27 Проголосовать: не нравится
Комментарий удален по причине нарушения правил Codeforces
»
11 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Special Thanks for your great contest! I'm willing to take all the downvotes only to thank you personally! :)

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

I think there is some problem on div 1 problem D'time limit! 2 dimension segmeng tree and the 2 dimension tree array have a same time complexity O(m*logn*logn),but you make first TLE and last one AC..it is different from usual cf's problem.

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

    i think you probably make some mistake about the time.

    the time complexity of quad tree is O(n) is indeed.

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

      !!!what?...i treat it as O(logn*logn) until now.=.=~..thank you~

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

        Can "xianduanshu tao pinghengshu" get accepted?I do want to do so,but when I see the time limit I changed my mind.(sorry I don't know how to translate it into english)

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

          I don't see the time limit at first....555...and after TLE by segment tree, i'm too native to believe that cf would not "卡常数"..so i didn't to write tree array at once.

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

      Are you sure about it? every step at updata or query on my quad tree(just like kd tree) , the area became area / 2. So i think the number of total steps is log(n^2), time complexity is O(logn*logn). Why you say it's O(n).

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

        I think it's O(N) for query(1,1,1,n)

      • »
        »
        »
        »
        11 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
        • O(log(n2)) = O(2log(n)) = O(log(n)), so there must be something wrong.

        • btw. binary indexed tree or fenwich tree instead of tree array :)

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

Похоже, что lhyzjz поставил АНТИрекорд набрав -600 http://codeforces.com/contest/340/standings/page/102

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

Классные задачи...!!! Спасибо авторам за контест.

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

Nice problems, really liked them. Damn E, declared the array of 1000 instead of 2000, else I would've gotten AC.

Very nice contest. Congratz to the organizers!

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

Problem B in Div2 was awesome.

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

Very nice problem set,and a very enjoyable contest overall.

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

great contest! great problem! thank you all!

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

Very cool problemset. I really liked D: At first glance I thought it was another Range tree problem. I almost implemented that, but luckily I remembered the author's comment that "all tasks don't require too complicated algorithms" :D

Edit: First time in congratulation list, yay ^_^

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

Помогите кто-нибудь, я в замешательстве.

Отправил решение 4377911. Вердикт: WA 1. Проверил через запуск и выяснилось, что мой код выводит 10 3 вместо правильного 22 3. В какой-то момент добавил строку cout << ans << "\n"; после строки sum += a[i];. Тогда ответ выводился верно. При удалении той строки опять получалась лажа. В чем проблема? Заранее спасибо.

UPD: Вспомнил прикольную штуку, у меня все заработало, когда я объявил переменные n и i в глобальной.

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

    Я тоже не могу понять, сдал во время контеста решение 4374933. Получил WA 1. Сейчас вижу, что тоже на тесте из условия выдает 10 3 вместо 22 3.

    Я пересдал это же решение на Visual C++, получил OK (4375227).

    Только что выяснил, что все зависит от ключей компиляции. Если компилировать под g++ с ключами -O0, то выдает на претесте правильный ответ, если с ключом -O1 — неправильный.

    Посмотри, у тебя не такая же ошибка? В своем коде я ошибку найти не могу.

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

      Я не знаю ответа на вышепоставленные вопросы, я просто вставлю свои 50 копеек:

      1) Кроме смены языка во втором решении (4375227) появился вектор. Может он как-то влияет на процесс оптимизации?
      2) Первый код (4374933) просто не компилируется на сервере под Visual Studio 2010. Да что тут вообще происходит?

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

        Вектор появился от того, что я просто уж не знал, что сделать.

        Второе решение с вектором обладает всеми описанными свойствами — поведение программы меняется при изменении ключа оптимизатора. То есть вектор не при чем.

        Более того, выяснилось, что если заменить строчку

        sumpairs += A[i] * i - sum;
        

        на

        sumpairs = sumpairs +  A[i] * i - sum;
        

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

        Похоже, это баг в gcc. Говорят, что в gcc версии 4.8 это уже не воспроизводится.

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

      Ну в этом решении написано "long long A[n];", что противоречит стандарту C++; так что это вообще должно быть compilation error, но оно его скомпилировало и видимо как-то весело соптимизировало.

      Про решение [JustCrazy] пока непонятно; надо бы посмотреть, что генерит компилятор, но у меня (на GCC 4.8.1) это не воспроизводится.

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

        У меня есть решение без long long A[n] (то, которое на Visual C++ сдано), где используются вектора. Проблема там такая же.

        Проблема не воспроизводится на компиляторе 4.8.1, этому есть уже минимум три подтверждения.

        Похоже, мы оба натолкнулись на один и тот же баг в оптимизаторе gcc, который уже исправлен в версии 4.8.

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

          А у кого-нибудь есть gcc 4.7 и 64-битная машина? Этот баг проявляется только для int64, так что битность процессора тоже может быть актуальна.

          В первый раз вижу баг, воспроизводящийся простым циклом for, без рекурсии и всяких ужасов. Интересно было бы его исследовать...

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

            Женя Курпилянский говорит, что компилятор при ключе -O1 вообще пропускает строчку sumpairs += A[i] * i — sum; То есть sumpairs просто не считается правильно.

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

            У меня 4.6.2 и 64-битная машина.

            Упростил код (выкинул все лишнее — gcd, сортировку и объявление массива длины n).

            После рассмотрения генерируемого ассемблера выяснил, что оптимизатор почему-то удалил строчку "sumpairs += A[i] * i — sum" и посчитал только сумму.

            P.S. Кто не знает если использовать g++ с ключом -S, то на выходе будем ассемлер-код.

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

              Вот это получается, если заменить "+=" на "= sumpairs +".

              Код цикла находится в метке L5 (в обоих версиях кода). Видно что во втором случае он гораздо сложнее :)

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

    Да, правильность твоего решения в g++ также зависит от оптимизатора.

    При компиляции с -O0 выдает ответ 22 3, при компиляции с -O1 — неправильный ответ 10 3.

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

      То, что добавление cout'а влияет на ответ, однозначно говорит, что это оптимизатор шалит.

      Посмотрите в дизассемблере, что там с циклом происходит.

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

        Я, к сожалению, не знаком с ассемблером и не смогу это сам сделать.

        Но похоже, что минимум 4 человека в контесте столкнулись с аналогичными проблемами.

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

I will always add X while subtracting two integers modulo X!!!
I will always add X while subtracting two integers modulo X!!!
I will always add X while subtracting two integers modulo X!!!

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

DIV1-C can be solved in O(N), why constraints are so weak?

solution

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

    So that O(N*N) solutions can pass too.

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

      I suppose problem would be more interesting with larger constraints, so well-known derangement problem with n^2 solution shouldn't pass:-)

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

        The O(n) solution is well-known, so smaller constraints wouldn't make it more interesting. Just make the imbalance between people who've seen it and those who didn't worse.

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

Интересно, с каких соображений автор поставил задачу В (div 2) на такое место, что ее стоимость осталась на 3000?

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

Awesome contest ! I loved the problems , they were GREAT . Thank you for this very well made contest :) !!!

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

Thank you authors for the contest!

I'm wondering what was the intended solution in Div 1 C, because one can use inclusion-exclusion principle to get to the answer, which is: ,where K is the number of places i where a[i] = i still can happen and F is the number of free places. Judging from post-contest reaction, most people used DP approach. Thanks to gen for knowing Latex.

Also, does anyone has any tips on Div 1 D without using any king of 2D structures? I believe one could somehow split it in 2 independent parts: rows and columns, but couldn't think of how.

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

    For D div 1:

    First you need to observe that the problem can be solved by using only operations of 2 types: Query(1,1,x,y) and Update(1,1,x,y)

    By observing 4 relative positions of (u,v) to (x,y), you can solve it by using 2D Fenwick tree (which I hope is simple enough) :)

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

      Yeah, maybe it was intended. But I just got a feeling from the pre-round author comments that there is some cool solution with no 2D structures at all. And that the long long as the values was designed to stop the majority of 2D structures from passing.

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

    There is another simple solution. Let n be the number of free cells and k the number of those free cells in which we cannot put values equal to their position, but it can still happen. Let calculate such DP[n][k] = (n — 1) * DP[n — 1][k — 1] + (k — 1) * DP[n — 2][k — 2], if k > 1. DP[n][1] = (n — 1) * (n — 1)!, DP[n][0] = n!. One can see that we should calculate only values with constant difference between n and k, so there are only O(n) states.

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

How it was necessary to solve the problem of B div 2?

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

    You have to fix one diagonal with O(N^2) and then with O(N) find the best points ( the ones that make the biggest area ) to the left and right of the diagonal . Overall complexity is O(N^3).

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

Is there no time limit scaling for slow languages (e.g Python)? Was something like that maybe discussed before on Codeforces? I just timed-out on div1-B using python (finding LIS in nlog(n)), but passed in 0.124 after retyping the code in C++ :(

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

Спасибо авторам! Наконец-то я фиолетовый!

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

http://codeforces.com/contest/341/submission/4375062

No reversely sorted test case!

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

Some whining about the problems follows.

Problem B: it was 100500 times already, it's a shame to reuse this problem again.

Problem C: it is obvious for the ones who remember how to calculate the number of permutations without fixed points (or for the ones who do not hesitate to use Google/Wikipedia during the contest). Again, this problem appeared on a different contests 1050 times. And for the ones who do not remember the solution it is way harder, since they have to reinvent this dynamic programming.

Problem D: it is super-evil, since 2-d segment tree (with time complexity is terribly slow (especially in Java), and 2-d Fenwick tree (with the same time complexity) seems to be the intended solution (at least, everyone got AC with it). Did the authors intend to make a problem with key idea in non-asymptotic optimizations?

Update: another complaint: seems that most of the Java solutions for problem A are easily hackable (with anti-java-sort test). Did not you bother to add such a test? It is very unfair, since one can be hacked with this test, and in the other room the same solution may pass. Anyway, as I understand, general guideline for tests is to kill as much killable solutions as possible, and it seems to be violated.

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

    If somebody had been successfully hacked by such a test then it would have been added to final system tests.

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

      As I know, there is no automatic adding of successful hacks to system tests on codeforces (unlike topcoder). And adding the tests selectively is even worse (e.g. see this).

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

        Exactly in that contest I was the victim of a successful hack added to the system tests. The successful hack made by Arti1990 was added as a test 52 to the final tests of problem C.

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

          Ouch, this probably means that tests are still manually added during contest despite the discussion initiated by Petr. Too bad :(

          Anyway, IMO problem authors should not depend on this and at least try to prepair strong tests before the contest.

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

            Sorry, maybe my previous post wasn't clear enough. Exactly in that contest which you pointed in your previous post (Round 172) the successful hack was added to the system tests.

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

              Ah, I see, thanks for the clarification. IMO is would be better just to automatically add all successful hacks to systest, but it can explode testing time as a drawback.

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

It is strange that there is no warning like this in task D:

"Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier."

And I forget to use long long but passed pretest. :(

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

    %lld works now in all C++ compilers used on CF

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

      Hmm..then why not to remove this annoying time-consuming message that appears after submitting llds? Time, especially at the beginning of contest, is really significant for wasting it on reading unnecessary warnings.

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

I submitted the following code for A: http://codeforces.com/contest/341/submission/4374002 and got WA on pretest 1, with checker saying it received 0 instead of 22. Could anyone explain me why did my code print 0? On my laptop it prints 22, both with "%lld" and "%I64d". The logical part of the code is OK, as I got AC after simply deleting some macros and unnecessary #include's (code http://codeforces.com/contest/341/submission/4376745).

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

Can somebody tell me why this code ( http://codeforces.com/contest/340/submission/4383684) is outputting 10 3 ,it is giving 22 3 on my laptop.

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

    Try to compile your solution with -O3 option

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

    I've replaced #define LL long long with this:

    typedef long long X;
    #define LL X
    

    And now it gives 22 3

    http://codeforces.com/contest/340/submission/4383966

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

      yeah that worked! How can this create any difference :-o ?

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

        I used g++ -O2 main.cpp -S -fverbose-asm to get the assembly codes and it turns out that the var ans is not in it while it is in if using g++ main.cpp -S -fverbose-asm.

        I found that this code when compiled with -O3 will output 10 (g++4.6.2). So it must be a bug in the compiler.

        #include<stdio.h>
        
        long long ar[3]={2,3,5};
        long long ss,ans,num;
        int i;
        
        int main(){
            for(i=0;i<3;i++){
                ans += ((ar[i]*i) - ss);
                ss += ar[i];
            }
            num = ss + 2*ans;
            printf("%I64d\n",num);
            return 0;
        }
        

        After reading the assembly codes, I found it ran like this:

        ar={2,3,5}
        ss=ans=num=i=0
        ss'=ss
        ss+=ar[0]
        ss+=ar[1]
        ss+=ar[2]
        ans-=ss'
        ss'*=2
        ans-=ss'
        i=3
        tmp=ans*2
        tmp+=ss
        num=tmp
        print num
        
»
11 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Looks that was a great contest!! unfortunately I missed it...

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

I find that i cannot view any problem. when i click the problem title, the web give the alert telling me "can't find or parse problem descriptor". I know nothing about the exception, and anyone can give me the answer or one solution?? Thanks!!

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

What's the meaning when I got a "Hacked"? Ps:I am a beginner!!

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

Very interesting round and thanks for challenging problems !