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

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

UPD: разбор

UPD:

D2: 500 1000 1500 2000 2500

D1: 500 1000 1500 1500 2500

UPD: Важно: контест проводится в необычное время! http://www.timeanddate.com/worldclock/fixedtime.html?day=20&month=7&year=2013&hour=17&min=30&sec=0&p1=166

Привет!

После шквала нестандартных соревнований (memSQL, ABBYY, Yandex), мы представляем вам стандартный, забавный (и странный) раунд Codeforces. Этот раунд подготовлен группой авторов из Индонезии: fushar, jonathanirvings, и я (dolphinigle)! fushar готовил D2-E/D1-C, jonathanirvings готовил D2-B, остальное делал я. Для меня — это мой четвертый раунд после Codeforces Beta Round 87 (Div. 1 Only), Чемпионат КРОК 2012 - Финал, и раунда на прошлой неделе MemSQL start[c]up Round 1 (там была только одна моя задача). Мы также хотим поблагодарить Gerald за помощь с контестом, Delinur за перевод, и MikeMirzayanov за систему!

Мне кажется, что этот контест более странный, чем обычные контесты — условия странные, куча картинок везде и тому подобное. Есть даже одна задача с очень длинным условием (к сожалению, я не могу сделать его короче не теряя сути условия). Остальные задачи имеют короткие условия.

fushar оставил для вас сообщение:

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

Приятного решения задач!

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

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

Хочется поскорее увидеть эти необычные задачи.

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

    И углубится в чтение и понимание условия на 2 часа?

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

      Можно.Но 2 часа уже перебор.Нужно ещё успеть код написать.

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

WOW like that kind of contests.

But to clarify, what do you mean by "unusual" or "unusual solutions"?

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

    Nothing drastic really -- you can compete as if it's a normal round and you should be fine :)

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

    May be the problems will have less similarity with past problems and the solutions are not as usual as we seen before.That means no chance to have a common problem. But that's only my point of view. :)

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

What you said really arouse my curiosity."you might find that the solutions will not be too “usual” " I hope I can solve some of them.

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

I imagine some crazy ad-hocs (contruction algorithms with tolerance, debugging a code, games where game theory is useless...) as strange tasks. In general, I don't find "strange" good, because it's easier to mess up when preparing such problems... oh well, I'm travelling to IMO during the contest, so I won't be able to participate no matter what.

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

What I can say is: the problems will be interesting, and you will be very satisfied when you solve them :)

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

You should mention about the unusual time in this contest!

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

"Есть даже одна задача с очень длинным условием (к сожалению, я не могу сделать его короче не теряя сути условия)."

А вот в ABBYY это могут сделать) Кто был на онсайте поймёт)

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

i cant wait :3

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

is the earlier time because of indonesian setter :P ?

i like this kind of time :D

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

Супер, после шквала нестандартных соревнований будет стандартный, но странный раунд. :)

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

    И я за! Даешь задачи для div2, а то решать одни и те же задачи c div1 сложновато. На последнем соревновании (ABBYY Cup 3.0 — Finals (онлайн-трансляция)) занял 362 место и ... понизился на 15 пунктов в рейтинге.

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

      Изменение рейтинга определяется не только занятым местом. Оно определяется также тем, насколько занятое место отличается от предварительно расчитанного ожидаемого. Ожидаемое место расчитывается исходя из рейтингов всех участников раунда. Поэтому нет ничего страшного в том, что в смешанном раунде есть участники с большим рейтингом. Если выступил "как обычно", т.е. как ожидалось, то рейтинг изменится приблизительно также, как если бы это был Div2/Div1 раунд. А вот если будучи "синим" прыгнуть выше головы и обойти большинство оранжевых, то прирост будет гораздо больше, чем если бы это был Div2. Бывают случаи, что синий прыгает через два цвета и становится оранжевым, например. В Div2-only раунде такое невозможно.

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

Everything is unusual. Expecting an unusual increase in rating too :-)

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

Слова "стандартный" и "забавный" раунд меня радуют, но "странный" почему-то пугает. а особенно условия "в картинках" — всегда с ребусами проблемы были

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

The other problems have relatively short statements.

I love short statements.

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

Seems a cool contest! "This contest is stranger than usual"

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

I hope I am able to solve at least one! I'm not very good at these contests and this would be my third contest

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

Hope that unusual solutions will uplift my rating unusual up. :)

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

It's nice to see many up coming contests already scheduled, this is going to be a very interesting week!

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

It's just a test~~~~

Codeforces is a test for me, too~~~~

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

What is the scoring method? If it's static scoring, what are the scores for each problem?

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

Ничего не сказано о разбаловке... Может для "интересных для придумывания задач" лучше динамическую UPD: Недоглядел английский коментарий автора соревнования

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

the contest will not be usual, en...., but I hope the contest will fit our taste, good luck & have high rating for everyone~

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

Ура, толпа не слишком сложных задач — это здорово =)

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

Я совершенно уверен, что регистрировался на раунд. Меня, правда, тогда почему-то перенаправило на страницу со списком команд, которые меня приглашают, но я не придал этому значения. Можно ли это все-таки как-то исправить?

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

Does 'mikemon' stand for 'Mike — monster'?

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

A really unusual contest!!

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

Is it possible that n can be equal 1 in Problem B div 2???

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

Unusual number of hacks!

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

I really like today's problems! But the number of hacks is a bit disappointing

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

Just find the bug several seconds after the contest finished!!!!WTF

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

Div-1 C — Разбор случаев?

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

    Или random_shuffle. =) Я не придумал, как его валить.

    UPD: А вот свалилось, поди ж ты.

    UPD2: Если увеличить количество итераций в 10 раз, заходит.

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

      Можно поподробнее, пожалуйста? У меня задача свелась к тому, чтоб разбирать циклы длины 3, 4 и цепочки длины 2, 3, 4.

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

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

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

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

        Фигачишь ребра рандомные, чтобы степень у каждой вершины была не больше 2. Если все получилось — выводишь, не получилось — еще раз пробуешь :)

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

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

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

        Вы пробуете много раз рандом шафлить вершины, потом пытаетесь поставить рёбра вида i,i+1. потом у вас образуется много цепочек. и каждую цепочку пытаетесь сделать циклом. Если рёбер уже хватает, то бряк. Утверждается, что на больших тестах это зайдёт потому, что маленькая вероятность попадания на запрещённые вершины, а на маленьких, потому что много успеет перебрать.

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

    Пытался решать жадным конструктивом, основанным на текущем множестве вершин степени 0, множестве вершин степени 1 и множестве запрещенных ребер. Претест 10 — WA. Весь контест не мог понять, почему он может давать неправильный ответ. Когда откроют тесты, станет понятно, ошибка в коде или алгоритм неверный.

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

Около трехсот с лишним мест занимают люди, решившие 2 задачи. Раунд = кто быстрей закодит халяву.

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

Как решать D? конструкция

>>>>>>.vvvvvv
.............
^^^^^..<<<<<<

получает только 85к

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

    Может быть

    UPD: именно то, что написано ниже

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

      repeated 50 times. Initial active stone is at (99, 1).

      One cycle gives 66 sounds (33 at the top and 33 at the bottom), and there are 33 cycles (until “^” can freely move up, where it activates the next cycle and gives another sound.

      50 × (66 × 33 + 1) = 108950 sounds in total.

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

    Думаю, что примерно так сработает, если <<<<<<< в конце около 50:

    >>>>>>>>>>>>>>v
    ^.<.<.<.<<<<<<<
    ^.<.<.<.<<<<<<<
    ^.<.<.<.<<<<<<<
    ^.<.<.<.<<<<<<<
    ^.<.<.<.<<<<<<<
    ^.<.<.<.<<<<<<<
    
»
11 лет назад, # |
  Проголосовать: нравится -19 Проголосовать: не нравится

Was it only me who noticed that 3 questions(!!) had something to do with matrices.

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

Wonderful contest. I don't think the problems are as strange as I expected before, but Div 1 D is certainly strange (pretests are all tests, and it's not really a programming problem) and it is certainly my favorite.

Also, in my room, only I submitted a hardcoded answer (for D)? Only I ripped off the first two cases from the sample cases (which then I regretted as it makes the second test case run for absurdly long)? :P

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

Wonderful contest! All problems are special and enjoyable to solve. It's really amazing to discover solutions!

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

Thank you for the contest! D was definitely memorable.

Speaking about D, does anyone have a successful ring-based approach? I get a feeling there might be a solution but it'll be considerably harder than snake-based approach. My best try took about 85.8K.

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

this is my first time to join the codeforces contest and i feel really excited to beat the buzzer~....the questions were not too unusual....

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

still slow…… sbcf…… I pressed "submit" when there were only 10 seconds left. After 20 seconds, Codeforces show me an error page...

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

    visited[i][j]=true; bad idea) Need in if() { visited[i][j]=true; }

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

    Looks like you can add vertices to the queue more than one time, because you don't check visited before adding. Try empty field 20x20 and look at the size of your queue.

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

    Yeah, it's MLE.

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

Found D1-B funny: despite the huge statement about mikemon breeders looking at the path beforehand, it is completely irrelevant for their optimal strategy anyway (they should all just run to the exit as soon as they can!)

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

    Exactly. That, I believe, is the crucial deduction; after that it's just implementing breadth-first search from the exit to see which breeders can reach the exit before or at the same time as we can.

    Additionally, even though we're not required to minimize the number of moves, the optimal strategy is indeed to minimize the number of moves to reach the exit.

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

It was a very amusing contest , In problem D , I spent a very long time in the contest trying to figure how to get the shortest path from some nodes to a node avoiding high complexity, and I totally forgot that it's the same from the other side :D Changing the starting point of the BFS will make the code pass :'(

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

very slow system test:|

I solve problem D div2 2 minute after end of the contest:(((((

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

    You aren't the one, i only figured a bug in my code of D div2 after the contest ended..

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

for problem div2 B Road Construction. in case 1 is WA for input 4 1 1 3 output 3 1 2 1 4 2 3 why is incorrect?

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

I don't know if I got the question wrong. some of the solutions are accepted but for the following test case they give wrong result.

4 2 1 2 3 4

For above test case they dont print anything but solution exists. 1 3 1 4 2 3 2 4

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

Can anyone point out the mistake in my solution http://codeforces.me/contest/330/submission/4121524 for Div2 D/Div1 B — Biridian Forest? I have used a bfs to compute distance of the exit from each point. I have stored the graph in 1-indexed arrays and put trees on the boundary so that the algorithm does not process invalid points.

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

    I don't see where you check vis array when computing the answer. You may add to result points from which finish is unreachable.

    See the comment below for the example.

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

      I check it here: for(int i=0;i<4;++i){ int newx=x+dx[i]; int newy=y+dy[i]; if(vis[newx][newy]||(inp[newx][newy]=='T')) continue; vis[newx][newy]=1; } I don't include a point if it is a tree. I have added trees along the boundary too. How can unreachable points go into the queue?

      EDIT: Got it. This mistake cost me a colour change :(

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

    Try this case:

    4 4
    ETTT
    0T9T
    0TTT
    000S
    
»
11 лет назад, # |
  Проголосовать: нравится +54 Проголосовать: не нравится

It looks like someone throws the testing machine into water...more and more slowly...

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

Proud to be Indonesian! too bad I competed on Div 1, my skill is not enough to "enjoy" all the problem, lucky I could solve 500 pts problem.

Btw, I'm a big fan of fushar/Ashar Fuadi (yes, I said that). I never beat him on local contest, my team's best result was able to solve as much problem as fushar's, but beaten by time penalty. He's a very good problem solver/setter, and a humble person too. This year is my last year in university, so last year competition season was my last season. So good luck for you and your team fushar, hope you all will achieve World Final next year. And good luck for jonathanirvings too, Go Get Gold! And dolphinigle too! (too bad I don't know dolphinigle personally).

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

My solution for Div2-C is wrong and got AC.

Input:

4
.EEE
.EE.
EEEE
E...

Output:

1 1
4 4
2 4
4 2
4 3

While the minimum number of spells is 4.

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

    If I were you, I would not advertise it

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

    Looks like I missed this test case.

    Originally the problem has more than 120 test cases, but to make system test faster we decide to reduce it to 60. It's likely that I accidentally removed the case that would've countered your solution.

    Sorry and thanks.

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

Единственное зашедшее решение по Div2-Е 4121855

if(clock()>2800000.){
	puts("-1");
	return 0;
}

Убило! :D

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

Examples were explained very good and pictures were really nice and clear. Thanks for the contest.

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

Ого, так быстро рейтинг посчитали

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

Really love this kind of contests. Thank you dolphinigle, fushar and jonathanirvings!

I spend one hour to find a deterministic way to solve C, but it's too complicated to code. After some minutes of despair, I figured out if N is large then there will be lots of solutions, so I code a naive random algorithm and passed.

After the contest I read the problem D, it's more interesting! If I read both C and D, I will definitely try D first. :)

By the way, does "mikemon" in problem B refers "pokemon"?

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

    Thank you! I'm really happy to hear people enjoying my contests :)

    ...and for the other question, I replaced "po" with "mi" >:). You should read it "mi" "ke" "mon", not "mike" mon.

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

    Actually my personal intended solution is the deterministic one, but we also let randomized solutions pass quite easily :)

    By the way, there exists a deterministic solution that is not very complicated (although there are too many tricky cases for this problem) in the editorial soon.

    Yes, this actually refers to Pokemon, but we were afraid of copyright infringement so we changed it to mikemon :P

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

      Here comes a deterministic solution.

      First check whether this graph has a connected component of size no less than 5, if so, we can use these vertex to construct a circle. It's easy if we connect vertex i with (i+2)%size and be careful when size%2 == 0.

      Otherwise if there exist two different connected component of same size 2,3 or 4, we can construct the circle easily by union them. You can also do this when you have four isolate vertex.

      Now we keep this circle in hand, then for all other connected component, if its size is large than 4, we just construct a new circle by themself, otherwise we can insert them to the circle we keep because the circle's size is no less than four.

      The only question now is how to deal with the situation that we can not build a circle first. If so, this graph can just contain at most 3+2+3+4=12 vertex, then we can do a simple search algorithm for that.

      I come up with this idea durning the contest and spend more than half an hour to code it but finally fail, it's really a huge work for poor me. I feel very depressed when I see so many random solution pass the system test >_<.

      Here is my accept code, it's a little bit ugly... http://codeforces.me/contest/329/submission/4123108

      But indeed, it's a really nice problem, thanks for your work. :)

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

      Do we have some guarantees of the accuracy of the randomized one. Actually I use a deterministic solution employ divide and conquer of time complexity of O(nlogn) and deal with a tricky case of circle_length=3.

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

    Thank you. I'm really happy to hear that. Actually I only wrote Div-2 problem, so I couldn't "entertain" Div-1 users in this contest. (Well, maybe next time :))

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

Though I got -49, The contest was really good and encouraging for all, specially for beginner. :)

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

can anyone please tell me why my solution of Div 2-B is giving WA on test 29 as it is giving correct ans on ideone as well as on my system also... my solution-- http://codeforces.me/contest/330/submission/4116737 http://ideone.com/Wet1Tt

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

Как решалась бы Div-2 D, если бы, когда заходишь на выход и не ждешь микемонов, то есть сразу выходишь?

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

    В моем решении просто знак <= поменять на <.

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

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

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

        Если бы не ждали у выхода, то ждали бы у одной из четырех соседних клеток.

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

The contest was really good . . . .

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

how can I see why my submission to "Purification" (div1-A) problem gives compilation error?

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

    Ok, I see, I forgot #include Anyway, how to use "custom test" to see that?

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

    I mean I forgot "include cstdlib". I don't know how to use "custom test" to see that.

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

    If you click on compilation error you will see what's the cause of CE. Edited : Sorry! Didn't see your last comment.

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

    It gives "exit was not declared in this scope" on my computer.

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

    You should be able to click on the "Compilation error"?

    But anyway, you declared i four times, in each for loop. That gives the compilation error (redeclaration of variable).

    EDIT: Weird, I tested redeclaration and got compilation error, but when I copied your code instead, it gave the "exit was not declared" error as above. So the reason I gave above might be incorrect.

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

      That is not the reason. i is considered to be declared in the loop, so it is not a redeclaration.

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

    In custom test you will see your compilation error on output section.

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

      I got the message "Error: Form elements must not have name or id of "submit"." I don't understand this message.

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

Anyone can say me what is wrong with my submission in problem B here:

http://codeforces.me/contest/330/submission/4121515

The checker simply says that : wrong answer You cannot constract bad roads.

Which bad road did i constract? How can i see it. How can i see whole input, answer and output for the wrong test?

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

Nice contest! Thanks!

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

(Y) (Y)

I didn't manage to participate, but my friends are saying it was lots of fun. I hope problem setters make more of this kind :)

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

Прочел сейчас задачи второго дивизиона, меня одного смущает это в первой задаче?

Дан квадратный торт, который имеет вид таблицы размером r × c

Ну и первый же пример — "квадрат" 3х4

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

    Меня не смущает. Торт 3х4 вполне может быть квадратным, если состоит из прямоугольных ячеек (4см х 3см, например). А вот "квадрат" на рисунке действительно смущает

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

Very interesting contest! Like Problem D in Div-2 the most! I always enjoy solving the problems that seem complicated and require the contestants to think in a clever way.

BTW, can someone give me a hint for E in Div-2? It has puzzled me for a while.

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

[Div2:B]After the contest, I suddenly tend to realize the importance of the constraint m < n/2, which ascertains the existence of a central junction which could be connected to all the remaining cities. My Question is: What if we relax the condition m < n/2. Let m be any number.
For example (A test case):
6 7
1 3
1 4
1 5
2 6
3 4
3 5
4 5
Here there is no central junction but there is still a solution which is:
8
1 2
1 6
3 2
3 6
4 2
4 6
5 2
5 6
What would be the algorithm in this case?

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

    Sorry, that was a bad idea.

    If the solution exists, it would certainly be a complete bipartite graph, but I don't know the algorithm for dividing the vertices between the two sides.

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

hey well done guys, it was an interesting contest! the only thing i would like to suggest for future contests is that u increase the possibility of hacking by excluding a few corner cases (not all, mind you! :P ) from the pretests!!

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

Could anyone please tell me why this code behaves differently on Codeforces and ideone (also my laptop, if that's a valid standard for anyone)? I get wrong answer on pretest 12, but it works correctly on the aforementioned platforms.

Thank you in advance.

http://ideone.com/c5kfDT http://codeforces.me/contest/329/submission/4122055

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Visual Studio Debug Mode:
    Expression: map/set iterator not incrementable.
    

    You are removing some elements from the set in another level of recursion, and when you go back the iterator still points to the removed element.

    Check this code (same error): http://ideone.com/nzrPXb

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

today's contest was a great contest, OMG!! um loving codeforces. Coderforces why you are so lovely and sweet?? :)

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

codeforces i love you

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

codeforces is better than topcoder in all ways.. and its the best in the world

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

I haven't see in the table submissions if they don't have AC. It's true only for div2 table viewing friends result

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

Guys, thanks for this contest! Now waiting for tutorial)

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

Здравствуйте, объясните пожалуйста идейно задачу Div.2 (B) Заранее признателен...)

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

    div1(B)

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

    Если мы возьмем какой-то город и соединим его со всеми остальными городами, то получится как раз то, что нужно. Осталось только найти такой город, который не принадлежит ни одной из запрещенных m дорог и соединить его с остальными (n — 1) городами. Такой город найдется, поскольку m < n / 2.

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

Hey, that was a good contest. I regret missing it.

By the way, in Div2 B the constraint m < n / 2 made it pretty simple.

How would you solve it without this constraint?

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

Some solutions to Div1-C work as follows: choose a random cycle on the N nodes and see if it works (some edges in the cycle may be invalid and we can ignore those).

Why does this work? What's the worst case probability that a randomly chosen cycles isn't valid?

One bad case seems to be when every node in the input graph has degree 2. In this case, every edge in our random cycle must be a valid edge.

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

    This is one of the intended solutions -- we set the time limit so high that even python solutions will pass using this method.

    A rough approximation I used is by evaluating ((n — 2) / (n))**n. On n=100,000, it is 0.135. I think the actual number shouldn't differ too much from this (like how Derangement Probability does not differ too much from ((n-1)/n)**n).

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

Nice (Ad-hoc) Contest. Tutorials please . :)

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

Problem C:can anyone explain how the case no 10 can be purified ? , the answer that is given cannot purify cell no (5,7) & (5,8). my answer is -1 and it gave wrong ans. :(

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

    in edition according to editorial as it has 5th row and 8th column completely full with E it can't be purified , am i understood wrong? :( PS — it's test ( not pretest ) i am talking about.

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

      The correct answer of tenth test case is -1.

      So what goes wrong? It is YOUR code gives a solution, which is invalid, not jury's.

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

        sorry , i just wanted to know why wrong and not who's wrong ; and i believe jury's are much much better than me and i'm not being disrespectful; :) editorial says: "If there exist a row consisting of entirely "E" cells and a column consisting of entirely "E" cells, then the answer is -1. This is since the cell with that row and that column cannot be purifed." test 10 input: 17

        EE...E.EE.EE..E..

        E.....EE..E..E..E

        EEEE.EEEE..E..E.E

        .E.E.EEE.EEEEE...

        EEEEEEEEEEEEEEEEE

        EE.E.EEEEE.E.....

        ..E.EE.EEE.E....E

        .E..E..E...EE.E.E

        EEEE.EEE.E.EEEE..

        ...E...EEEEEEE.E.

        ..E.E.EE..E.EE..E

        .E..E..E.EEE.....

        .E.....E..EEE.EE.

        EE.E...E.EEEE.EE.

        ...EEEEEEE.E..E.E

        EEEE.EEEEEE....E.

        ..EEEEEEE....EEEE

        the 5th row and 8th column is entirely of E

        so , why the answer is not -1 occured to me.

        hope i got a explanation not what's correct answer

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

          The answer is -1, while your output is not.

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

            (sigh) it's the answer and i know that but how , please can u explain a bit elaborately :(

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

              But you have already explained it — as long as fifth row and eighth column both contain only 'E', answer is -1, because you can't purify (5, 8) anyhow. What else do you want to know further?
              Notice how judge's verdict is located:

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

Задачи были хорошимы. Единственный минус — взломов почти не было!