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

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

Всем привет!

Codeforces Round #201 пройдет в пятницу, 20-го сентября в пятницу, 20-го сентября в 19:30 MSK(23:30 CST)

Авторы задач: CMHJT и я.

Тестеры: error202, havaliza и tourist.

Мы хотим сказать спасибо MinakoKojima за обработку условий, Delinur за перевод условий задач на русский язык, и MikeMirzayanov за разработку мощной платформы для подготовки контестов.

Особая благодарность пользователям tourist и Gerald за их советы по задачам, теперь задачи расположены в наиболее правильном порядке.


500 — 1000 — 1500 — 2000 — 2500.

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

Удачи!

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

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

Thanks for the contest!

The problems are not so hard, but you need more thinking rather then coding.

It seems that the problems will be very interesting.

Good luck to all participants!

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

    Ok, sorry if I give bad idea (at first I think it's good idea). Thanks for your vote.

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

      Are you a bot who copy automatically comments with high number of upvotes? That's why you just used tjandra comment witout any reason? Edit: After looking at your previous comments, yes, it's exactly that...

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

Good luck to everyone.Thanks to XHXJ.

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

Compact and interesting statements wanted! Thanks! :)

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

Orz XHXJ ....

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

I will definitely take part in this round because UESTC_Nocturne has given me a lot of suggestions on my computer programming. Special thanks to you and Good luck to everybody. By the way,his nickname in pinyin is "xue jie"~~~~

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

ORZ...Good luck! God bless us!

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

oh ! 26 hours remaining ! I can't wait ! :-<

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

Thanks to the setter for preparing this contest :-)

If there're some tricky case, I hope all tricky case is put on the pretest, so if my code got accepted (pretest passed) it'll accepted too after system test.

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

    Ok, sorry if I give bad idea (at first I think it's good idea). Thanks for your vote.

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

    So, What does hacking mean then?? All of solutions will be right and no one could hack another...

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

A small question, xiaodao...her help? ^_^

tourist!!!! Always be my super idol!!!!

Hope it to be an awesome round and Everyone enjoys it!

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

Sooo you say it is going to be the best tested round?:D:D

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

I apologize for my ignorance, but I always wondered what does UESTC stand for ?

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

UESTC_Nocturne CMHJT It's first time for you in prepare a Round ?

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

Good luck to everyone!Long time no coding in codeforces.

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

Best of luck to everyone , problems set by some of the best people in the arena , looking forward to it :)

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

first time to attend div1 I know it is so hard for me but good luck

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

minus

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

today and he will codeforces 201, and involves more than 3,000 people

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

Why I always got WA on #4 on D Div2?

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

someone push Start System Testing button please

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

Great round, thanks! Problems are interesting, indeed there was no need to write big solutions, except, maybe, problem B. Seems like it should cost 1500 instead of 1000 — it's the most hardcoding problem today =)

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

Why solutions are not visible even after the contest??

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

Very great contest, problems were very intresting but not much hard. Could someone explain the solution of Div2.C / Div1.A? By induction I proved that if we have k numbers and there is no valid move, those numbers should be a, 2a, ... , ka, but couldn't find the complete solution.

Thanks in advance.

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

    Try GCD to solve this kind of tests.

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

    Let's denote g = gcd(a1, a2, ...an). It's obvious that every number in the end will be divisible by g. From other side, we can obtain g with Euclid Algorithm. Thus we can prove that resulting set is . So the answer is , where amax is the greatest ai.

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

I think the worst thing and the best thing in the world may be you HAVE to skip a high scoring solution because you find a bug in it. :D

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

Спасибо за классный раунд! В дальнейшем буду ждать от вас еще контесты:)

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

had i seen the gcd part in C, it could have easily been my best! Hacked two solutions which made the same error as me. Good and false-motivating pretests!

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

After seeing the number accepted solution from the dashboard,it seems, in div-2 problem A is harder than problem B ... :(

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

Почему этот генератор теста в С неправильный ? Система отвечает что 2 пробела подряд в 12 строке.

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

    А можно точное сообщение валидатора?

    UPD Я кажется докадался. Вы посылали его как тест, а не как генератор. И в нем действительно два пробела в 12-ой строке.

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

    Да, в самом деле этот тест содержит два пробела подряд в строке 12. Вы отослали исходник как тест, а не как генератор.

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

      То есть, все остальное в этом тесте системе нравится? =)

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

        Запускается два валидатора. Собственно валидатор, и проверка на well-formed. Там такая галочка в полигоне есть. Почему-то well-formed запускается первым, и это первое не well-formed место. Видимо порядок стоит поменять.

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

          Видимо, стоит, потому что такие сообщения об ошибках несколько сбивают с толку.

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

            Мне казалось, что если нажать на взлом, то видно какой тест сгенерировался. Из этого делается однозначный вывод мне кажется.

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

In problem D, the following phrase confused me:

Please note that mzry1992 can give orders to the robot while it is walking on the graph. Look at the first sample to clarify that part of the problem.

Does it mean that our orders can depend on where the robot goes, as opposed to some set of orders fixed before the movement?

In the contest, I misinterpreted it as "the robot can receive orders only when it moves from the starting vertex", and that makes the statement controversial.

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

How did you solved A ? Thanks.

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

it seems lots of people FST in problem C. :)

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

I did not participate in this round,but i am glad to see so balanced and amazing problems thanks to UESTC_Nocturne.

I want to solve problemc C(div 1),I know only DP solution in O(n*(a-b)).what is correct solution?

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

    each time choose such x_i that makes a-a%x_i minimal and a-a%x_i>=b. the correctness can be proved by the monotonicity of your dp function.

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

Tasks are very nice, especially A, C and D. (B is a coding task and it's fine. For E, I don't know the solution yet.)

I'm very luck to win this round by finding this trick in task C: x[] can have repeat numbers.

Thanks for the writers/testers!

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

When will ratings be updated???

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

Why is TL for problem C is only 1 second?

I wrote a solution in java during the contest and got TL (4522683). But when I wrote the same in c++ after the contest I got AC (4522630). This makes me sad.

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

    There exists a subtle O(a-b+n) solution.Even written in java would get accepted.

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

      Well, yes. The solution is very nice indeed. However I found an (a-b) log n solution and I settled for it, because I figured it's common sense it should pass and it didn't. There are other (a-b) log n solutions that do pass however, but have smaller constant or use less memory.

      Did you intend to only accept the linear solution? If that's the case, why not give a-b <= 1e7 so people know the log n factor is too much?

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

      I guess you might forget that you need to sort xi or you use radix sort instead of quick sort.

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

Great contest!! Thanks to the problem setters and testers!!

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

Cool problems. Never had so many dumb bugs in a contest in my life :S

For example, in A, I computed the gcd, but forgot to divide by it, i.e. didn't do anything with it :D

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

How to solve C (div1)?

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

    There's a apparently a linear solution, but an nlogn solution that passes in time (for example, my solution in the practice room) is this.

    First, it's very important to make the given numbers unique, i.e. eliminate duplicates. Then you take each x_i and for every multiple of x_i between a and b (call it y) update best[a-y] = max(best[a-y], x_i) (I'll explain what best[i] is in a second). This whole thing is O(nlogn) (the worst case is when X = [2, 3, 4, ... n+1], because then you have the most multiples).

    When you have that, then you process numbers from a down to b. For every such number (let's call it c), you want to compute the minimum number of moves you need to do to get to it from a (that's the 'minlen' variable in my code).

    There are two options basically for each c. You either use the solution for c+1 and reduce a by 1, or you make a "jump". You store all the minlen values for larger c values in a Fenwick tree (or some such structure that allows you to do range minimum queries). Then you use best[c-a] to know what is the largest x_i that is a divisor of c. Using that x_i, you can get to c from any number in the set {c+1, c+2, ..., c+x_i-1} in one step. So you query the Fenwick tree for the minimum in that set, and increase that by 1.

    HTH

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

My code prints output in pretest-1 in my PC BUT it prints no output in codeforces. Can anybody explain?

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

Nightmare。

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

can anyone explain me logic behind the solution of problem C of DIV 2 ? I have seen 1-2 codes , that is something i was thinking while contest, but still i am not able to get that solution. Can anyone please explain little bit ? thanks in advance.

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

    Idea: In the end of the game all numbers printed will be g 2*g 3*g ... MAX_NUMBER where g = gcd(a[1], a[2], ... a[n])

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

      This is actually not correct, though the answer with that assumption stays the same. Consider the case 2, 3, 5. Here g=1, but you can't make any moves, i.e. can't add 1 or 4.

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

        I can add 1 = 3 — 2 and then 4 = 5 — 1.

        Also, obviously we may get g because of Euclid algorithm. After that we may get all the numbers up to MAX_NUMBER using - g

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

    I guess this is problem A from div1 (the Alice and Bob one)?

    First, notice that it is never possible to get a number that is not a multiple of the gcd of all the numbers (let's call the gcd d). That's because if d divides both a and b, it will divide |a-b| as well. Therefore, you can divide all the numbers by d.

    Also, you will never be able to get numbers larger than the max number (obviously), or lower than 1. Now, the key thing to notice that out of the remaining numbers from 1 to MAX, the numbers you can't get always come in pairs. That is because if you have three numbers a<b<c and a+b=c, you can't get either c-a or c-b. Therefore, the solution depends only on the parity of the number of missing numbers.

    Edit: actually, you can get all the numbers from 1 to MAX (after dividing by d) -- see the answers above.

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

А я правильно понимаю, что при TL'е генератора тест просто недописывается? Просто у меня одинаковый генератор по задаче C на Джаве получал какой-то вердикт, что тест некорректный, а тоже самое на Плюсах проходило.

Генератор на джаве (взлом 79947): http://pastie.org/private/w4abbyu8u97kxpokaoptgg

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

    Нет. Джава генерирует некорректный тест. В конце второй строки стоит \n, а не \r\n.

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

Было бы неплохо запоминать язык генератора(хотя бы совместно с языком сдачи, лучше отдельно). У меня сбрасывался на первый пункт.

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

Problem 346C - Number Transformation II has already been used on Baltic Olympiad last year link.

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

    Sorry but .. what is the connection between this two problems? ..

    And ... is there any website I can submit these problems?

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

      The differences are that in BOI task you have to transform n into 0 (also there is many n's), you can use only second type operations and all x[] values are prime (but it doesn't really matter). When I saw problem C, I wondered that I just know the solution, which should also get AC.

      I don't know if it is possible to submit BOI problems somewhere, but here are statement + test data + solution. So, it was possible to find the solution during contest, which is not so good, I think.

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

        There are literally thousands or even tens of thousands of problems with solutions on the web. Sometimes duplicates will occur, there's nothing really wrong with that. Probably 99% of the competitors in this round never saw this particular BOI problem.

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

        Since b is no longer always zero, there are more necessary tricks to avoid getting TLE.

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

Div2 D, had around 140 submissions , but only 10 got AC. Mine failed on #30 test case and cant seem to figure out a way around it. Any hints on how to solve it ?

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

    You can do dynamic programming where the state (a, b, v) solves the subproblem where you're at index a in s1, at index b in s2 and the first v characters of virus are the suffix of the subsequence you've found in the prefixes of s1 and s2.

    I assume many solutions failed on updating v. When you take a character (s1[a]==s2[b]), it is not enough to check if (virus[v]==s1[a]) and then either increase v or set it to 0. Instead, you must do something very similar to Knuth Morris Prat, i.e. there might be a smaller prefix of virus present in the new subsequence (i.e. the new v value may be smaller than the old one, but not 0). See my code in the practice room for details if you like.

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

4519236

Hacked by this test:

ZZZZZRR
ZZZZZRR
ZR

4520203

Accepted but wrong output for same test. I think CF should add hack tests to final tests like TC.

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

Problem A (Div 2): why "lexicographically smaller"? Simply "smaller".

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

When will we get Editorials for this Round? Nice Problem Set :)

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

Как решать задачу B(Div1), D(Div2)?

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

What deceptive pretests... originally accepting my brute force on E xD

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

This round was so good. "The problems are not so hard, but you need more thinking rather than coding" was true. Thanks for the setters :D

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

can somebody expain how to use KMP for tracing virus growth in DIV2 Problem-D

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

It was very intersting! Thanks!

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

The robot is so cute, isn't it?

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

I love this competition。