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

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

Всем доброго времени суток!

Сегодня в 12:00 по Москве состоится Codeforces Round #279, предназначенный для участников второго дивизиона. Раунд проходит на задачах муниципиального (II) этапа всероссийской олимпиады школьников по информатике 2014-2015 учебного года, который проходит в это же время в Саратове.

Раунд подготовила для вас дружная команда Saratov SU 2, членами которой в разное время являлись и являются ikar, HolkinPV, IlyaLos, fcspartakm.

Вам будет предложено 6 задач на 2 часа 30 минут. Разбаловка будет оглашена непосредственно перед раундом.

Раунд является рейтинговым для участников из второго дивизиона. Участники из первого дивизиона, как и всегда, могут участвовать вне конкурса.

UPD: Разбалловка — 500-1000-1500-2000-2000-2500.

Удачи!

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

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

ranked!?

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

waiting! waiting!!! good luck to all participants!

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

wish high rating

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

I think it will be a good contest

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

Везет же некоторым с областью) У нас в городе позавчера давали три задачи, уровня div2-a,c,d; без возможности проверить решения. Да что там, в феврале на областной олимпиаде тоже не было никакого тестирования во время контеста, полдесятка участников не смогли из-за этого гарантированно попасть на финал...

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

    Так вся Россия оффлайн писала региональный этап в том году. В этом году есть шанс, что будет онлайновая регионалка.

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

      Шо, правда? У меня просто в голове не укладывается, как можно писать алгоритмы на регионалку без проверки. У нас так несколько не попали на финал из-за глупых ошибок, потом решают финал — 230 баллов в первом туре, а поезд-то уехал)

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

        Тестировать нужно хорошо. И нужно пробовать генерировать большие тесты. Я сам в том году не поехал на всеросс из-за того, что в 5-ой задаче забыл 8 знаков после запятой выводить на регионалке. Потерял 50 баллов на этом.

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

When you visit codeforces.com

Can you look the message "connecting to fonts.googleapis.com ..." with 10 sec?

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

6 problems. Wow!!!!!!!!

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

10 minuets to start. Why yet not scoring have been published? Waiting for it.

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

Delay? Again

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

    When it was moved last time, servers were showing they are busy almost all the time, hopefully today it will be better...

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

      hope that also last time I asked to be unrated because of the same reason but they told me they didn't face any problem during contest :D now it seems that it's not mine only :D

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

        There was a lot of contestants complaining, I didn't understand why it was rated, I left the contest earlier also...

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

Scoring have been published. Best luck to all participants.

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

Начинать раунды вовремя? Нет, не слышал..

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

Contest not start

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

delayed :|

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

Not again! It's becoming a tradition to delay the contest right before it starts!

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

again more 10 minutes waiting :D nice. P.S. good luck everybody

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

when will i be candidate master???

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

Almost every contest gets delayed these days! Anyone knows what the problem is?

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

I wish will be candidate master today)

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

I arrived at home just now from school (it's 12:30 here)

I'm so stressful now... :(

Please pray a good contest for me... :(

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

It delays for 10 minutes! Am I right?

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

Good luck to all!

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

Its good that this contest has 6 problems. Better chance to improve ratings. Wishing high ratings to everyone :)

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

    Really? It depends on number of problems? I don't think so...

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

      Its not always correct, but most of the times it is easier to solve 3 problems out of 6 than solving 3 out of 5. Of course, it includes the fact that you should solve the 3 problems fast.

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

Is there any way to help Codeforces to strengthen its servers ? I think it worth to pay for having a faster and stronger programming contest platform.

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

Can you unblock gym?

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

Hello, why all problem pages are blocked? is this because contest is running?

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

Does the interface always inform about hacks with delay?

I got a message about my stupid C solution being hacked only after about 20 minutes and hadn't enough time to correct it =(

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

Why all wrote n^2 to C. I earned 5 hacks because of that. (actually n is the length of string)

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

    All my hacked solutions were exactly the same. My test was s = '9' 10^6 times, a = 9, b = 2

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

Как решать F? Очень интересная задача. Но я пока придумал решение только за O(N^3). N раз запускаю bfs от каждой вершины, а внутри bfs считаю динамику d[i], где d[i] — длина НВП(наибольшая возрастающая подпоследовательность), оканчивающаяся в i-ой вершине. Каждый переход динамики за O(N), потому что каждый раз бегу по пути от i-ой вершины до стартовой.

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

    Если искать НВП за O(log(n)) и делать "откаты" когда уже поднимаемся с вершины, то сложность будет O(n2 * log(n)). И да, это проще делать при обходе в глубину.

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

    Сначала закореним дерево где угодно.

    Динамика за O(N^2).

    Параметры: текущая вершина(v), в какой последней вершине был концерт(last).

    Переходы: Переберем все ребра из текущей вершины, узнаем, можем ли мы сделать переход в вершину на другом конце ребра. Как это узнать? Допустим, v — предок last. Тогда нам можно идти по всем ребрам, кроме того, которое ведет в поддерево с last. Допустим v — не предок last. Тогда нам можно идти по всем ребрам, кроме того, которое ведет вершину v к ее родителю. Еще всегда нужно учесть два случая — проводим концерт в вершине v или нет.

    Почем это работает быстро? При фиксированном last каждое ребро переберется не более двух раз. Ребер O(N). Следовательно, всего переходов по всем состояниям O(N^2).

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

В задаче Е должно же ведь заходить жадное решение? Очевидно, что неинтересны случаи, когда у нас у предыдущего числа меньше или больше разрядов. Пусть у текущего и предыдущего числа одинаковое количество разрядов. Тогда попробуем текущее число сделать больше предыдущего, минимизируя текущее число. Почему это неверно?

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

    ну это заходит, мб с лидирующими нулями накосячил?

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

      ВА5. Ну, тесты откроются, тогда гляну, что не так. Печально, что не сдал.

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

        у меня WA5 было примерно на таком тесте 1100 12??

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

    А если все разряды текущего и предыдущего неизвестны, то что делает твоя программа?

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

    Я так и делал. У меня был WA9, подобрал такой контртест:

    3 1236788 123?58? 1237889

    Смотрел справа-налево и забывал обнулять предыдущие знаки вопросов, если встречаю бОльшую цифру.

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

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

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

Omg, after I locked my C I found it will fail with

1230
123 10

...I'm so unhappy :-(

BTW: where I can test hacking using generator? Because I wanted to try huge input for heu2013201410's solution in my room — 27...

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

    The answer should be "No"? As your test doesn't differ from

    120 12 1

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

    Wanted to hack solution C by TL with test.

    1...1 (1 repeats 1e6 times)
    5 1
    

    But this test file has size (1e6 + 5) Bytes! And this is more then 256KB. Why does system not allow to upload big tests???

    Lost my hack because of this.

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

      How about generator?

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

      You can create generator — program, that generates the input. I wanted to try it first time today also. Motivation is clear, if everyone uploads 1MB big file it is a lot of network traffic...

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

    A generator is a program which outputs the hack input in the correct format. I don't think that you can test it without a contest. Just write one and check if the generated input is ok.

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

    The two parts must be positive integers
    is zero considered to be a positive integer ?

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

Чувствую у многих C-шка не проидет

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

    По мне в D-шке слишком простые тесты

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

    Решение проходило претесты, если оно для всех суффиксов за линию проверяло делимость на число b?

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

Div.2 C. Couldn't understand why hack attempts were unsuccessful until realized that me forgot expand generated test changing magnitude(10^) from 1 to 6 :( .

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

The problem statement of F today was so bad and unclear that I had to read the statement over and over again and rewrite my code about 4 times from scratch because of not understanding what was actually I needed to do. I had to code this problem mostly on assumption. Glad it was only a div-2 contest. I hope the authors will provide easily understandable statements from next time.

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

why b=1000000007 for hacking of C is invalid?

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

why b=1000000007 is invalid test for hacking of C?

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

this code is still wrong, but for this tc, it gives right answer and yet it got WA http://mirror.codeforces.com/contest/490/submission/8820977

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

New contest new color...

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

Can anyone tell me why am I getting a wrong answer on pretest 4 ? I'm new here! http://mirror.codeforces.com/contest/490/submission/8821196 (Ignore the biginteger part,coding begins at the function compute() ) thanks!

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

    Because there is the answer for string "604": "60 4" where both of numbers are divisible by 6 and 4 respectively

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

Why can't I see the wrong test case when submitting problem E in practice?

Edit: It's fixed now

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

вот бы и рейтинговые раунды писать так же хорошо, как нерейтинговые :( Отличный контест.

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

Surprisingly fast system test. I thought problem C can be solved using O(n2) algorithm. Too bad I didn't check the constraint for n. Anyway, thanks for the contest!

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

I think that codeforces should check the IP when a new user registers because i can bet that there are lots of div1 members who make clone accounts in order to participate in div2 rounds with rating and because of that our chances for a lower rating grow. Or we get a lower improvement than we should. Just my opinion.

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

    Some nations do not have static IP.

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

      I know that it cant be that accurate, but at least.. you block few users. With a bit luck, more users :D

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

    IP based check is bad idea. But I have same feelings... Mbaybe solution could be that when there is no Div 1 competition, they will have same problems in and they can compete in speed typing... Or separate ranking can be created for such contests...

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

When will ratings be updated ???

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

Anyone on how to approach Problem C. I thought about writing own function to check if the two numbers formed are divisible by the given number : eg. 64010 64 10 check for each value of i 6|4010, 64|010, 640|10 ... for divisibility Will this approach run in time?

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

    try to check forward and backward (will be almost the same like forward )

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

    the idea starts from the observation:

    lets say you have the number 78541

    78541%x = ( (7*10^4)%x + (8*10^3)%x + (5*10^2)%x + (4*10^1)%x + (1*10^0)%x )%x

    if you dont get the further idea for the solution i will add the next part :D

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

For B I allocated int[] map = new int[1000000] instead of int[] map = new int[1000001] and I got a WA on Test 55 because of that. Cruel!

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

    Do people like downvoting stuff just for fun? This community should be a little more mature.

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

I got TLE in 'C' with O(n) solution. :/

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

OK

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

How I can solve problem C?

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

    Traverse a string in both directions and keep two arrays ad, bd.

    For ad[i] we traverse the string from the left to the right and find the reminder s[1: i]%a. There is a formula for this: ad[i] = (ad[i - 1] * 10 + s[i] - '0')%a.

    For the bd[i] we traverse string from the right to the left and find the reminder s[i + 1: n]%b. Also we keep the variable bteni which is equal to 10i %b. So there is a formula for bd: bd[i] = (bd[i + 1] + (s[i] - '0') * bteni)%b.

    Finally we traverse the arrays ad, bd and search for such index i, that ad[i] = bd[i + 1] = 0.

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

Rating....so late.

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

Can someone Please explain the idea behind problem C ? in detail preferably. Thank You. :)

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

    If we divide the sequnence into two parts: 1, 2, ..., i and i + 1, ..., n, then we need to check s(1, i) % a and s(i + 1, n) % b. Since s(1, i) % a = (s(1, i — 1) * 10 + s[i]) % a, s(i, n) % b = (s(i + 1, n) + 10^(n — i) * s[i]) % b, we can compute every s(1, i) and s(i, n) within O(n) time firstly. Now, we can check s(1, i) % a and s(i + 1, n) % b within O(1) time.

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

    I Will explain it using an example:

    consider the number 116401024(call it N)

    we can split it as

    (1*10^8)+(1*10^7)+(6*10^6)+(4*10^5)+(0*10^4)+(1*10^3)+(0*10^2)+(2*10^1)+(4*10^0)
    
       a8       a7       a6       a5       a4       a3       a2       a1       a0 
    

    If this number is divisible by a number M then the modulus must be 0(i.e. N%M==0), to check this we can do:

    rem = 0;
    rep i from 0 to 8:
        rem = ( rem%M + ai%M )%M;
    if(rem == 0)
        the number is divisible by M
    

    Coming to the actual problem

    The possible ways we can split the number into two parts are :

    1 16401024
    11 6401024
    116 401024
    1164 01024
    11640 1024
    116401 024
    1164010 24
    11640102 4
    

    now for each of this splits we want to check if the first part is divisible by "a" and second part is divisible by "b".

    Now we can modify the above for loop by storing for each index i, whether the part of the number from 0 to i is divisible by a, like this:

    n = Number of digits in N;
    rem = N[0]%a;
    rep i from 1 to n-1:   --------------------------------> O(N)
        rem = ((rem*10)%a + (N[i]%a))%a
        if(rem == 0)
            divisible_by_a[i] = true;
        else
            divisible_by_a[i] = false;
    

    Similarly, we can do for b starting from least significant digit of the number.

    and once we have divisible_by_a and divisible_by_b, we can easily check if we can divide the number into two parts for each index i by the logic:

    (divisible_by_a[i] == true) && (divisible_by_b[i+1] == true)  && (N[i+1] != 0)    -------> O(1)
    
  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Call the large number s and let n be its length.

    For every prefix, compute x[i] = s[0..i] % a. For every suffix, compute y[i] = s[i..n-1] % b. Now scan s from left to right and check if x[i] == 0 and y[i+1] == 0 and s[i + 1] != '0'. If this condition holds, we have an answer.

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

Когда уже рейтинг обновят? Почему так долго?

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

Can anyone please tell me, why my solution of C always takes 0 or 15 ms and suddenly on test 36 i got TIME_LIMIT_EXCEEDED? There are no cycles or anything and I'm getting really clueless... http://mirror.codeforces.com/contest/490/submission/8823963

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

    There's also the weird thing, that it shows my output (which I think isn't supposed to be there, because I shouldn't have time to it), but there is no Answer...

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

    Don't use ansistring. Try to use array of char instead.

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

Can someone explain to me their approach for problem E? I got it accepted in practice but barely under the time limit so I guess there are faster approaches.

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

What's wrong with checker of problem D ?

Test #12

2160 3240
7200 384

Вывод
5
1280 1080
3600 384

Ответ
5
640 2160
3600 384

Протокол тестирования
wrong answer reported answer can be reached in minimum 1000000002 operations, but given result is 5 operations

Seems like my solution gave a valid answer, but checker haven't noticed that!

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

What is the approach for Problem B?

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

    My approach:

    1. If we determine the first two elements, we can determine the rest uniquely. -> Make an array X such that X[A[i]]=B[i] for every i. Then answer[i+2]=X[answer[i]] for any i.

    2. The student ID of the second person is X[0]. The first person in the line has a = 0, b = (second person's ID).

    3. The student ID of the first person is A[i] which does not appear in array B. Let id = the first person's ID. There's no student such that b_i = id, because there's no one in front of him! And conversely, the first person is the only student with such property.

    We can uniquely determine the first two persons, which determine the rest uniquely.

    The total run time is O(n).

    My submission

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

Can someone please explain their approach for problem E? I got it accepted in practice but barely under the time limit so I guess there are faster approaches.

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

    Just find the smallest feasible number every time. I'm not sure what is the best algorithm to find this, but my solution is: First, compare the length of the string with the one of last string, and there are three cases: 1. s[i].size()<s[i-1].size(): impossible, print "NO" 2. s[i].size()>s[i-1].size(): set all '?' to 0 (If it's the first number, set it to '1') 3. s[i].size()==s[i-1].size(): Find the first digit j where s[i] and s[i-1] is different. There are two cases: 1. j==s[i].size(Can't find) or s[i][j]<s[i-1][j]: Find the rightest '?' before digit j whose corresponding digit 'k' in s[i-1] is not '9'(because no digit is larger than 9). If you can't find it, also print "NO". Otherwise, set the '?' to 'k+1'. Then set all '?' before this digit exactly the same as their corresponding digit in s[i-1], and all '?' after this digit to '0'. 2.s[i][j]>s[i-1][j]: Similar to the case 1, but don't need to do the first step because this digit is already larger.

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

      Thank you very much. It's very similar to my solution but I used a recursive approach and I guess that's what's taking my algorithm longer.

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

    I used binary search to solve E.
    Here is my submission.

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

      Could you please explain how you used binary search? I didn't understand very well by reading the code.

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

When I was trying to hack a solution by the output generator, I got a message "FAIL Line [name=public_key] equals to "#include <b...spond to pattern "[1-9][0-9]{0,999999}" (stdin) [validator val.exe returns exit code 3]".

I didn't understand the meaning of it. Please anyone help me how to hack in problem C if anyone use only 10^5 array where I need 10^6.

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

Do you guys know when the editorial will be published? I am really interested what is the idea for D and how one can figure it out.

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

    Every time Polycapus eats the chocolate, he set one of the number to 2/3 or 1/2. So what you should consider is, whether these two products is the same after dividing all 2 and 3. If it is, you can set the power of 3 to the same number by performing several 2/3 cuts to the one which has more 3, and then set the power of 2 to the same number by 1/2 cuts.

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

My C problem reached TL on test 42. How to solve this problem correctly?

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

The contest is useless. I don't gain any thing throng the contest. The problems are so silly!!!

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

How to solve B?

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

Is there any tutorial?

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

The B has a error in your problem description.To give an example, how do you solve in this data? 4 0 2 1 3 3 5 4 0

It's easy to infer that the correct answer is 1 2 3 4 5.. but many programe are not give me this answer but also accept it! please view.

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

    In your example you have n=4, but 5 different ids in the list. Change n to 5 and add a line with "2 4" — then you will get 1 2 3 4 5.

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

    Your test is wrong not enough information while n == 4 if n == 4 you test data be like this 4 0 2 1 3 2 4 3 0 if n == 5 4 0 2 1 3 2 4 3 5 4 0 try again

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

In case anyone is looking for the Editorial as I was, it has been posted here.

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

After reading the tutorial, I realized how unnecessary this solution by me is: http://mirror.codeforces.com/contest/490/submission/8829276