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

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

MikeMirzayanov


Обратите внимание, что мы напряглись и подготовили дополнительные задачи для Div 1. Таким образом, параллельно с отборочным раундом будет проведен Codeforces Round 434 Div.1+Div.2 (рейтинговый раунд для обоих дивизионов — всё как вы любите). Участвуют все!

Добрый день.

17-го сентября в 16:05 (московское время) стартует Отборочный Раунд 1 (и открытые раунды для обоих дивизионов по его мотивам) олимпиады для школьников Технокубок 2018. Раунд будет длиться два часа, участникам будут предложены 6 задач. По его результатам лучшие участники (но не более 45% от общего числа участников раунда) будут приглашены на финальный этап в Москву. Для регистрации на раунды и участия перейдите по ссылке. Не забудьте заранее зарегистрироваться на раунд. Впрочем, если забудете — не беда. Через 10 минут после старта будет открыта дополнительная регистрация для опоздавших (ее длительность — 20 минут).

Зарегистрироваться на Отборочный Раунд 1 →
Соревнование открыто для всех в виде отдельных раундов для первого и второго дивизионов.
Для всех участников всех трех редакций этого соревнования будет пересчитан рейтинг.

Напомним, что согласно правилам раундов Codeforces во время соревнования ваши решения будут тестироваться только на претестах (предварительном и неполном наборе тестов), а системное тестирование состоится после окончания раунда. Обратите внимание, что претесты не покрывают все возможные случаи входных данных, поэтому тщательно тестируйте свои программы! После прохождения претестов у вас будет возможность заблокировать решение, тем самым получив привилегию искать ошибки и взламывать чужие решения, но отказавшись от возможности перепослать ваше решение при каких-либо обстоятельствах (например, даже если вы найдете ошибку или вас взломают). Со временем задачи падают в стоимости. После системного тестирования учитываются только полные решения. Подробнее про правила соревнований можно прочитать по ссылкам:

Регистрация на олимпиаду Технокубок еще открыта. На кону — значительные квоты при поступлении в престижные технические вузы России и ценные призы. Если вы — школьник 8-11 классов и пока не зарегистрировались на Технокубок, то самое время сделать это:

Зарегистрироваться на олимпиаду →

В финал соревнования будут приглашены лучшие участники каждого из отборочных раундов (но не более 45% от общего числа участников раунда).

Большое спасибо KAN, vovuh, Neon, ifsmirnov, irkstepanov и WHITE2302, все они участвовали в подготовке раунда.

Желаем удачи на олимпиаде,
MikeMirzayanov и команда Технокубка

UPD: Соревнование завершено. В отборочном раунде Технокубка первые три места заняли:

Место в Финале Технокубка достается лучшим 100 участникам раунда (по участника dfczyjd включительно). Поздравляем победителей!

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

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

Извините за вопрос ,а отборочный раунд рейтинговый ?

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

you forgot to thank MikeMirzayanov

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

MikeMirzayanov is the writer of that note he cant thank himself!!

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

Отборочный раунд будет больше как див 2 или как див 1?

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

    По опыту двух прошлых лет: как див2. Финал: как див1

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

Mike himself to the rescue B)

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

And thanks MikeMirzayanov for the codeforces platform,great polygon and also for this post.

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

Is it Xxxxx ? (Please no downvotes)

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

Is this contest only for a Russian speaking student?

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

Если я участвую в официальном раунде, будет ли рейтинговая формула учитывать и участников из зеркала?

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

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

this round will be rated or not ?

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

Sorry for bad knowledge of codeforces, but will there be hacks in the official round?

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

I hope it will have begineer level A like yesterday... ;-)

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

is it....emmm, interesting ?

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

Please announce the scoring!

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

    They didn't say, they will. :D

    As soon as the contest starts, you can see it both on standings page, and on the right bar.

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

Если я не ошибаюсь, раньше приглашали min(100, 45%) участников раунда на финал, а сейчас просто 45% участников

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

3993 мс на претестах... Надеюсь, в претестах есть макстест...

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

10 pages queue !!

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

Очередь 11 страниц...

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

My solution is 'running on pretest 1' since 15 mins.

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

testing system is stuck

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

Я человек простой, задержка больше 20 минут, минус на пост)

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

Such a long queue...!! I guess round should be declared unrated...

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

Experiencing Queue on hacks for the first time

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

What would happen if two person attempt to hack a code simultaneously when there is a queue on hacks ??

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

Is Codeforces mining bitcoin?

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

Will it be unrated?

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

twenty minutes to receive a "Memory limit exceeded on pretest 1", RIP points

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

such a long queue :( waiting since 20 minutes.

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

Well, this queue is unresonably long...I must say

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

This contest

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

Long queues... So most likely this contest is unrated.
Moment of silence for all our brothers/sisters who realized this news after 2+ hours on this contest, as they were only giving the contest to increase their rating.

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

In queue...

after the contest end

Wrong answer on pretest 7

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

My Rating Graph clearly depicts the guy who is the mayor of the friendzone.
I was about to break it through the friendzone and get laid today finally but long queues will most likely result in declaring the contest unrated.

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

My 2D works OK on my computer but WA on CF, WTF

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

Please make this round unrated. I still don't know whether my solutions have passed the pretests or not.

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

    Now it showed me wrong answer on pretest 7 for E problem now and time is increased by 10 mins. So much of adrenaline rush !!

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

Such a long queue. Waited for 20 mins just to find out WA of pretest 6.

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

If i have submitted right earlier and by mistake i made another wrong submission which will be evaluated

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

I waited for 30 minutes, but my code is still in queue. :(

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

Maybe the system is trying to teach us that a solution aged for 30 years is valuable than one aged for only a year. Like a whiskey or a wine.

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

Yeeey, another unrated round, haven't seen for some months...

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

I'm alone who's sad that round isn't rated?

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

What happened on the juding system? I have participated in some rounds(and watch some) recent two months and found almost half of them get stuck in queue after 1 hour of the contest. What is the bug of this system? Could it be fixxed some time? Very eager to get a fluent contest without waiting for In queue and in queue and in queue..... Or finding the 404 and 403 and 504 and so on.... Hope Codeforces will be a better Online Judge System/

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

A sad story.This round is unrated...

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

Well, now I don't have to worry about my submissions failing systests because contest is unrated anyway :)

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

Barichek не школьник уже.

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

Unrated. Rip Top 20 :(

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

Unrated :( Rip top 20 :( Huhu

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

неттттттттттттттттт(

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

I was gonna have a +120 rating change :(

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

I sumbit 2B with the same code for twice, and heres the results.

30437680

30439382

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

How to solve Div.2 A?

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

    contest isn't over yet.

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

      Oh sorry, I had an old tab open with the time before it was extended.

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

    Isn't answer just LCM(10k, n)?

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

    my idea for A is: since number of zeros in the end is the minimum of powers of 2 and 5 in a number, I calculate the powers of 5 and 2 that are in the number, and I put more 2's and 5's as needed to make the minimum of powers of 2 and 5 at least k, for example n = 375 and k= 4, 375 contains 3 fives and 0 twos, so I add 4 twos and 1 five (2^4 * 5^1) = 80 and multiply it by 375 = 30000

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

Finally, my solution for D passed after 30 mins. What a happy story!!!

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

Really didn't expect this after yesterday's contest, especially considering how the system tests took like 10 minutes. A lot of people have to wait longer to get their submission judged than that entire system testing took. These sort of issues are really unfair on everyone, unfair on those who did well because they won't increase in rating, and unfair to those who got stuck in the 30 minute queue.

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

Well still no red for me :')

(Ehh why always when I do ok on a round it becomes either unrated or I have a stupid bug and one of my solutions fails)

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

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

    your fourth submission pretests are still in queue. Hoping for your statement to come true soon. My E is also waiting.

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

    Perfectly described me.(P.S.:with +1:-3 Hacks by the way)

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

    Same opinion in Div.1...

    The first time for me to be in top 50...but unrated...

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

You know you are a programming competition addict when you get your best rank, and you come to know that the contest is unrated(at the end of contest), and still you are alive.

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

How to solve F?

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

I unaccepted 2B 4 times. thanks for the unrated. I don't worry about my rating!

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

Looks like problem F from this round and http://mirror.codeforces.com/problemset/problem/406/C are the same.

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

Will it take a lot of time to system test? I want to go to bed because it's midnight in my country...

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

    As I understand, the intended solution there is something called "string hashing". Does "string hashing" mean just cramming it all into a hash table as I did (and got AC) or is it supposed to be something more clever?

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

div1B is bad in my opinion. Just many maps/sets/hashsets will pass, although trie is intended(at least I think, that it is).

UPD: And it's already well-known problem, link is 2 comments above.

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

    Why do you think solutions that require hashing are bad?

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

      For this platform it's bad, because most probably it can be hacked. For instant full feedback contests it's fine.

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

        Well for this problem if we do polynomial hash with base 13 it will fit in a 64-bit variable so I don't see how it can be hacked.

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

        Even for this platform using for example polynomial hash with 4-5 random prime bases and random prime moduli, it may fail, but not by hacking.

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

      Because it's too easy for a Div1 B when you can very easily use map and set from C++

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

    Yeah, seems solutions with map gets pretests with 3500+ms, but I think they will fail at system tests...

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

      My unordered_map solution ran pretests in 1.38 sec

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

      I used unordored_map and it passed in ~2700ms which has a decent chance of passing system tests

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

      I doubt that. There are only at most

      values to hash, and I don't think calling map, set, etc. that many of times would exceed the time limit of 4 seconds.

      • Edit : edited after checking the problem parameters.
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

    I have a tricky solution. Using map with substring of length 8, for substring of length less than 8, just use array[2.10^7]. :)

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

как узнать кто пройдет дальше в технокубке?

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

My logic for D was -- for every suffix of a given string insert it into the trie then for ans for each string for every starting position calculate the depth of the position where trie[node] has only 1 index Can someone tell whether this logic is correct cuz I got WA.

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

What is the pretest in div2 B?

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

How to solve div1C/div2E ?

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

When s̶y̶s̶t̶e̶m̶ pretest testing will be finished?

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

I'm really disappointed ! Just spend the whole evening and the contest was unrated !

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

    Well...I think despite the slow judgement,spending whole evening enjoying the problems themseves is OK.(Maybe I'm too weak to say that,but we do these problems to improve ourselves and get progress as well...

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

I Think This Round Should Be Rated And Used This :- New_Rating = Old_Rating + max(rating_change_that_was_going_to_happen, 0);

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

    It is very bad idea, also not fair...

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

      Why Not? Explain Please.

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

        Everyone had problems in this contest, so rating must be changed or not changed for everyone.

        One little update: Someone has rating ~1890 and with rating change he will be ~1910, but if there was not long queue in contest, s/he could make 2000+ rating which is better, because with 1910 rating you will fall expert if you write bad in your first contest, but this doesn't happen with 2000+ rating...

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

        Think for next contests, they are wrong again and we will continue to apply your formula and what will happen? Maybe all coder will have rating > 1900. All people will join Div.1 !!! And maybe I will get Red color soon :))))

        p/s: I solved 4 problems in this contest, but I don't care about rating.

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

    instead of spamming these illogical comments. Do some practice your rating will increase for sure

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

    Taking such measures often enough would lead to unnecessary rating creep.

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

UPDATE: the problem was just casting. Works as expected in GNU G++14, but not in GNU G++11.


So, there is a weird bug with the GNU C++11 compiler... I was getting TLE in pretest 1 with http://mirror.codeforces.com/contest/861/submission/30432329 I got it solved by removing the pow call: http://mirror.codeforces.com/contest/861/submission/30432756

pow(long long, long long)

pow(10LL, k), where 0 <= k <= 8

Doesn't seem to ever exit the function... but works fine in every other environment I've tested. Waiting for the end of system testing so I can make sure it's really the pow, and only in GNU C++11.

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

    pow() returns a double, not an integer or long long

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

      UPDATE: okay, so I tried it and you are right, pow is returning. The problem is exactly the cast. In GNU G++11 (long long) pow(10, k) turns out 10^k - 1. In GNU G++14, however, it works as expected.

      I should have been more careful. Not the first time I have a problem with double -> int casts, and I keep making the same mistakes :).


      Since submissions can't be seen until the end of system testing, this is the line: long long k10 = pow(10LL, k); // k is a long long

      Even if it returns a double, it's then casted to a long long. The point is, it never returns, so it doesn't even matter what it returns...

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

        How do you know it never returns?

        Have you tried with CUSTOM INVOCATION?

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

          Custom invocation was not working (would run forever with any code I submitted), but as soon as it started working again I tested it and now I know it is returning. The problem is the cast.

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

Todays contest be like

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

When you finally did ok on a round

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

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

Очевидно же. Все потому что он не поблагодарил MikeMirzayanov)

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

I made a video explaining my approach to problem div 1 a div 2 c https://www.youtube.com/watch?v=p4JGd5g9K9o&feature=youtu.be

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

After waiting for 10min, my long-queued submission turned out to be WA on pretest 2.

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

This all happened because there is no thank for Mike in announcement... :(

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

    What is the pretest 3 of div2.b?

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

      I don't know this test, but here is why you got WA3:

      When you check if you found another count of rooms for each floor, don't print -1 immediately, also check if n is not in the same floor with previous answer.

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

top 100 get shirt?

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

I'm pretty curious, but what sort of technical errors can lead to a round being unrated? Like, I think with the timestamps of all submissions, rating modification is always possible (as long as the contest setter intends to do so).

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

    What about if I waited for 30 mins for checking my solution then got WA and realized little bug immediately? 30mins is 1/4 of contest...

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

      Ah... I got it now. I did feel the same thing when waiting for problem D, at least it turned out good (not sure if it could withstand the system tests). But okay, thanks.

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

      i see, but i was going to be an expert if this round is rated

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

For problem F, would it be right to say the following? Construct a new undirected graph where the edges from the input graph are considered as vertices and if any two edges in the input graph are incident on some same vertex, then connect them in the new graph. The vertices from the input graph are not considered in this new graph. Now find the maximum matching in this new graph. This gives the answer. I know this won't work even if it is correct but I just want to know if this reduction is right. Thank you!

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

    This reduction is correct. Nevertheless, it cannot get AC, because in some cases it requires constructing too big graph. For example, imagine a test with n=100000, m=99999 and with edges {1,i} for each i from {2,3,...100000}. Then your sollution needs to contruct a new graph consisting of m*(m-1)/2 = 4999850001 new edges, which is far too much to hold in memory without getting MEM/RTE. Your sollution's expected time complexity is O(m+n+E*logm), where E is the number of edges in new graph, which is enough if E doesn't exceed 10^6. However, due to the fact that E can be O(m^2), pessimistic time complexity of your sollution is O(m^2*logm), which is too slow to be able to pass all tests.

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

test 43 on Div1C?

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

Почему до сих пор нельзя смотреть посылки других участников?

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

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

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

    В понедельник появится список на сайте, а так же придет письмо на почту всем, кого приглашают на финал. Обычно проходят 100 человек.

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

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

Возможно ли увеличение количества прошедших в заключительный тур из-за проблем с тестированием во время раунда? Потому что результаты тестирования и взломов приходили с большими задержками. Например мне пришел вердикт о том, что я указал во взломе некорректный тест, уже после окончания раунда (тест для взлома я отправил ровно за полчаса до конца раунда). Хотя если бы это случилось ранее, то была бы возможность исправить это и получить баллы за этот взлом.

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

    Вряд ли организаторы увидят твой комментарий. Впереди ещё 2 отборочных раунда, у тебя будет шанс занять высокое место.

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

My one of the best performance, but unrated :(

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

When can we submit the code in Practice. Can not currently :(

Update: We can submit now :')

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

When will the editorial be posted?

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

    I think I have solutions to everything in Div 1, even though I couldn't get them to work in the contest. Here's the short, short editorial:

    A: Greedily extend the current word until adding another letter would violate the condition. Constraints are low enough that you don't have to be particularly clever (I think my solution is O(N^2) even though linear is quite easy).

    B: Make a frequency table of how many words contain each substring. You have to be a little careful because a substring might appear twice in one word. Then for each phone number, check every substring in increasing length until you find one that only appears in that number.

    C: Make two lists of initial filenames (examples and other), say I0, I1 and target filenames (examples and other), say T0, T1. Any file that already has a valid target name for its type gets crossed off both lists. If I0 == T1 and I1 == T0 then you have to rename some file to a temporary to break the cyclic dependency. After that or otherwise, you can always find some target in T1 \ I0 (or T0 \ I1), and then pick the source from I1 & T0 (or I0 & T1) if not empty, otherwise any from I1. You can prove that applying this renaming is safe and will again allow a subsequent renaming.

    D: In each component it's always possible to use half the edges. In fact, it's possible to picks off episodes such that the component remains connected. Build the DFS tree. Where a vertex has two up-edges, combine them into an episode — removing up-edges won't affect the DFS tree. Now pick the deepest leaf, picking one with an up-edge if possible. There are a few cases to consider, but it's always possible to use the edge from the leaf to it's parent plus some other edge in a way that won't disconnect the tree.

    E: I'm using a heavy-light decomposition and small-into-large merging. My solution was running out of memory (it turns out a deque per node uses a surprisingly large amount of memory even if they're empty), and I want to check if it's fast enough before posting my approach — I'm not 100% sure it is actually O(N log N).

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

      There is a near-linear solution for E using LCA and a stack.

      30443098

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

      Your solution seems to be O(N*sqrt(N)). The code below gives test cases where your solution performs a little over 0.6*N*sqrt(N) calls to push_down. I think that is about the worst you can do, since only the push_down call on the heavy child seems suspect (I think) and because of the merging of light childs before it, it seems a vertex can receive at most O(sqrt(N)) such calls.

      int n = 500000, d = 0;
      while (3 * n - 3 * (d + 1 + (d + 1 + 2)*(d + 1 - 1) / 2) >= 2 * n) ++d;
      vector<int> p(n);
      p[0] = -1;
      FORE(i, 1, d - 1) p[i] = i - 1;
      int at = d;
      REPE(i, d - 2) {
      	int prv = i;
      	REP(j, d - i) { assert(at < n); p[at] = prv; prv = at++; }
      }
      while (at < n) p[at++] = d - 1;
      printf("%d\n", n);
      REP(i, n) { if (i != 0) printf(" "); printf("%d", p[i] + 1); } puts("");
      
      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Yes, I'd also concluded that my solution is O(N sqrt(N)). Once I fixed the memory usage it passes system tests though, so the tests are probably not that strong. I think the push_down calls can be improved because they'll always operate on a contiguous range of the vertices at each level, so they can be made O(depth of light subtree) rather than O(size of heavy subtree to depth of light subtree).

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

Rating changes for contest: Div. 1, Div. 2, Технокубок.

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

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

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

Does anyone have an O(n log(n)) approach for div1 E ?

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

    Can you please share your approach.Solutions are not public yet.

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

    Yes, me. Also, it is possible to get O(N) if I use LCA in O(N) precomputation and O(1) query, but it's just theory. Add nodes in layers and construct the compressed tree with the current nodes and do some partial sums

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

Когда будет разбор задач?

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

When will we be able to see testcases/resubmit? I'm curious about WA76 in Div1C.

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

Сколько участников прошло в следующий раунд и будят ли другие раунды зависеть от этого

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

I think using O(nlogn) for intended solution in 1E and trying to make O(nlog^2n) can't pass is not a good idea in cf :/

I thought O(nlog^2n) is really fast and submitted without thinking and got TLE in the system test.

UPD: resubmitted the TLE code without editing and got AC :/

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

i have an issue, my code pass div 2 problem D's pretest, then my code get time limit exceeded on test 3 when system testing, then i resubmit again after system testing, and ac,,, what is going on???

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

This is quite weird. My answer for div2 A here gives correct answer 30000 for pretest 1 on my system but is giving wrong answer 29952 on CF. What can be the reason? Any help is appreciated.

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

    pow() returns double, write one that calculates in integral type by your self!

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

      Thanks, that worked.

      But here both arguments are integers, then why should returning double be a problem (I am typecasting the result in long long)?

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

        Cause pow(base, exp) = {base}exp = (eln(base))exp = eexp * ln(base)

        This is how pow function implemented among almost every C++ compiler. Both functions ln and ex calculate result by Taylor series. So there always will be some error. If you want integral-type based implementation you should do it by yourself.

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

Эхх... Мечтал оказаться в блоге, а выложили только топ-3.

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

editorials please?

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

Can anyone please help in Div2C.I am constantly getting WA on test case 40.Here is my code.

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

    Try this input: dfacccbabc

    Output that you should be getting

    dfaccc babc

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

      I am getting "dfacccbabc" when i am running locally.I am not able to get my mistake.

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

        Yeh i get it. That's why i gave this input. So now you know what's your mistake, should be easy to correct i guess.

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

      I can not figure out , why the answer should be dfaccc babc?? Will you please explain?

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

        From what i can figure out this is your mistake-

        Once you're getting consecutive consonants which have all the same character you're printing all of them, which you shouldn't. Suppose you've got cccccba then printing cccccba is incorrect as you'll have a substring ccb which is a typo and should have been printed cc b or rather the whole string ccccc ba.

        Hope this helps :'). Haven't looked at you code but i'm guessing this is the mistake.

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

I submitted my TLE code for D after the contest and it gets AC. Can someone please comment on this?

TLE submission during contest: http://mirror.codeforces.com/contest/861/submission/30435774

Submission after the contest: http://mirror.codeforces.com/contest/861/submission/30459324

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

Editorial please!