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

Автор Nerevar, 14 лет назад, По-русски
В четверг, 15 апреля, в 19:45 по московскому времени состоялся Codeforces Beta Round #10. В этот раз автором задач для контеста выступаю я. Хочется поблагодарить создателя Codeforces Михаила Мирзаянова за корректировку условий и Юлию Сатушину за отличный перевод задач на английский.

Сразу хочется извиниться за задачу D, потому как уж точно в моем авторском решении был баг. Более того, возможно, что эта задача вообще неразрешима за полиномиальное время даже при небольшом диапазоне чисел [0.255]. Хотя мне так не казалось:))) Надеюсь, что при любом итоге исследования этой задачи никто сильно не обидится.

UPD: Я уверился в палености своего рещения по D. Еще раз приношу свои извинения. Как сказал бы председатель жюри KPI-Open, задача получилось "с хитринкой", то бишь кривая. Никакого перетестирования решений, сданных на контесте, не будет. Задача будет изменена таким образом, чтобы в ней требовалось найти НОВП для двух последовательностей. Для такой задачи уж точно решение существует.

UPD: Задача D изменена так, как я до этого обещал.
  • Проголосовать: нравится
  • +21
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Сорри, что не в эту тему, но не знаю куда писать:
А возможно ли сделать чтение или с stdin или c input.txt и писать в stdout или в stdout?
Просто при тестировании, каждый раз вбивать тесты неудобно в консоль, а если забудешь убрать чтение с файла, то выдает РЕ.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    *А возможно ли сделать чтение или с stdin или c input.txt и писать в stdout или в output.txt?
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      #ifndef _DEBUG

      freopen("input.txt", "r", stdin);

      #endif

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

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    По этому поводу недавно спрашивал я.

    На сервере определена константа ONLINE_JUDJE ЧТО можно испольховать для не открывания файлов в на сервере и открывания на локальном компе. Кроме того в той теме люди предложли еще несколько вариантов.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    a.exe <in.txt >out.txt
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    В студии пишешь?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
>>Кроме того в той теме люди предложли еще несколько вариантов.
В какой теме? Не могли бы дать ссылочку, я бы прочитал и не парил мозги людям.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    http://codeforces.com/blog/entry/255

    я решил что ее просто найти через мой блог.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Можно перенести контесты на пятницу, я не могу по четвергам...??
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Вообще меня тоже удивляет, что раунды один за другим проходят в четверг вечером. Думаю, что следующий будет в другое время (я раунды для второго дивизиона не учитываю).
14 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

No need to thank me for each contest. Frankly speaking, I feel embarassed, and... ashamed for the comment I made some days ago (hope, you know what I'm speaking about). Forgot to ask you earlier not to mention me. Moreover, one of the translations is yours))

We'll see how good the translations are during/after the contest ;-)

From the bottom of my heart I wish you all the best! It is such a difficult think to make a contest (now I know this for sure). So, you deserve only the best))

  • 14 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    We will give You a lot of thanks for each contest over and over again. =)
    Thank you! =)
  • 14 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    Forgot to say – it’s a difficult thing to make a contest, but it’s even more difficult to reconcile with the idea that you have to miss the contest and lose rating points… :-( For a programmer like you it’s hard… So, good luck one more time))

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Не успел зарегистрироваться :(
14 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
всем удачи :)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
За сколько минут до начала соревнований заканчивается регистрация?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
а нет ли возможности дорегистрировать меня? совсем забыл, что нужно отдельно на контест регистрироваться...
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    К сожалению нет.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      На всякий случай поинтересуюсь - а зачем вообще введена регистрация на контест? На топкодере она есть, чтобы по комнатам поделить, а тут?
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Здесь вскоре тоже будет разбиение по комнатам. Я полагаю, лучше пусть люди пообламываются на бета-раундах из-за плохой памяти, чем после релиза. Есть еще несколько причин.

        Я не думаю, что трудно зайти разок и зарегаться, тем более что регистрация идет несколько дней, о ней написано в каждом письме, а ее каунт-даун есть на главной.
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Кажись очепятка в задаче A:

"Через T1 минут после того, как Вася с последний"

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
НОПВ - это многомерное ДП какое-то надо делать?
14 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
Anyone wants to share ideas about solving D?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Сегодня первый раз задавал вопрос:)) ступил конечно же, но суть не в этом:) неплохо было бы в списке вопросов по задачам скрывать текст вопроса под кат. то же относится и к ответу. а то как-то некрасиво и неудобно получается:)

ps
Большое спасибо за контест!
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А по-моему, не стоит скрывать. И так страницы не сразу открываются, а тут ещё лишняя вкладка или лишний клик будет, после которого опять придётся подождать.

    Лучше не задавать длинных вопросов ;) .
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
C: they require to count the number of triplet (A,B,C) which d(C)=d(d(A)*d(B)) but C!=A*B?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    ya, I guess that is what we need to find. The translations for all the problems, can be made better. 
    No need to go for complex english wording. Either make the little story in the problem simple and neat or, after the little story is finished in the problem, you can just write precisely, "in other words, you are given --this-- , and you need to find --this-- ". Apart from this, Problems are very nice. Thanks a lot for all this !
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      The translation seems fine to me.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        For what it's worth, I personally couldn't make heads or tails of the problem statement during the contest or after it. I still don't get what it asks. That doesn't necessarily prove anything about the quality of the translation of course (maybe I'm just thick) but it's not a good sign.

        For a slightly more objective assessment, it might be interesting to calculate the percentage of Russians amongst those who solved the problem, and compare that to the percentage of Russians in the competition.
        • 14 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится
          I'm a native English speaker and I understood the problem statement fine.  It is almost all technically correct English but the choice of idiom is often foreign and not what a native speaker would naturally say.  Nevertheless I felt the statement was clear when read with sufficient patience.
    • 14 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Well, the translation is not really good. But I found it's challenged and interesting to understand the problem-statement (it's tricky but still logical). I saw similar writing style in other Russian contests at acm.timus.ru.
      • 14 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        Maybe it's not a problem of translation but simply a style? It is common for the contests we are solving on our trains, that one have to "decode" a statement at first, to get rid of the "story", and only after that - start solving the mathematical problem.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          I don't think so. That's not bad logic or bad style, but bad English. Some guys here had solved thousands of ICPC problems, but couldn't understand the problem-statement of problem C.

          Maybe the version you read was the Russian one?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Люди хочу тренера по программированию(решению олимпиадных задач)
если кто хочет помочь пишите в личку или на номер icq:487363834 
  • 14 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    Надо перенести в раздел "Смешное на контестах".

    И что ты хочешь сделать с тренером? Купить, арендовать, нанять или ещё что-нибудь?

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Напиши сначала что-нибудь о себе. Хотя бы имя в профиле. А ещё лучше — поучаствуй в паре контестов здесь, или дай ссылку на свой профиль там, где уже участвовал.

    Иначе потенциальному тренеру будет как-то странно — неизвестен ни уровень, ни опыт участия в олимпиадах, вообще ничего. Даже не прочитать ни одной строчки твоего кода. А вдруг ты на самом деле Петя Митричев или Гена Короткевич? Или пишешь принципиально только на INTERCAL-е? Тогда круг возможных тренеров резко сужается ;) .
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо, контест был отличный. Особенно понравилась задача С.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Когда откроют коды для просмотра?
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
I got AC on D using some kind of optimised BFS. Not sure, however, that it is the right idea. But here it is:

For each pair <V, L> you save all ordered sets of n numbers such that you can find the common subsequence of length L that finishes in the positions from ordered set and has length L. Whenever you add new ordered set, you chould check if there exists a set that has the following properties:
1) For each sequence a corresponding number in it for this set is begger than in new set
2) Length for this set is less or equal to length of sequence ending in the new set
Every such set you should delete. Some other small optimisations are also requred.
The rest is just loop through all pairs<V,d> and all corresponding sets.
You can see my code in upsolving. Sorry in my English is not understandable enough
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
How come we cannot view code of other people's submissions?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    We can, but not yet. Viewing other people codes takes some time after the contest is over.
14 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
I have a question about gnu c++ compiler. Which precisely version is it? Today I had a problem with outputting a long long value. The "%lld" format works at my computer, not at checker; "%I64d" - inversely.
Thanks
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Если НОВП для двух последовательностей, то я бынапример  ее решил :) Ведь она была на северном четвертьфинале neerc в 2003 году
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    да, точно была. и я даже сдал ее тогда, но кстати, там решение за O(n^3). там по условию N=500, тут по условию N=1000 - за секунду может и не пройти)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Если обозначить за M кол-во разных элементов, то там можно не за O(N^3) а за O(N^2*M) реализовать. В той задаче это бессмысленно, там элементы в последовательностях большие, а тут может и прокатит, хотя все-равно на грани...
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Can someone show me how problem E works?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    It's a known problem... You can read this, for example:
    http://graal.ens-lyon.fr/~yrobert/algo/coins2.ps
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Thanks for the reference ;)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Wow, that's like the exact thing.  Did you know this before the contest?  I guess I don't read enough.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        No I didn't know that before, I was just very lucky to find it :)
        Once I've heard some lecture where some guy was talking about a criteria
        to check whether a knapsack problem is greedy solvable. I thought maybe this problem
        is also has a known solution, so I went straight to google and started to search. And after
        some time I've found this.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Not sure who David Pearson is, but that was one good paper.  I recommend it to everyone!
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      I wonder if someone solved it on his own without David Pearson help
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        I think it's physically impossible :)
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          It's possible to "guess" this algorithm in the contest. The algorithm is rather intuitive. Though a rigid proof to convince yourself needs sometime
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            I still cannot see why the relationship between the minimum counter example w and a[i-1] - 1 is intuitive or obvious.  Any insight into this?  May be I am just stupid.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Me :D
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I passed a tough time to understand the problems statements, specially C. Please try to make the problem statements more understandable. Though the problems were very nice, keep going :-bd.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Nerevar, а когда задача D будет изменена для поиска НОВП в двух последовательностях? Дорешивать охота =)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Минут через 15.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А на задачи пишутся скрёстные решения другими людьми:? Иначе баги такого типа могут быть постигнуты и в дальнейшем ...
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Обычно пишутся. И решения задач обсуждаются. Но в этот раз почему-то от этой схемы отступили. Ни обсуждений, ни альтернативных решений. Хотя я об этом просил. Буду надеяться, что этот случай был исключением.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Can anyone give hints about how to solve problem C ?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Yes, I can.
Hints are:
  1. Pre-calculate some values with dynamic programming
  2. Bust d(A) and d(B)

Full solution is:
  1. First, let's calculate cnt[X] - count of numbers from 1 to N, inclusive, with the fixed digital root X. We can do it with brute force.
  2. We bust A' and B', which is digital roots of A and B from condition
  3. For each pair (A', B') we need add to answer (which must be 64-bit integer to avoid overflowing) count of triplets (A, B, C), where digital roots of A and B are fixed (A' and B'), and digital root of C is d(A' * B'). But we need to deduct count of real solutions (let it be cntMul[A][B]).
  4. So, we need to count triplets (A, B, C) with fixed digital roots of A and B, such that C=A*B and C<=N. Well, bust first number (A), and we automatically get maximum B (maxB). For example, we can divide N to A or use two pointers. So, every time we are increasing A, we need to bust d(B) and add to cntMul[d(A)][d(B)] count of numbers, that are lesser than maxB and it's digital root is equal to d(B).
  5. We can dynamically maintain array with this count. Initially, array is equal to cnt[]. Every time we decreasing maxB, we 'delete' from it waste numbers. Just use one pointer.

And, if you can, leave feedback for my mistakes in English. :)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Hey , I really appreciate your effort to explain the solution , but I am still a bit lost :)  I didnt get what you meant by bust . And how do you define cntMul[A][B] ?
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      I think he means, in American English, brute force, or enumerate.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      cntMul[A'][B'] is count of pairs of numbers (A, B) with fixed digital roots - A' and B' such, that its multiplication - A*B is less or equal N. In the other words, it's count of solutions, when digital roots of A and B are fixed.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
This looks like an article that solves the original version of D:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.97.2394&rep=rep1&type=pdf
Personally, I thought the idea was to find this article, read it and implement during the contest.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Just looking at the abstract, the algorithm requires O(r) time, where r is the number of tuples where the sequences match, and that is one big number, right?
14 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
No. It is exponential.
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can somebody please write a tutorial for the updated D problem :)

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

In case of problem C, for N=4 why (1,2,2) and (2,1,1) is not among expected pairs?

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

Can someone tell me how to solve E?

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

Can Someone tell me how to solve problem D ?

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

    we need to build a graph over the elements after co-ordinate compression, consider two elements i,j if i is present before j in both sequences and i<j then we add a directed edge from i to j , now the answer is to find the longest path in a directed acyclic graph

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

Editorial ?