Codeforces Round #226 (Div. 2)

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

Мне вот интересно, если див 1 участвует вне конкурса, могут ли они делать взломы?

→ Ответить

riadwaw

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

Да, у них отдельные комнаты.

→ Ответить

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

круто, спасибо

→ Ответить

NVAL

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

Да, внутри своей комнаты с такими же участниками из div1

→ Ответить

worse

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

-20

I want to rating under color of my eyes... (red)

→ Ответить

Ali1377

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

+13

You say this in all contests?! :D

→ Ответить

Eran

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

+16

i think i've heard this earlier

→ Ответить

Ali1377

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

Take a look at this.

→ Ответить

caustique

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

+38

I was always curious why not just to add 2 more problems and make Div1+Div2 round instead of just Div2 one. It seems to me that the level of Div1 problems is not always very high — for example, take a look at D and E from previous round 225. They're just medium, not hard and still were not solved by a lot of contestants. I mean, one doesn't need to overestimate level of Div1 participants but it would me much cooler to have more frequent Div1 rounds.

→ Ответить

Killever

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

Big Like

→ Ответить

alohamaloha

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

Just like topcoder.

→ Ответить

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

-17

why +5 min ?

→ Ответить

knst

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

← Rev. 2 →

+26

All right, I was late, but now I'm here. Start! (just a joke) :)

→ Ответить

nikalosaberidze

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

Don't worry Lasha !!!

→ Ответить

BiMokh

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

-12

5 minutes delay?
Why!?!

→ Ответить

mory91

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

+19

maybe he forgot to write the last problem! :D

→ Ответить

ans_

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

Страсти накаляются

→ Ответить

SC_pRo_ION

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

А! О! Какой ужас! Перенесли на ПЯТЬ МИНУТ! Уписаться.

→ Ответить

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

Как решать C ? и что там за четвертый тест?

→ Ответить

htkek

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

В четвертом тесте, некоторые L и R > 10^7. Нужно учесть этот вариант.

→ Ответить

snake13

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

Как делать C без факторизации всех элементов массива? 1731 мс как бы намекают...

→ Ответить

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

-9

По всей видимости, никак.

→ Ответить

noogler

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

-8

можно. Если предпочитать для всех чисел наименьшее простое число в разложении.

→ Ответить

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

Ну подсчитали (по всей видимости, линейным решетом) и что дальше? Вероятно, как раз таки факторизовать эти числа.

→ Ответить

noogler

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

← Rev. 3 →

leastprime[i]= наименьшее простое число, вот таким образом делаем факторизацую

while (x > 1) {
   primes.push_back(leastprime[x])
   x /= leastprime[x].
}

→ Ответить

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

Это и есть факторизация.

→ Ответить

noogler

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

извиняюсь я кажется подумал что с факторизации :(

→ Ответить

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

Фрагмент кода вашей программы:

	while (x > 1) {
		int p = prime[lP[x]];
		if (ls != p) cnt[p]++;
		x /= p;
		ls = p; 
	}

Что это, если не факторизация?

→ Ответить

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

у меня такая же идея, по почему то не пашет 4 тест((

→ Ответить

caustique

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

Just calculate for each prime number of its multiples that are in the given set. The complexity will be N / 2 + N / 3 + N / 5 + N / 7 + ... = O(NlogN) where N is a maximum possible number (10⁷).

→ Ответить

caustique

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

+24

Я не знаю, что на меня нашло, но я ответил по-английски, хотя знаю русский:)

→ Ответить

enot110

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

+35

На самом деле, там чуть лучше асимптотика ;)

$\text{[math]}$

→ Ответить

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

← Rev. 2 →

вот http://mirror.codeforces.com/contest/385/submission/5787970

→ Ответить

ELKIN_

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

Solution for B with n^2 complexity passed my hacking test :'(

→ Ответить

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

← Rev. 2 →

+13

B is supposed to be solved in $\text{[math]}$ . ofcourse it will pass the hack!!

→ Ответить

logic_max

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

+23

There is an O(N) solution also.

→ Ответить

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

can u plz share the idea with us?

→ Ответить

logic_max

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

For each occurrence of "bear", you have to count the number of valid indices to the left of this, and to the right. It will contribute countLeft*countRight number of tuples. For each "bear", left count will be the number of characters from 'b' of previous "bear" to this 'b'.Right count will be number of characters from this 'r' to the end of string.

You can check my submission(5788550) for details.

→ Ответить

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

← Rev. 3 →

thanks a lot! :)

EDIT: i wonder how your $\text{[math]}$ submission and my $\text{[math]}$ submission (5791720) both pass with a time of 78 ms :D

→ Ответить

alv-r-

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

I got TLE at first with O(n²), then got AC with O(n) :(

→ Ответить

Metamorphus

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

← Rev. 2 →

Man, just a piece of advice for you. On Codeforces if you wanna hack somebody on time limit, you gotta be sure, that his/her program will perform at least 10^9 operations on your test. Because the servers are really fast. On this contest I tried to hack a program, which performed in the worst case about 4*10^8 operations, but the result was just 1668 ms.

→ Ответить

omse1998

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

Из-за лагов на последних секундах не смог перепослать задачу :/

→ Ответить

BiMokh

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

Couldnt submit my code in last 20 seconds :-@
Again loss of rating :-(

→ Ответить

jibon_ebong_shomoy

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

at last minute codeforces was unavailable, So I couldn't submit my soln.Did someonne else have this problem?

→ Ответить

MohammadFatafta

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

Yeah same thing happened here!!!

→ Ответить

adelnobel

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

Couldn't submit a problem in the last two minutes because of constantly getting the message "Codeforces is temporary unavailable "

I really hate this!!!

→ Ответить

jibon_ebong_shomoy

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

Me too -_- .. spent 1.5 hours for 1 problem , couldn't submit it.. what a joke ..

→ Ответить

kojak_

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

I complained about this. Answer: "No comments"

→ Ответить

kuruma

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

Hello,

I need guidance on problem B.

Can it be solved by suffix array?

I thought of using suffix array + lcp to get all substrings only containing bear and count those.. Maybe even suffix tree was better choice but couldnt implement it yet.. was that the way to go?

→ Ответить

ELKIN_

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

nope, solution is very simple. For each "bear" count positions on left from which we can start, it will be (i — prev 'bear' position), because we shouldnt use the positions already used by previous bear and positions on right on which we can end, it will be = n — i — 3. then increment ans to rightcount*leftcount, and change last bear index.

sorry for bad explanation. if you disunderstand then look to others code

→ Ответить

Mostafa_36a2

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

← Rev. 5 →

I've BruteForced it , and it passed

Edit : TLE in testcase 9

→ Ответить

AU.Bahosain

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

Codeforces is temporary unavailable :(:( It cost me hack in the last minute :(

→ Ответить

princeladdak

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

Whats the idea of problem C ,i got TLE.

→ Ответить

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

you need to use sieve of Eratosthenes in liner time

→ Ответить

Mediocrity

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

+14

I got AC with simple sieve of Eratosthenes.

→ Ответить

http://mirror.codeforces.com/contest/385/hacks/91276/test

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

+27

I liked problems very much,exceptionally problem C,thanks CleRIC for great contest ;)

→ Ответить

PraveenDhinwa

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

I wasted 10 minutes to write a generator. It only gives the error that first line should not be empty.

Can anybody help me why is this happening ??

→ Ответить

vintage_Vlad_Makeev

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

+34

Спасибо Вам! Отличный раунд!

→ Ответить

PraveenDhinwa

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

For problem D constraint n <= 20 suggested that something like bitmask dp could be done. But I can not find any reason why not to use just all the flash lights instead of a subset of them ?

→ Ответить

kingofnumbers

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

Not sure but I think this is because the order of lights matters.

→ Ответить

PraveenDhinwa

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

← Rev. 2 →

I got the idea, infact it is true that all the lights can be used. But the bitmask can be used to extend intermediate result dp (mask) to dp (newmask) easily using geometric manipulations.

→ Ответить

Uni

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

+36

My hack #91170 was marked as unsuccessful. But the details contains "Time: 2152" and this problem (Problem C) has 2 seconds time limit. Doesn't 2152 > 2000?

→ Ответить

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

← Rev. 2 →

in the last two contests, i saw problems with time limit of 2 seconds, and submissions that took 2011 ms got accepted.

wait 2-3 mins, i will post the links.

EDIT: sorry for the delay, but finally found them! 5722902 5706257

→ Ответить

MikeMirzayanov

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

+12

I'll handle it. Already has found the issue. Thanks.

→ Ответить

numa

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

← Rev. 2 →

There may be something wrong.
I found a successful submission for problem C which takes 2245ms to execute. 5796553
And I hacked a code which causes TLE, according to verdict, it ran 2000ms.

To keep contests fair, this problem should be deeply discussed.

→ Ответить

Ali1377

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

What a "runtime error" contest!

→ Ответить

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

How solve problem E?

→ Ответить

Andrei1998

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

What was the idea behind D? (n<=20 sugests that the problem is NP for bigger values of n). Was is something like meet in the middle?

→ Ответить

oml1111

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

More like travelling salesman dp. For every subset of lamps store the farthest point that can be reached using them. When adding a lamp to a subset it is easy to see, how much it extends the reach.

→ Ответить

pbtbbo597

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

I just solved D, the dp[] size is (1<<n), than every step only turn on one unused light and update dp[cur|(1<<k)] (k is the unused light)

→ Ответить

tinybells

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

For the first time, my rating is going to go above 1500 (hopefully) :)

→ Ответить

karthikabinav

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

Any idea why http://mirror.codeforces.com/contest/385/submission/5798194 gives a run time error. But uncommenting the commented lines doesnt give. I cant see what fails.

→ Ответить

p-space

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

← Rev. 4 →

yes, i have the same mistake, the thingis that s.size() is an unsigned int... and when it is 1 and substract 3, it is 4294967294, because all the expresion is indeed unsigned int, and then when you access to the element 4294967294 of the string it give you RE, because it only has 1 element.

→ Ответить

karthikabinav

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

ohh interesting. yeah this makes sense. thanks !

→ Ответить

mohamednabil00000

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

I think there is nothing wrong on your code. but the compiler make infinte loop but I don't know why.

→ Ответить

ghooo

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

← Rev. 3 →

because s.length() is unsigned int

and by negating 3 from it, it will give another unsigned int, so

s.length()-3

will be some non-negative number

→ Ответить

Kianoosh

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

← Rev. 13 →

+97

Rank 2:SquirrelDetected Registered: 4 hours ago(Before Contest)
Rank 3:MahooshojoNHB Registered: 7 weeks ago(Before Contest)
Rank 4:Dong5k Registered: 4 hours ago(Before Contest)
Rank 6:Uni Registered: 4 hours ago(Before Contest)
Rank 7:FastYes Registered: 3 hours ago(Before Contest)
Rank 9:akatsukiLH Registered: 9 hours ago(Before Contest)
The NEW brains...!

→ Ответить

KiAsaGibona

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

Can Someone Explain problem E in details (i.e : How the matrix was built?? )

// So far I go...
   |  1 0 1 0 1 0 |     | sx |
   |  0 1 0 1 1 0 |     | sy |
   |  1 1 1 0 1 0 |  *  | dx | 
   |  1 1 0 1 1 0 |     | dy |
   |  0 0 0 0 1 1 |     | M  |   M= Number of moves so far
   |  0 0 0 0 0 1 |     | 1  |   1= Constant term to increase M

→ Ответить

adelnobel

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

Well, instead of the first 4 zeros in the last column, they all should be 2. I got a WA during the contest because of this stupid bug. Note that you need to decrease sX, sY by one to turn the coordinates to 0-index instead of 1-indexed to make it easier, consequently, you will need to add 2 to K in each step.

→ Ответить

KiAsaGibona

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

Why they first 4 zeros need to be 2 ? What is the logic behind this?? I don't understand.. And when sX or sY is greeter than N we need to mod them by N ... how to apply mod N operation in matrix multiplication?

→ Ответить

adelnobel

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

← Rev. 2 →

Well, we will be working with 0-indexed coordinates, ok? Now, dx is updated as follows dx = dx + sx + sy

But since we are working with 0-indexed coordinates then this should be dx = dx + sx + sy Why? Assume sx == 1 && sy == 3 in 1-indexed mode, now when we turn it to 0-indexed then we have sx == 0 && sy == 2, so dx should equal sx + sy + 2

Now for modding by N part, you can mod every thing by N in every step of your calculations, because the only operations you do are addition and multiplication, and the mod can be distributed over these operations normally

→ Ответить

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

-10

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

→ Ответить

enot110

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

+25

писать стресс!!!)

→ Ответить