Всем привет!
Скоро, 24 января в 19:30 MSK, состоится очередной Codeforces Round #226 для участников Div. 2. Как обычно, Div. 1 участники смогут поучаствовать в этом раунде вне конкурса.
Задачи были подготовленны группой авторов в составе — Алексей Чесноков (CleRIC), Кирилл Бутин (KirillB) и Иван Попович (NVAL). Это наш первый раунд на Codeforces и мы надеемся, что все пройдет хорошо.
Вам предстоит помочь герою задач — обычному медведю.
Благодарим Gerald, Delinur, Aksenov239 за помощь в подготовке соревнования и MikeMirzayanov за систему.
Разбалловка стандартная: 500-1000-1500-2000-2500.
Удачи!
UPD: Раунд перенесен на 5 минут позже.
UPD: Разбор задач
UPD: Надеемся, что раунд вам понравился.
Поздравляем победителей:
November 29th?? When you click the link, it shows the correct time.
Thanks:)
Fianally a new contest author for Div 2! Sounds good...
I think this is contes — very simple contest ! :)
New contest author, I am look forward this contest :D
It feels so good to be div1 and participate at these contests....It's so relaxing....
It is so relaxing to be a div1 and participate at Div.2 Friday evening...Thanks for the round!
good luck and have fun.
hope all get positive ratings :)
Only div2...But It doesn't matter.Just enjoy this contest!
Finally can join a contest without any pressure...
whats meant by "Div. 1 participants can take part out of the competition"?
it means that they can compete but it will be unofficial for them
so these div1 participants wont be given rankings along with the div2 participants, right?
yep
Мне вот интересно, если див 1 участвует вне конкурса, могут ли они делать взломы?
Да, у них отдельные комнаты.
круто, спасибо
Да, внутри своей комнаты с такими же участниками из div1
I want to rating under color of my eyes... (red)
You say this in all contests?! :D
i think i've heard this earlier
Take a look at this.
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.
Big Like
Just like topcoder.
why +5 min ?
All right, I was late, but now I'm here. Start! (just a joke) :)
Don't worry Lasha !!!
5 minutes delay?
Why!?!
maybe he forgot to write the last problem! :D
Страсти накаляются
А! О! Какой ужас! Перенесли на ПЯТЬ МИНУТ! Уписаться.
Как решать C ? и что там за четвертый тест?
В четвертом тесте, некоторые L и R > 10^7. Нужно учесть этот вариант.
Как делать C без факторизации всех элементов массива? 1731 мс как бы намекают...
По всей видимости, никак.
можно. Если предпочитать для всех чисел наименьшее простое число в разложении.
Ну подсчитали (по всей видимости, линейным решетом) и что дальше? Вероятно, как раз таки факторизовать эти числа.
leastprime[i]= наименьшее простое число, вот таким образом делаем факторизацую
Это и есть факторизация.
извиняюсь я кажется подумал что с факторизации :(
Фрагмент кода вашей программы:
Что это, если не факторизация?
у меня такая же идея, по почему то не пашет 4 тест((
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 (107).
Я не знаю, что на меня нашло, но я ответил по-английски, хотя знаю русский:)
На самом деле, там чуть лучше асимптотика ;)
вот http://mirror.codeforces.com/contest/385/submission/5787970
Solution for B with n^2 complexity passed my hacking test :'(
B is supposed to be solved in
. ofcourse it will pass the hack!!
There is an O(N) solution also.
can u plz share the idea with us?
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.
thanks a lot! :)
EDIT: i wonder how your
submission and my 
submission (5791720) both pass with a time of
78 ms:DI got TLE at first with O(n²), then got AC with O(n) :(
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.
Из-за лагов на последних секундах не смог перепослать задачу :/
Couldnt submit my code in last 20 seconds :-@
Again loss of rating :-(
at last minute codeforces was unavailable, So I couldn't submit my soln.Did someonne else have this problem?
Yeah same thing happened here!!!
Couldn't submit a problem in the last two minutes because of constantly getting the message "Codeforces is temporary unavailable "
I really hate this!!!
Me too -_- .. spent 1.5 hours for 1 problem , couldn't submit it.. what a joke ..
I complained about this. Answer: "No comments"
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?
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
I've BruteForced it , and it passed
Edit : TLE in testcase 9
Codeforces is temporary unavailable :(:( It cost me hack in the last minute :(
Whats the idea of problem C ,i got TLE.
you need to use sieve of Eratosthenes in liner time
I got AC with simple sieve of Eratosthenes.
I liked problems very much,exceptionally problem C,thanks CleRIC for great contest ;)
I wasted 10 minutes to write a generator. It only gives the error that first line should not be empty.
http://mirror.codeforces.com/contest/385/hacks/91276/test
Can anybody help me why is this happening ??
Спасибо Вам! Отличный раунд!
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 ?
Not sure but I think this is because the order of lights matters.
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.
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?
in the last two contests, i saw problems with time limit of
2 seconds, and submissions that took2011 msgot accepted.wait 2-3 mins, i will post the links.
EDIT: sorry for the delay, but finally found them! 5722902 5706257
I'll handle it. Already has found the issue. Thanks.
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.
What a "runtime error" contest!
How solve problem E?
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?
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.
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)
For the first time, my rating is going to go above 1500 (hopefully) :)
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.
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.
ohh interesting. yeah this makes sense. thanks !
I think there is nothing wrong on your code. but the compiler make infinte loop but I don't know why.
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
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...!
Can Someone Explain problem E in details (i.e : How the matrix was built?? )
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.
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?
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
MikeMirzayanov, пожалуйста, добавте возможность скачивать тесты или каким-то другим образом просматривать весь тест, ибо уже не первый раз по началу теста невозможно определить как он выглядит, почему решение валится и что делать((
писать стресс!!!)
на сколько я понимаю, стрес тест — какой-то большой тест, который мы генерируем случайным или почти случайным образом. И все что я из него могу получить проходит ли время и нет ли слишком странных ответов типа отрицательных или очень больших.
где я ошибся?))
Часто, если решение получает WA, то можно действовать по следующей схеме:
Пишется генератор небольших тестов (достаточно небольших, чтобы и на них могло не заработать, и было не так сложно отдебагать)
Пишется простое решение, которое точно будет работать (пусть и долго на больших тестах).
Запускается батник, который по циклу (сгенерировать тест) → (прогнать оба решения) → (сверить ответы) не найдет тест, на котором основное решение не будет работать :)
http://mirror.codeforces.com/contest/385/submission/5789899 http://mirror.codeforces.com/contest/385/submission/5798663
Мегафейл, который стоил 1000+ мест
А у меня слетела, потому что не проверял случай, когда слова "bear" вообще нет. И как-то странно, что в претестах не было случая, где нет "bear". В дорешку сдал.
My solution of problem C fails on pretest 7. I just used a BIT with sieve of Eratosthenes. I can't find the mistake. Could someone help me find it? Thanks.
just skimmed.. i guess you should run another loop inside this loop for multiples of i when notp[i]=false
for(;i<mx;i++) if(!notp[i]) update(i,cnt[i]);Didn't notice that. Thanx.
In recent contest, there are Div1 users that register a new account to participate officially!!
Why? What's the difference?
Then Div2 users should compete with some Div1 users, too!
where can i find test file for a particular case that my solution fails
Can anyone tell me why the first code got runtime error while the second got accepted ??? 1. http://mirror.codeforces.com/contest/385/submission/5791451 2. http://mirror.codeforces.com/contest/385/submission/5798703
s.size() returns an unsigned number. And the trick of unsigned numbers that if it overflows, or goes negative, it takes by modulo 2 ^ 32 (int) or 2 ^ 64 (long long). So, if the length of the string is less than 3, it takes by modulo and becomes something lika 2 ^ 32 — l. Just output s.size() — 3 and you will see yourself.
http://mirror.codeforces.com/contest/385/submission/5789899 http://mirror.codeforces.com/contest/385/submission/5798663
I have this error too. it is because, str.size() — 3 in for — it is size_t type
try to
cout << s.size() - 3;whens = "a";!s.size()isunsigned intand(unsigned int - int) -> unsigned int! it cant be negative!thnx a lot M.Mahdi, i see this issue before but couldn't understand the reason :)
Kept getting Runtime error on 385B - Bear and Strings Spent much time to figure out it..
just use
i+1<v.size()instead ofi<v.size()-1Хороший контест, задачи интересно решать
Your first contest very good held.Thanks for this interesting contest :) CleRIC KirillB NVAL...!!!
Your first contest very good held.Thanks for this interesting contest :) CleRIC KirillB NVAL...!!!
The problem D is about Greedy and Geometry? I have no idea about it! Who can help me ?Thanks.
Bitmasks,DP,Geometry
I think it's useless to me. . . .
Thx for contest, it was my first contest that i get +rating) thx a lot)
CleRIC did a great job for his first time as contest writer, the problems were full of quality