Codeforces Round #236

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

wish all participants a very happy Holi :)

→ Ответить

somag

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

+41

your first both divisions contest after many Div2 contests :)

→ Ответить

Mobin_Teymoori

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

← Rev. 4 →

-43

I wish it will be a good contest as always !!

→ Ответить

PAP

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

+37

:|
Everything is funny for the first time!

→ Ответить

Emettant

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

-14

Что может больше поднимать настроение, чем вечерний контест в этот воскресный день :)

→ Ответить

EG0R

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

+27

новость про то, что завтра не нужно идти на пары;)

→ Ответить

Sunar

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

-8

Кому то завтра не нужно идти на пары))) это поднимает настроение)

→ Ответить

nic11

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

Как же поднимает, если ты идешь, а кто-то нет?

→ Ответить

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

+13

Это в некоторых узких кругах называется "умение радоваться за других" ;)

→ Ответить

SC_pRo_ION

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

← Rev. 2 →

-16

Плохая шутка :)

→ Ответить

Monick

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

+61

Since next Div.1 contest is on March 22, this contest is "Good Bye 1392" contest for Iranian Div.1 contestants. Nowruz 1393 is on March 20 so Div.2 contestants have one more contest in 1392 :) Happy Nowruz

→ Ответить

worse

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

-26

Лагаааать сегодня будет....

→ Ответить

Tehnar

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

+10

Не, с такими задачами не будет

→ Ответить

aladdin3

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

I guess, first time DIV2 contest takes a contest-id less than the corresponding DIV1.

→ Ответить

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

true that. it maybe because of the statement of the last contest's problem B

→ Ответить

HolyInq

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

Пойду-ка я лучше тимус порешаю...

→ Ответить

DmitriyH

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

DIV1-B: Правильно ли я понимаю, что ограничения выставлены таким образом, чтобы не прошло по времени разложение числа на множители простым пробеганием по 2..sqrt(a[i]) ?
Не успел подобрать максимальное простое число, укладывающееся в ограничения, чтобы опробовать на взломе, но предполагаю, что тест из a = maxPrimes должен много решений свалить.

→ Ответить

gridnevvvit

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

Нет. Нужно делать разложение за корень

→ Ответить

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

← Rev. 2 →

6035948

Разложение за корень с оптимизацией для того, чтобы повторно не ходить по чётным. TLE 43. ЧЯДНТ? Оо

UPD: #define int long long подвёл. Сам себе злой буратино :\

→ Ответить

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

тебе опыта не хватает

→ Ответить

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

+12

Ты просто мне завидуешь

→ Ответить

dalex

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

← Rev. 3 →

-6

Правильно понимаешь, у меня это только что упало и отбросило на 200 мест.

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

Лол, а еще вот такая подстава:

for (int i = 2; ll(i)*i <= xx; i++) — TL

for (int i = 2; i*i <= xx; i++) — AC

Если уж это валить, то надо валить оба варианта.

→ Ответить

DmitriyH

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

На мой взгляд, если не требовать решето, то это будет A.
Так — хоть какой-то подвох к тривиальной идее.

→ Ответить

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

А в чём прикол давать такие задачи как А, в которых главное — распарсить условие и не полениться написать два фора?)

→ Ответить

kraskevich

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

← Rev. 2 →

Самое интересно, что с небольшой константной оптимизацией не решето на C++ заходит в дорешке.

→ Ответить

Vaness

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

И без оптимизаций все заходит.

→ Ответить

kraskevich

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

Ну на контесте у меня был TL43.

→ Ответить

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

Да нет, вроде как заходит — 6033105. Как написать разложение за корень принципиально иначе, я не знаю.

→ Ответить

dalex

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

← Rev. 2 →

Ну я в своем сообщении написал как :) Надо конечно фиолетовым для этого быть — сейчас стану.

Кстати у тебя 935 мс — такое на контесте вполне могло не зайти. ~~Известно же что решения во время систестов в среднем работают слегка медленнее чем в дорешке.~~ А, это с контеста сабмит. Ну все равно еле-еле уложилось в ТЛ.

→ Ответить

bayleef

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

6032405 — ещё умноженное на логарифм из-за сета.

→ Ответить

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

+17

Ну, мне и в голову не могло прийти, что такое может не заходить. Я даже не запускал на макстесте. Почему-то всегда был уверен, что мы успеваем факторизовать около 10-20 тысяч чисел порядка 10^9 за секунду.

→ Ответить

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

Объясните мне, в чем вообще проблема, и почему оно у вас всех так долго работает.

Я вроде бы написал обычную факторизацию за корень, без решета для простых, без прыжков по нечетным, 6056074, и оно 30 мс работает.

→ Ответить

Silentium

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

А зачем в первом for приведение типа?

→ Ответить

dalex

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

При таких ограничениях оно не нужно. Я один раз пофейлился на такой фигне и начал везде перестраховываться. В результате пофейлился еще раз.

→ Ответить

cgy4ever

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

+46

The overall feeling is that tasks are tend to be a bit artificial, especially B.

And for E, I can't understand the statement.

Thank you gridnevvvit! I believe your next round will be better. :)

→ Ответить

flashmt

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

I feel that problem C just came out of nowhere...

→ Ответить

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

It was horrible Adiv2, but this is the first contest when I'm not sure in my B,C ideas at all) Smth new for me, thanks.

→ Ответить

DanAlex

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

← Rev. 2 →

What is the solution for C ?

→ Ответить

klamathix

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

+51

Is it just me or sometimes constraints on Codeforces are unnecessarily tight? For example today, I resubmitted B because I thought 5000 * sqrt(10 ^ 9) modulo operations won't pass in 1 second. Some time ago I got TLE for 5000 * 5000 in 2 seconds, although that was the expected complexity. Just because I also had 5000 * 5000 memory. Well today, after resubmitting I tried to hack such a solution and it fit into the limit, in something like 0.95.

So why make n = 5000 when you want n ^ 2? Why make n = 5000 today? The only way in which 5000 instead of 1000 (for example) affects the contest is that some sloppy implementations may TLE and others may not, depending on some non-algorithmic issues (cache breaking, input/output speed, speed of used operations, etc).

This was a good contest, congrats to the authors. They're not the target of this post, I'm just saying that generally we could avoid such issues if we just stick to reasonable limits, which don't cause doubts about TLE, be it for submitting or hacking.

→ Ответить

ikbal

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

Actually there is a faster way then sqrt(10^9)...

→ Ответить

jonathanpaulson

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

What is the faster way?

→ Ответить

flashmt

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

It's probably O(number of primes < sqrt(10^9))? (if we don't count Pollard's Rho algorithm here)

→ Ответить

Swistakk

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

← Rev. 2 →

sqrt(10^9) — something finite

number of primes — infinite

(numbers of primes < sqrt(10^9)) = 0

O(0) is pretty fast :P.

Btw pi(n) = O(n / ln n), where pi(n) if of course number of primes numbers less than n.

→ Ответить

klamathix

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

Well I know there's a faster way, do you think I resubmitted the same thing? But the optimization brings 0 additional value to the problem. So why think about if it's necessary or not? Why guess if it's needed or not when hacking?

→ Ответить

ikbal

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

You are using map which is red-black tree. Any number x has not got more then one prime divisor bigger then sqrt(x).

→ Ответить

sweetsc

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

Agreed. 5000 * sqrt(10 ^ 9) failed. That makes me frustrated.

→ Ответить

Nakochi

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

I think precalculate the prime that smaller than sqrt(1000000000) would be better. You can do it in O(n) time. That won't cause a Tle.

→ Ответить

Nicolas16

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

I've tried to hack a solution with 2 * 5000 * sqrt(10^9) operations and his solution took 0.998s... (I don't know how it is even possible to do more than 300,000,000 operations in less than 1s). As you say, I think it should have been n <= 1000 if this kind of solution was considered as OK or n <= 10000 if not. Nevermind, goodbye red :D

→ Ответить

niklasb

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

← Rev. 2 →

Totally depends on the operations. 3e8 array indices would probably be too slow, but if everything fits into the registers, you can get close to 2e9 cycles per second or so (= frequency of your processor).

→ Ответить

fushar

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

+11

My accepted D1-A solution is as follows:

For each step, create edge (u, v) with the smallest deg[u]^2 + deg[v]^2.

It does not care about p, 2n + p, nor 2k + p. What is the intended solution, then?

→ Ответить

klamathix

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

If you solve p = 0 then you can add any p edges and the solution will be ok. To solve p = 0 you can make a cycle out of N — 1 nodes, tie the N-th one to them and add 2 more edges somewhere. There are other ways, of course.

→ Ответить

afrizal

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

I didnt really understand the problem and just generate the pattern for C div2...

and got AC :v

→ Ответить

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

look at this solution for the same problem :P

→ Ответить

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

-22

fuuuu, pascal

→ Ответить

Emettant

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

tourist usually code in Pascal. That is not make any problem to him to be the first

→ Ответить

yermak0v

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

And what?

→ Ответить

jonathanpaulson

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

← Rev. 2 →

The condition is equivalent to saying that removing any vertex should delete at least two edges. So if for every vertex you can pick 2 edges touching it (each edge can be picked by at most 1 vertex), you're ok.

I just connected i to (i+1)%n and (i+2)%n, and added p random additional edges.

→ Ответить

NotImplemented

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

I was creating edge for min(degree[i]+degree[j]).

→ Ответить

rhyme

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

I simply "distributed" 2*n+p edges in the manner hinted in sample solution

1-2,2-3,3-4,4-5 .....,1-3,2-4,3-5,4-6 ....,1-4,2-5,3-7 ...

till the count becomes 2*n + p .. didnt care for the subgraph conditions

→ Ответить

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

← Rev. 2 →

I was reducing the code written in 3 minutes (deleting vectors,pairs), until it became my solution)

        int cn; cin >> cn;
	for(int ci = 0; ci < cn; ci++) {
		int n,p; cin >> n >> p;
		int cnt = 0;
		for(int k = 2; k <= n; k++) 
			for(int i = 1; i < k && ( cnt < (2*k + p) ) ; i++)
				cout << i << " " << k << "\n", ++cnt;	
	}

→ Ответить

6031777 6031879
6041332 6041177

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

+22

Кажется, кто-то должен быть наказан.

→ Ответить

DmitriyH

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

Комната #1, обращение к тем, у кого A была заблокирована: удивлен, что мой бред никто не взломал.

    for (size_t i = 0; i < n; i++)
        SetEdge(links, i, (i + 1) % n);

    for (size_t i = 0; i < n; i++)
        SetEdge(links, i, (i + 2) % n);

    for (size_t i = 0; i < p; i++)
        SetEdge(links, i, (i + n / 2) % n);

→ Ответить

Alhantro

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

← Rev. 2 →

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

Жаль пришло это решение после 3х реджектов=(

→ Ответить

Astreb

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

А как её решать?

→ Ответить

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

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

→ Ответить

Astreb

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

Ну более-менее понятно.Спасибо.

→ Ответить

Kianoosh

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

Another Tricky Contest but there could be a lot more hacking attemps!

→ Ответить

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

Почему в С работает Флойд?

→ Ответить

Lelby

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

А он работает? :(

→ Ответить

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

6034764 — не знаю, работает ли, но авторские тесты проходит.

→ Ответить

http://mirror.codeforces.com/contest/402/submission/6035354 http://mirror.codeforces.com/contest/402/submission/6035395

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

-12

ну ты пушкин

→ Ответить

SC_pRo_ION

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

← Rev. 2 →

+28

Great!

→ Ответить

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

← Rev. 3 →

+17

i dont know whats the funniest of the following:

user thinks that adding comments makes it difficult for others to see that solutions are similar
the two handles are FakeErdem2 and kalimm (also very similar)
they both submitted within 30 seconds of each other
the "fake" account submitted before the "real" one

→ Ответить

doomsfear

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

The last point is just to not affect rating if the pretests failed .

→ Ответить

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

Adding comments makes it difficult for system to skip the solution automatically.

→ Ответить

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

oh. so ur saying that if two exactly identical solutions are submitted, system skips the second one automatically?
i dont think this should happen. what if both codes are copied from some old blog post or any other public site?

→ Ответить

Nicolas16

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

They actually have cheated in this way during the contests 225, 226, 227, 234 and 235, so this means that their strategy is not this bad...

→ Ответить

Nodir.Daminov

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

Sooo when will ratings be updated ???

→ Ответить

sikander_nsit

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

updated.

→ Ответить

kien_coi_1997

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

+31

Time limit in problem B is too strict. I've got TLE and got AC (after contest) by a small optimization. I think that either TL must be adjusted to 2s-3s or biggest test (test with biggest run time) should be in pretests.

→ Ответить

abhinav92003

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

same happened to my code..

→ Ответить

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

+71

Давно ли при нажатии на кнопку "положение" открывается страница с моими результатами, а не первая страница? Это довольно неудобно: вроде бы основной юзкейс таблицы результатов — открыть топ-20 и посмотреть, что и за сколько сдают топы. Теперь это делать чуть неудобнее.

→ Ответить

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

+27

В прошлом матче уже точно было.

А вообще у каждого свои юзкейсы — кому-то, например, интересно посмотреть, есть ли выгода от взлома. Или сколько мест он потерял из-за минуса.

Чтобы все были довольны — надо для этой фичи галочку в настройках сделать.

→ Ответить

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

Минимум с 228. Ещё тогда писал об этом. Действительно неудобно.

→ Ответить

jigglypuff

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

+82

Ты аккуратнее, так и Bredor призвать можно.

→ Ответить

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

А я и приврал, ко всему прочему. Фича эта с Рокетона. Полез в посылки смотреть дату последнего контеста, ибо она тогда появилась, и не учёл, что данные за февраль были утеряны.

→ Ответить

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

Ты никогда не опоздаешь туда, где тебя ждут

→ Ответить

MikeMirzayanov

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

+11

Видимо баг какой-то, исправим.

→ Ответить

abhinav92003

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

← Rev. 3 →

Time limit for D : Upgrading Array was too strict.. I got TLE but when I changed some variables from long long int to int, my code got Accepted..

→ Ответить

abhinav92003

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

Time limit for D: Upgrading Array was too strict.. I got TLE but when I changed some variables from long long int to int, my code got Acceepted..

→ Ответить

Lazzaro

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

← Rev. 2 →

What's wrong in my solution of Pro.B Div2? Anyone can help? Submission:6037256

→ Ответить

afrizal

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

← Rev. 2 →

So complicated way. Why dont you just find the first element of the corresponding element of array and count it? And the constraint is so small only about 1000 first element was able to counted.

If there are some element had been in the right order in sequence for a first element most, so its the most probable sequence. Then find differences with corresponding element in array. Just it

Here my solution : 6037944

→ Ответить

Lazzaro

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

Thanks.

→ Ответить

RetiredAmrMahmoud

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

Putting an advanced topic in a C problem even it's a direct one wasn't a smart idea i think !

→ Ответить

ivplay

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

← Rev. 2 →

Whats wrong with my idea, can anybody tell me? I have confusion with "//*******************" marked lines. http://pastebin.com/vi446T5f

Div2 D,div1 B

→ Ответить

TsunamiNoLetGo

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

Actually it is quite funny mistake :D In those two lines

V[j]/=gcd(V[j],Div[i]);
Div[j]/=gcd(Div[j],Div[i]);

the iteration at which j==i (the first iteration of the loop) ... the value of Div[i] becomes 1 ... So it is not the correct value for the rest of iterations when j<i

Here is a link of accepted solution after fixing Submisson

→ Ответить

Xellos

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

I seriously can't understand E. If the edge (x, y) is of different colour than (p, q), then x and y lie in a different tree than p and q, so condition 2 is impossible. No?

→ Ответить

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

+15

Результаты вывесили так даже KADR на фотке повеселее выглядеть стал

→ Ответить

Rubanenko

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

I guess vepifanov placed the second, not the third.

→ Ответить

gridnevvvit

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

Thanks, fixed.

→ Ответить

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

← Rev. 2 →

waiting eagerly for Round Statistics which DmitriyH usually posts!

EDIT: its now available here, and i got my wish of my name being published! :)

→ Ответить

fillets

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

I am stuck on 402D/403B. I tried several approached but I keep getting TLE. I think I am missing something here. Can someone please have a look :
Using Sieve factorization (TLE at #18) : http://mirror.codeforces.com/contest/402/submission/6050051
Using Normal factorization (TLE at #42) : http://mirror.codeforces.com/contest/402/submission/6046374

→ Ответить

pllk

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

Just add this line to your first solution and it becomes fast:

for(int p : primes) {
    if (p*p > v) break; // <- add this line
    int cnt = 0;

I tested it here: http://mirror.codeforces.com/contest/402/submission/6050585

→ Ответить

fillets

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

Thanks a lot pllk !

→ Ответить

vlfom

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

Задача А Div2 сложнее А Div1..

→ Ответить

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

+11

Нет.

→ Ответить

worfzyq

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

I want to know the problem C why the tree can't have the height of 0

→ Ответить

p-space

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

hi, someone can explain solution for problem E div2/C div1?

→ Ответить

worfzyq

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

Just for the strongly connected components A^k means The path length between two points for K

→ Ответить

EROR

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

← Rev. 2 →

Nice One for Div 2. Thank you for arranging that. Hope You will arrange some more next time. Plz post the tutorial.

→ Ответить

zeosutt

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

There were many chances to hack, but I couldn't do at all =(

→ Ответить

surendrasingh9426

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

why i am not able to register for this round??

→ Ответить