Codeforces Round #215

11 лет назад, # |

Какие вырожденные случаи существуют в задаче С 2-го дивизиона?

→ Ответить

11 лет назад, # ^ |

Если длина подстроки меньше трех, то ответ всегда YES.

→ Ответить

11 лет назад, # ^ |

тьфу... Обидно.. Спасибо..

→ Ответить

Eran

11 лет назад, # ^ |

строка q длиной менее трех символов

→ Ответить

11 лет назад, # |

+57

А за взлом жюри +100 не дают, да?

→ Ответить

11 лет назад, # ^ |

+36

Тогда +300, у нас было 3 решения, все упали.

→ Ответить

Zlobober

11 лет назад, # ^ |

Ага. Картина маслом: у меня -2 по задаче, у тебя -1, у Petr -1, у Dmitry_Egorov -1. Что нужно делать в такой ситуации? Правильно, такого не бывает, жюри где-то лажануло, надо идти решать другие задачи.

→ Ответить

11 лет назад, # ^ |

+19

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

→ Ответить

Petr

11 лет назад, # ^ |

+22

Я сделал так же, но жюри мне ответило "нет, у нас нет такой баги" (ну либо я его не понял), поэтому пришлось дальше баги у себя искать :(

→ Ответить

11 лет назад, # ^ |

-12

Извиняюсь, просто я был уверен, что если 3 решения верны и обсуждены, то все будет хорошо. Не все так хорошо... :(

→ Ответить

gen

11 лет назад, # ^ |

Можно было написать совершенно тупой брут, который делает то, что описано в условии (;

→ Ответить

Petr

11 лет назад, # ^ |

Ясно. Мне кажется стоит на первые несколько бревен по любой задаче смотреть глазами, благо задач всего 5 в контесте :)

Спасибо за раунд!

→ Ответить

11 лет назад, # ^ |

Учту :)

→ Ответить

EzhikOo

11 лет назад, # ^ |

+11

+100 к рейтингу:)

→ Ответить

WasylF

11 лет назад, # ^ |

а в чем у жюри ошибка была?

→ Ответить

11 лет назад, # ^ |

xx
1
1 2

Жюри считало, что ответ NO.

→ Ответить

11 лет назад, # ^ |

для длины 2 неправильно считали.

→ Ответить

sujiao

11 лет назад, # |

I spent lots of time trying to use method mentioned here to hack submission 5246996, but failed to generate the anti-hash sequence in time.

→ Ответить

Safadurimo

11 лет назад, # |

Whats wrong with my code (5256546) for 367A - Sereja and Algorithm ? I'counting 10e5 steps, but still get time limit exceeded?

→ Ответить

cup_of_tea

11 лет назад, # ^ |

← Rev. 2 →

Maybe it's because you used "cout" and "scanf". I think I have read one time that "cout and cin" and "printf and scanf" can have problems when used together...

I tried with only cin and cout, and it is accepted: http://mirror.codeforces.com/contest/367/submission/5259184

→ Ответить

sudip1401

11 лет назад, # ^ |

Actually, its because your solution is O(n^2) and not O(n) as it looks. That's because you're calling strlen(s) in the for loop, for each iteration, which is itself O(n). Call strlen once, keep its value in a variable and use it in the for loop.

→ Ответить

11 лет назад, # |

А на чем B так активно ломали? Неужели антихештест?

→ Ответить

yarrr

11 лет назад, # ^ |

+24

Егор у нас ломал, видимо, на этом:

lastIndex = i + (p — 1) * m; // overflow

if (lastIndex >= n) ...

→ Ответить

Egor

11 лет назад, # ^ |

Да, все 3 взлома таким тестом

→ Ответить

11 лет назад, # ^ |

Блин. На том же упало.

long long index = i + (p-1) * m;

Не до конца подумал, что там лонг лонги.

→ Ответить

http://pastebin.com/S4zNh4Em

11 лет назад, # ^ |

Некоторые зачем-то перемножали p и m. И иногда получался бред.

→ Ответить

fetetriste

11 лет назад, # ^ |

У меня в комнате было несколько неправильных, которые не проверяли, что q + (m - 1)·p ≤ n и из-за этого слишком часто добавляли в свою структуру элементы массива b, что приводило к TL на тестах с большими m и p.

→ Ответить

Zlobober

11 лет назад, # |

Сломал восемь решений разными тестами вида:

n, m, p = 100000, 100000, ...
print(n, m, p)
L = ' '.join(map(str, [i % 4243 + 1 for i in range(n)]))
print(L)
print(L)

где вместо ... подставляются числа 90000, 80000, 70000 и 60000, чтобы добиться разных видов переполнения выражений вида (m - 1) * p. А кто C на чём ломал?

→ Ответить

11 лет назад, # ^ |

С ломали на неправильных формулах.

→ Ответить

11 лет назад, # ^ |

У меня все взломы на неправильных формулах для минимального размера. Кажется в претестах нет содержательных четных случаев.

→ Ответить

Crab-de-KhNURE

11 лет назад, # ^ |

Девять на этом же =) n = 110000.

→ Ответить

PraveenDhinwa

11 лет назад, # |

← Rev. 3 →

I can not even imagine how author come up these ideas for problems? Sereja Can you please give us some idea about how did you think about setting about these problems, so that it might be good for upcoming setters ??

→ Ответить

Gassa

11 лет назад, # |

Если я правильно понял условие, задачу 367D - Сережа и множества мы с vysheng давали уже почти семь лет назад с ограничением m ≤ 26 (задача G). Широко известным бояном она, видимо, не стала.

Интересно, удалось ли мне её после этого сдать :) .

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

Прикольно, а как ее делать для 26?

→ Ответить

Gassa

11 лет назад, # ^ |

Так же, как недавнюю forbidden-words: векторизацией битовых операций, а основные идеи все те же.

А твоя D у меня не прошла :D . Забавно...

→ Ответить

Zlobober

11 лет назад, # ^ |

Забавно. Я в итоге свёл эту задачу к чему-то, напоминающему твою же, кстати, задачу с последнего ГП СПб (D отсюда).

→ Ответить

Nikitosh

11 лет назад, # |

← Rev. 2 →

Задача С очень похожа на А из этой интернет-олимпиады. Правда, там был цикл, а здесь массив, но это мало что меняет.

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

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

Тем более тут еще и цикл)

→ Ответить

Nikitosh

11 лет назад, # ^ |

Ну на самом деле это условие там никакой роли не играет. А ответ в той задаче был почти такой же как в этой.

→ Ответить

adamant

11 лет назад, # |

Кажется, настало время выполнять обещания =(

Кстати, кто-нибудь может сказать решение В и, по возможности, объяснить, почему следующая стратегия ведёт к ВА 3: Разобьём a на двумерный массив moduls[i][j], где moduls[i][j]=a[p*i+j], а затем отдельно рассмотрим все строки такого массива и найдём все подстроки оных, которые совпадают с b.

→ Ответить

WasylF

11 лет назад, # ^ |

← Rev. 2 →

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

UPD: и полные тесты тоже

→ Ответить

adamant

11 лет назад, # ^ |

Хм... Кажется, понял, в чём моя проблема. Я там вёл переменную кол-ва чисел-отклонений от правильного кол-ва и порой увеличивал её в некоторых неоправданных случаях.

→ Ответить

oversolver

11 лет назад, # ^ |

ВА3 — это не сортишь ответ

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

+35

ВАЗ это Жигули :)

→ Ответить

SauceCode

11 лет назад, # |

It seems that many people got tricked when solving Problem A,Div.2.I got tricked,too.Although I found it in the last few minutes,I still lost a lot of score.I think it's a good lesson for us who want to solve the easy problems as fast as possible.Nice job,Sereja.

→ Ответить

testingcode

11 лет назад, # |

← Rev. 2 →

Как решить "B" (div 2) ?

Я решил таким образом: pastebin.com/LvYPHfQm

Но у меня превышен time limit на 11 претесте.

Скажите пожалуйста, в чем у меня ошибка?

→ Ответить

Levantiy

11 лет назад, # ^ |

TL ты поймал из-за того, что для каждого запроса пересчитываешь ответ. Асимптотика решения получается O(n^2). Можно и нужно её улучшить :)

→ Ответить

testingcode

11 лет назад, # ^ |

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

→ Ответить

testingcode

11 лет назад, # ^ |

или как это делается?

→ Ответить

pitfall

11 лет назад, # ^ |

← Rev. 2 →

Нужно было предпосчитать ответ для каждого i=1..n,чтобы потом отвечать на запросы за O(1); Предпосчитать можно за линию несколькими способами.

→ Ответить

HASP

11 лет назад, # ^ |

← Rev. 4 →

Допустим, у нас есть задача, где мы должны быстро отвечать на запросы о сумме на отрезке от l до r. Возьмем наш изначальный массив и на основе него посчитаем новый массив(этот трюк называется префикс — суммы). Пусть этот массив называется sum, а изначальный массив — a. Тогда i-тый элемент в массиве sum равен сумме первых i элементов в массиве a. Обратите внимание, что массив a[] у нас в 0-индексации, а массив сумм в 1-индексации.

sum[0] = 0;

for(int i = 1; i <= n; i++) {
    sum[i] = sum[i - 1] + a[i - 1];
}

Замечательно, sum[1] = a[0], sum[2] = a[0] + a[1], sum[n] = a[0] + a[1] ... + a[n — 1]. Что это нам дает? Пусть нам поступил запрос найти сумму от l до r, тогда ответ — (сумма от 1 до r — сумма до 1 до l — 1).

result = sum[r] - sum[l - 1];

Теперь подумай, как на основе этого давать ответы на запросы, которые в задаче В.

→ Ответить

andreihh

11 лет назад, # |

Can anybody please tell me how he solved problem C div 1? I tried to count what's the minimum required N to use K different values, so I tried to find the maximum K <= M such that the found N is less than or equal to the given N and pick the largest K costs from input, but I couldn't pass pretests.

→ Ответить

dc.

11 лет назад, # ^ |

The idea is just like that ... Seems you have got the implementation wrong.

→ Ответить

andreihh

11 лет назад, # ^ |

Thank you!

→ Ответить

nghiemtucboy

11 лет назад, # ^ |

← Rev. 2 →

+10

F(K) is the minimum required N to use K different values. If k%2=1 => f[k]=k*(k-1)/2 + 1. If k%2=0 => f[k]=k*(k-1)/2 + k/2.

→ Ответить

Bidhan

11 лет назад, # ^ |

What's the proof?

→ Ответить

nghiemtucboy

11 лет назад, # ^ |

It's about Euler path in Complete Graph. There are K vertices and a edge is a condition, you want to go through all edges. If k%2=1 => k vertices with even degree. If k%2=0 => k vertices with odd degree. You can think about it that way.

→ Ответить

Bidhan

11 лет назад, # ^ |

During the contest it looked like a Chinese Postman problem in complete graph to me. In Euler Path edges can't be visited more than once, aren't we allowed to do that here (even in optimal solution) ?

→ Ответить

nghiemtucboy

11 лет назад, # ^ |

← Rev. 2 →

If k%2=1, all vertices have even degree so we can go through all edges and finish in start vertice. That's why f[k]=number of edge + 1 in this case. If k%2=0, we have k vertices with odd degree, so just add an edge between 2 vertices have odd degree, we add in total k/2 new edges. After that we can go through all edge but not finish in start vertice (be cause the last edge is the added edge and we already go through the original edge).So F[k]=total number of edge (new edges and original edges) for this case.

→ Ответить

Bidhan

11 лет назад, # ^ |

Thanks, nice explanation.

→ Ответить

11 лет назад, # |

+12

What's the source of the problem with problem div1-A? How is it even possible to have the judge solution for the first problem in the contest fail pretests? Have you tested the problemset at all?

I only saw the announcement around ~30 minutes into the contest (since the popup opens in a random open window of CodeForces, not necessarily the one you're looking at), and spent the whole time "debugging" my A. Then at the end I missed the chance to submit D by seconds :(

→ Ответить

11 лет назад, # ^ |

+32

We had 3 solutions. All of them were wrong :( Sorry for such situation.

→ Ответить

11 лет назад, # ^ |

Good thing my D TLEs anyway, I guess ;)

→ Ответить

SmartCoder

11 лет назад, # ^ |

-15

Whole time "debugging" your A ???
you submit it after 12 minute :) :)

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

Yes, and it was correct, but it got WA on pretest 3 then. 3-7 minutes later, the judge solution was corrected, but I only saw the announcement about this (and that my solution now has pretests-passed) 18 minutes later.

→ Ответить

estekan

11 лет назад, # |

+13

why are most of the nowadays contests in Sundays or in Tuesdays? I count and find that there are about five contests in this month that they were in Sunday or Tuesday. Unfortunately I have a class these days and I lost these contests. Is it fair? I wish next contest will not be in Sunday or in Tuesday. I wish ...:) (I want to write this comment before the contest but I arrive home now!)

→ Ответить

shankar556288

11 лет назад, # |

Problem B in Div 2: The question defines the sequence as "li, li + 1, ..., ln" but shouldn't this be "li, li + 1, ..., n" according to the second explanation which says "a(li), a(li + 1), ..., an" I got a WA because of this since I assumed it was "li, li+1 , ..., ln"...

→ Ответить

p-space

11 лет назад, # |

what a good contest! :D really cool, good problems

→ Ответить

UCI-Night

11 лет назад, # |

Wow, the system judged very fast today.

→ Ответить

adamant

11 лет назад, # |

Ого, обновление рейтинга просто-таки молниеносное.

→ Ответить

Nezzar

11 лет назад, # |

Integer overflow on Problem B again ARGHHHHH

→ Ответить

rng_58

11 лет назад, # |

+271

Finally 3000! :)

→ Ответить

HASP

11 лет назад, # ^ |

Congratulations!

→ Ответить

rng_58

11 лет назад, # ^ |

+20

Thank you!

→ Ответить

Xellos

11 лет назад, # ^ |

IT'S OVER 3000! (refer to my template: #define OVER9000 1234567890 :D)

Yet another CF target is born.

→ Ответить

Mukit09

11 лет назад, # ^ |

Congratulation for being second CF TARGET !!! :)

→ Ответить

Astreb

11 лет назад, # |

Как решалась C (Div2)/A (Div1)?

→ Ответить

r0p3Sw1ng3r

11 лет назад, # ^ |

Предподсчитаем количество букв (суммарное).

Далее, если r-l < 2, то ответ YES, иначе смотрим на кол-во букв на отрезке (разность предподсчета), если разница максимального и минимального больше 1, то NO, иначе YES

→ Ответить

11 лет назад, # |

Почему строка yyx это YES?

Задача С div2. Тест 3. Строка 2.

→ Ответить

gen

11 лет назад, # ^ |

Вы смотрите вывод программы, а не ответ.

→ Ответить

11 лет назад, # ^ |

Хахаха) Спасибо)

→ Ответить

pitfall

11 лет назад, # ^ |

Это у тебя нужно спросить, ответ там NO, это твое решение вывело YES

→ Ответить

11 лет назад, # ^ |

Да-да, серьёзно туплю сегодня:)

→ Ответить

Ali1377

11 лет назад, # |

What a good problem A! 7 successful hacks!

→ Ответить

witua

11 лет назад, # |

← Rev. 3 →

+46

witua: 2293 -> 2191 (-102), 278 место.

I_love_Tanya_Romanova: 2291 -> 2189 (-102), 479 место.

Как-то мне оно кажется странным. Или так должно быть?

→ Ответить

I_love_Tanya_Romanova

11 лет назад, # ^ |

+19

Похоже на искусственное ограничение. Еще пример: poopi: 2217 -> 2115 (-102), 448 место.

Но готов поспорить, что все равно формул нам никто не скажет.

→ Ответить

11 лет назад, # ^ |

+18

Мне кажется, или имеет место неправильное вычитание? ;)

→ Ответить

0Silencer

11 лет назад, # |

← Rev. 2 →

Very interesting round, waiting for the tutorial..

→ Ответить

Dixtosa

11 лет назад, # ^ |

Happy being blue : ]]

→ Ответить

Petr

11 лет назад, # |

+41

Удивлён, что раунд rated — вроде же аж 15 минут было неправильное решение жюри?..

→ Ответить

Dmitry_Egorov

11 лет назад, # ^ |

+30

К сожалению, в последнее время требования к раунду для признания его рейтинговым сильно упали. Постоянно падающий сайт, 15-минутная очередь тестирования, или, как сейчас, неправильное решение жюри одной из задач (а 15 минут — это очень много для старта контеста) уже давно перестали быть поводом для анрейта. Да и TC в последнее время этим периодически грешит.

→ Ответить

cgy4ever

11 лет назад, # |

+17

Thanks Sereja! It's a nice round: Solutions are short and clear. And the overall difficulty is not too low as I thought (Because it has some tricks in implementation, I failed 2 tasks by it.).

Maybe we can have more rounds like this, do you think so?

→ Ответить

http://mirror.codeforces.com/contest/368/submission/5266990

11 лет назад, # ^ |

+11

It is not so easy to make such rounds :) But I will try.

→ Ответить

Tintin

11 лет назад, # |

-11

In problem Sereja and Algorithm, here the constrain is "string q, which doesn't equal to either string "zyx", "xzy", "yxz". If q doesn't contain any such subsequence, terminate the algorithm, otherwise go to step 2." But when I see the testcase then I'm confused, because answer is "YES" when q contains such substring like "zyx", "xzy", "yxz". Why? My code is AC after the contest because in contest time I was confused.

→ Ответить

askhatish

11 лет назад, # |

А разбор по ссылке найден. Или это только у меня?

→ Ответить

lovelymoon

11 лет назад, # |

Div1-pB is almost as same as IIUPC 2013 pH which occured on contest of UVa Online Judge today!

→ Ответить

forthright48

11 лет назад, # |

I got AC on Sereja ans Anagrams with this code: 5261631. Yet, I am getting WA with this 5261332. This two codes are virtually same except for in one I am using

(WA) if ( good == mp.size() ) // Here mp is a map < long long, int > mp
(AC) if ( good == dif ) // Here dif = mp.size() right after inserting things in map.

The reason I am getting WA is because the size of mp changes at the end of the process. But it shouldn't since I am not inserting anything after the beginning. Can somebody explain this bizarre situation? It would suck if I ever have to face such situation during contest time!

→ Ответить

DuX

11 лет назад, # ^ |

+11

When you use map[num], it will add new element in map if num isn't already in it (example). So, if array A has some elements that B dosen't have, size of map will be changed.

→ Ответить

najim4689

11 лет назад, # ^ |

Run this code. May b this might help you. int main() { map<int,int>M; int sz=M.size(); cout << sz << " " << M.size() << endl; if(M[5]==1)cout << "i m not gonna print" << endl; sz=M.size(); cout << sz << " " << M.size() << endl; return 0; }

→ Ответить

lawliet_

11 лет назад, # |

This is my submission of Problems B. Div 2

I confused why the output of test 2 was different from it was on my computer and Ideone.com. Any body can help me ? Tks for all :)

→ Ответить

Elk-Cloner

11 лет назад, # ^ |

I test your code for test 2 it's WA your program give me 3 2 1 also it's basically seem WA can you explain your solution ?

→ Ответить

lawliet_

11 лет назад, # ^ |

For each l[i], I put a[l[i]] into a Set in C++, and the set only holds distinct numbers, so I simply print the size of this set

→ Ответить

IgorS

11 лет назад, # ^ |

In your solution you're only counting the number of different integers amongst a_{l_m}, a_{l_m - 1}, ..., a_l₁. Instead, the problem asks you to find the number of distinct numbers amongst a_{l_i}, a_{l_i + 1}, ..., a_n, for each of l_i.

On a side note, I would discourage the use of preprocessor directives like these:

#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define FRD(i, a, b) for(int i = a; i >= b; --i)

Essentially, the main goal for the majority of participants here is to improve their problem solving skills. Even if less typing saves an extra 3 minutes per match for you or me, it is somewhat unlikely to make any difference. Rather than that, it's all about learning to find the solutions for increasingly harder problems in increasingly smaller amount of time. And especially if you're only beginning to practice solving programming contests, writing a clear code (without macros) will only help you to maintain a better clarity of mind.

But that's just my own opinion. I realize some people will disagree, and at some skill level this coding "style" may become more useful.

→ Ответить