Всем привет!
Сегодня в 19.30 по московскому времени состоится Codeforces Round #319, который настоятельно не рекомендуется кому-либо пропускать.
Автор раунда — я, меня зовут Дима Горбунов, и это мой первый раунд на Codeforces. Я очень надеюсь, что вам понравится раунд, и каждый найдет себе задачу по вкусу. Для того, чтобы увеличить вероятность этого события, пожалуйста, прочтите все задачи этого контеста.
Как всегда, благодарю Zlobober за неоценимую помощь при подготовке контеста и утонченный юмор, sankear за написание перекрестных решений, Delinur за перевод условий на английский язык и MikeMirzayanov за потрясающие системы Codeforces и Polygon.
У вас будет два часа на то, чтобы решить 5 задач. Успехов!
UPD. Разбалловка в первом дивизионе — 500-1250-1250-2000-2750.
Во втором — 500-1250-1500-2250-2250.
UPD2. Из-за тестов большого размера по некоторым задачам, системное тестирование будет идти медленно (возможно, займёт несколько часов). Благодарим за терпение!
UPD3. Разбор можно найти по ссылке.
UPD4. Winners!
Div1:
1). Marcin_smu
2). mnbvmar
Div2:
1). latisel
2). wrong_order
3). ntitry826
Отдельный респект al13n за правильное решение задачи Div1.E во время контеста!
Trinity Contest
Registered with bells on :)
the man in your pic look very depressed.make me crie evrytiem ;_;
He is a well-known poet in Egypt.. called Ahmed Shawky :)
Anyway this pic is much more better and possitive=)
If it can be postponed for 24 hours, that will much better. Friday is not weekend. Go to school or go to work prevent us from getting up late, even though we participate in Codeforces Contest in the evening.
Please do NOT postpone it.
Of course it won't be postponed. I just complain about the time for me~ However, I am curious for the reason why you disagree with postpone?
What about the fact that after moving it 24 hours forward it will clash with TC SRM?
Oh......What a busy weekend!
I want to start doing TopCoder, but its awful interface discourages me as soon as I open the site. And its applet isn't that good too.
You shouldn't worry about interface, but rather the problems. In general, topcoder problems have better english and more clear explanations, and the challenge phase is a rather interesting element.
Do u know any tutorial about playing Topcoder? I have tried several times but still dunno how to start.
Have you tried reading the official guide? It is a bit outdated but still conveys the idea.
Oh I have mentally prepared myself for this evening. :P
for me and a lot of contestants Friday is weekend :)
Why? Don't you need to go to school or work on Friday?
In Egypt our weekend is (Friday & Saturday) not (Saturday & Sunday) :)
In Muslim countries weekend is Friday
Usually I tend to miss lectures that has CF rounds conflicting with them.
It certainly feels different and the rush is better :D
Thank you for contest, I think in this contest will be interesting and a lot of hacks. Sorry for my poor english
Why do you think that there will be a lot of hacks?
I like hacks , they save u getting system test failed.
I didn't say that I don't like hacks. I just wonder why he is in this thought..
this contest had more system test failed than hacks.. :(
Will the problems be sorted in an ascending order of difficulty?
the statement in the post: "In order to increase the probability of finding that task, please read all of the problem statements" means alot
I think it doesn't, since "that task" refers to "everyone will find a satisfying problem". The question wasn't if the problems will be sorted in ascending order of satisfying-ness.
weekend or not weekend ,i hope contest will be running.
Because it is div2 round and it will happen after a long time.
Thanks for this holding this CF round and hope everyone can get good score!
I hope the problems will be short and to the point. Not with long stories.
But I hope The problems will be short and the point. Not with long stories.
But I hope the problems will be short and intersting, Not with direct statement "please calculate something"
Wish me positive contribution :P
looking forward for your first set of problems :D
Hope that more contests will be scheduled at 11:00 instead of 11:30
Time to lose red!
who know maybe time to get new max :)
Do you have any pointers on how to get out of green zone?
Increase your rating to 1500+ :D
Or probably decrease it to 1200- :D
No thanks EKGMA :p
If you are heavily color-blind like me then you already look red!
you have to solve at least A and B to stay at the blue zone.
Along with those, solve C and your chances to be purple are pretty high.
I hate A,B. And I suck at C,D. Its a viscious trap.
You did it :D Congrats.
Thanks! It feels good to see the progress as a color change.
Yay, I was right! :(
Hah, it seems we rise and fall together. If only C had 3-4 seconds instead of 2...
I hope you never again use c++ streams, your C passes in under 1 second using printf...
http://codeforces.net/contest/576/submission/12963316
NOOOOOOOOO
Or time to lose bottom yellow, after this revolution. :P
hope understand from first time read :3
Did you notice that registration finishes as time contest starts not 5mins before...
P.S No That was an error I think? When I looked both times were same..
Not anymore =(
это только у меня CF начиная примерно с часа, после начала контеста жутко лагал?
У меня все было ОК
У меня лагал только в самом конце. Учитывая что 10 минут добавили, лагало точно не у тебя одного.
я, просто, писал этот коммент, думая, что соревнование завершилось :)
Thanks to author!
contest was great
,how to solve "Modulo Sum"?
I used set, but might TLE. Saved all possible modulo remainders for each element, basically.
That's not enough. You need to combine each remainder with each remainder to get new remainders.
Yeah that's what I did. Instead of iterating over a 10^3 array, I used set, that's all. But sets have a huge constant associated with them, which is what is making me nervous.
And you can also combine the remainder with itself certain number of times. I cannot view the solutions yet, but I'd like to see how you solved that.
"And you can also combine the remainder with itself certain number of times." why?
For example,
3 3
1 1 1
There was given sample test
6 6
5 5 5 5 5 5
So obviously, he must have considered that.
Actually, you can't sum one number more than once, the only strange thing was that after n, the subsecuence could continue in 1, but without repeating any number.
its actually coin-change. treat the remainders as the coin that you have, how many numbers can you make. check through these numbers to see which are divisible by m. and you are done.
NO, is not like that, because is a subsecuence, not a subset, a subsecuence is of continuous numbers.
It didn't have to be a contagious subsequence. One of the examples had a non-contagious solution:
Yes, but I thought It could be circular, so, after the final 3, continues the first one.
contagious=transferrable, like diseases contiguous=one after another
At least that is what I thought, but now I see my answer received a WA in the 39 tests
I think there's no way it's impossible if N >= M. My not-very-rigorous-but-you-get-it proof:
Imagine you're doing a simple dynamic programming solution, with the elements sorted in ascending order first. If a number's multiples "circled back" all the way to 0 (this might mean going around the modulo space several times), we're done. So assume that didn't happen yet. If we can prove this means we'll always get at least one possible new modulo value when adding each number, it's proven. So take a new number X. There are 3 possibilities:
i found this during the contest http://math.stackexchange.com/questions/699857/proof-subsequence-of-n-integers-is-divisible-by-n
if you understand the proof please explain it here in plain english. thanks.
this is a different problem. for this subsequence, it doesnt have to be contiguous, whereas the link that you have shown seems to talk about subsequence in contiguous form.
But if there is a contiguous subsequence, then there definitely is a not necessarily contiguous one. I fail to see how this is not relevant.
Appears I was right, yay! :D Anyway, what I posted above is a plain English proof of this statement. But I guess the one given on Math SE is simpler, so I'll explain that one as well:
Let's assume M == N. I'll only use N in the proof.
Let's define the series R_1, R_2 .. R_n like this: R_k is the remainder of the sum of the first k elements, that is, (a_1 + a_2 + .. + a_k) % N.
If for some k we have R_k == 0, take that subsequence and we're done.
Otherwise, there are N numbers in the R series. They can have N-1 possible values (since none of them was 0). This means there are two equal numbers in R, so there are two prefix sums in the original series whose remainder by N is the same. Let's say R_i == R_j, and i < j.
This means that adding a_(i+1), a_(i+2), ... and a_j to R_i didn't change its remainder by N. So the subsequence a_(i+1) + a_(i+2) + ... + a_j has a remainder of 0 by N.
This also showed that there must be a CONTAGIOUS subsequence that satisfies this.
EDIT: ffao managed to explain this proof much simpler than I did, look at his explanation if you don't get it :)
The (easier, I guess?) rigorous proof:
Let the sum of the first i elements modulo m be S[i]. There are m different possible values of S[i]. If we find S[i] such that S[i] = 0, we're done. So suppose none of them is zero. By the pigeonhole principle, at least two of S[1], S[2], ..., S[m] must be equal, say S[x] = S[y]. But then a[x+1] + ... + a[y] = S[y] — S[x] is divisible by m!
So it's always possible if n >= m.
Thanks GrandMaster ffao
For the case of n < m, can i add dummy values of 0 so that n >= m and then argue that if we can't find S[x] and S[y] then it was not possible with the initial sequence ?
Adding dummy values of 0 is not a valid modification as it changes the answer to the problem. That happens because you can always select your newly added 0 as the divisible by m subsequence, which will make it always possible.
What is happening? Why the contest is still running when everybody stopped and there was even a window with information that coding phase has finished?
I haven't seen any notification about extending the round and a lot of people too. Was it a bug or there was no notification at all?
Nevertheless, I think that the submissions after the original time should not count...
The system gone to total gc on 1:23 :( We are working to reduce memory consumption and prevent such situations.
We increased contest duration while backed was restarting. Unfortunately, we were unable to send notifications.
Right now our highest priority task to fix it. Sorry to inconvenience.
No problem, I understand, but I was a bit surprised. Thanks for quick reaction!
People had started discussing the problems too.
Was the round extended? Cause I did'nt get any notifications.
Seriously, no adding minutes for the round? And system is not available last 5 minutes of contest.
Господа, продлевать контест после того, как все увидели плашку — это ппц!
Что такое плашка?
Are you going to cancel submits after 2:00?
Btw. I lost 5-6 minutes not knowing that round goes on. And I found a bug 10 seconds after the final end. I hope it wouldn't get AC — http://ideone.com/6DVME8
Well, at least your contest went without any problems :)
clarification: I'm not ranting. More like crying or something :D
;_;
Продлевать контест вот так вот, без оповещения — не дело. Я-таки мог за потерянные 2,5 минуты запихать C-шку.
У меня прикольнее было. Минут за 15 до конца контеста понял условие в В, начал писать, тысячу раз набажил, пока ловил баги — хром вывел сообщение "контест закончен". Я, расстроенный, сижу, дебужу не спеша. Нашел ошибки, думаю послать в дорешку. Пытаюсь открыть архив, вылезает надпись "администратор заблокировал архив". Вхожу в контест(счастье, что в этот момент не очень сильно лагало) и вижу, что контест продлили еще на 10 минут. Вставляю решение, отсылаю за 36 секунд до конца. В это время залагало, и уже после завершения контеста пришла надпись "претесты пройдены". Теперь сижу, жду систестов)
Прошла). Если не считать того, что я читать не умею, то нормально)
Я хотел написать такое решение на D(Div2) но конечно не успел: Если есть x такое что p^2[x]=x и для всех остальных чисел p^k[y]=y тогда и только тогда когда k четное, тогда ответ YES и все связаны с x либо p[x]. Иначе NO. Это правда?
Есть еще случай когда вершина связана с самой собой. В этом случае ответ yes потому что все вершины можно к ней привязать.
Ок, неважно, я тупанул :(
Раз есть ребро 4-6, то должно быть 1-5. Итого не дерево.
Вроде у вас в этом тесте 2 4 6 будут в цикле.
Кажется твой ответ неправильный например не хватает ребра (6, 1) т.к. есть ребро (5, 6).
Нет ребра 5-1. Вершина 4 может быть связана с вершиной 6 только если p[4] = 5 связана с p[6] = 1
А что если существует x, что p[x] = x. Тогда ее вроде можно с остальными соединить и все ок.
I hacked 2 C-div1 problems with carefully written cases to solutions close to what I believe is the correct answer (somehow partitioning the space in chunks of size 1000xsth and move around them properly).
However, if they are partitioning them in chunks of something different but close to 1000, my test cases probably won't work because their structure is completely messed up,since they are meant against partitions of 1000 (could have been 1001, nothing special in 1000).
Can you come up with a way of creating a challenge that doesn't assume a particular number with which partitioning space? There should exist some of those in system testing, but I cannot come up with them.
PS: the system test probably didn't have them because one of the programs I hacked got accepted just by changing the partition number from 1000 to 1500.
When editorial will be available?
Задача B(Div.2) — O(N*M) ?
Да
Но, помоему 10^9 — это работает больше чем 2 сек.
да, но вообще, как я понимаю, максимальное кол-во операций порядка 10^6(тк, почти всегда(может быть вообще всегда),если n>=m, то ответ да, следовательно достаточно дойти до n = m, а m <= 1000)
Я делал с структурой bitset, которая работает на константу быстрее простого перебора по остаткам
map пройдет?
Map и bitset совершенно разные структуры, так что не понимаю вопроса
Можешь объяснить свое решение див2 Б? Оно смотрится намного интереснее, чем то, что в разборе.
Стандартная динамика dp[j] — можем ли мы получить остаток j, используя первые i элементов. (Измерение по i не нужно) Вместо обычного массива для dp используем bitset размера 2 * m. Bitset поддерживает все битовые операции. Храним единички на местах, где мы можем получить остаток j. При добавлении нового элемента, если мы можем получить какой-то остаток j, то записываем, что мы можем получить остаток j + a[i] % m. Если делать это с помощью bitset, то это выглядит так: a |= a << (a[i] % m). Где-то j + a[i] % m могло получиться >= m, в таком случае нужно сделать так, что если (m + k)-ый элемент равен 1, то k-ый элемент тоже должен быть равен 1.(т.к (m + k) % m = k): a |= a >> m;
Потом ставим 1 на место a[i] % m: a.set(a[i] % m); Ответ YES, если на нулевой позиции стоит 1(можем получить остаток 0), иначе NO
Bitset — это конкретная структура, в С++ есть такой библиотека . С помощи этим можно любую битовые операции.
When will editorial be available?
The connection problems were unfortunate, but I really liked the problems, great job! B was especially interesting.
For C div2, My solution is to print all prime and perfect square numbers that are less than or equal 'n'.
Why is it wrong ??
8
you must also print 3, 4,5... powers, that less or equal n
for each prime, you print prime^i if this is <=n.
How solve problem C div1 ?
Wow , do we have a new dreamoon_love_AA : .o. ?
The problems are awesome. Hard to believe none of them had been used before. =)
Why do you call B and C awesome? Some arguments? B is 'write two if-s', C is 'think of the correct partition', both are boring and non-interesting for me.
Well, B ends up somewhat involved while being really simply stated (also I tend to like problems somehow connected to graph isomorphism =)), and C has a constructive flavour which is always nice. The 'think of the correct partition' is for sure more creative than 'implement the segment tree for the bazillionth bloody time'.
I agree that such original problems are the best. Like misof said, "The less it resembles anything I've seen before, the better!"
It is because you are too good For beginner, like me :'( , they are too interesting
Lol, I'm yellow forever
The idea of E is old though. For some reason it's still not very overused, I've only seen it maybe four times.
Can you provide some links? malcolm and sankear invented this idea while solving some completely different problem (having nothing common with this kind of semi-online dynamic connectivity) in a pretty complicated but elegant manner.
http://se.math.spbu.ru/SE/diploma/2012/s/Kopeliovich_diploma.pdf
(for the dynamic connectivity; the DSU with flags is new to me and was a nice touch)
Of course the dynamic-connectivity-offline itself is well-known thing, we do not pretend on inventing it. What I asked you is idea that while traversing the tree of divide-and-conquer we can still modify information in the future in a manner similar to segment tree. Did you see such approach before?
BTW, DSU with flags (as I understand you mean a data structure for adding edges and checking if the graph is bipartite) is described on e-maxx.
Oh, ok, I guess that's new. Sorry, haven't thought about it as a separate idea. Probably because in the implementation I'm used to it's a straightforward modification.
How to solve Div1-D?
Div 2 D anyone??
Div 2.D == Div 1.B
please make testcase so as to fail all n*m solutions mine n*m failed while this HURTS
That solution is not n*m. That solution is min(n*m, m*m). (The loop will always break after at most m iterations, for reasons discussed above).
In other words, that solution is correct.
Anybody who solved C(Div 1) as follows. Divide into 1000 blocks with 10^6x1000 rectangles. in each rectangle sort points by (x[i]+y[i]), I think it can be proven that will give 2n \sqrt(n) bound.
No, you can create a test giving 3E9 if you don't alternate the sort order.
It seems that it works if each block is 1414x10^6.
Why there wasn't any announcement for the extra 10 minutes!!
I tried to submit solution 2 minutes before contest end and I could not do it. 15 seconds before end I could submit, but I was not fast enough. I waited 2-3 minutes to see if contest is extended, but it was not. The only good think is that my solution would be incorrect anyway as I checked.
Div 2. A. What is a worst test case time complexity for this solution? 12930538.
It seems to be that the worst case for that solution is a n = 10⁵ and x = Highly composite number below 10⁹. It may be something like divisors(x) * n. On a quick analysis it seems that x has more or less 10³ divisors. So, the result should be 10⁸.
LoL, why this solution gives TLE:12934189? Is it because of using vectors?
No, because you did O(n*m). Beign n <= 10⁶ and m <= 10³ you have a 10⁹ solution. That's slow.
You are dividing 1E9 times but divisions are expensive so you can't make a lot more than 1E8 of them per second.
But my solution is O(m^2)( I consider case when n>m).
Ah sorry, I think the problem is that you are reading a million ints using cin, c++ streams are often too slow for such huge input.
that would be really sad as i also seem to have O(m**2) but i am reading data with cin :(.I also think this should have been covered in pretests
cin is fine; just add this magical command:
See here.
Magical command helps a lot, but anyway cin is much slower then scanf, even with command.
Ironically, I've had my first experience with that just now.
But it is fairly rare. Still, I'll use scanf from now on.
Do you ever clear xp? I think xp might be getting really big near the final iterations...
Oh, thanks. I think that was actual problem:)
Ugh, I only had a bit less than one hour for the contest. To be precise, I'm travelling and the only place where I could do the contest was one train/bus station (next to each other). But the train station's net hotspot didn't work and the bus station only has a 3rd party connection with 1 hour free, then nothing. So I hurried a lot and I think I'm going to fail both B and C.
Why couldn't the round be 2 hours earlier... I could've done it at home then...
UPD: yes, I failed both B and C.
Why didn't you leave this one for virtual contest if you were travelling?
Because it'd be yet another one. Most CF contests have had awful dates for me recently (which means the last few months, because there have been so few). When I'm home, there's nothing, then I leave somewhere without net for a few days and a CF contest is guaranteed.
So, you prefer losing ratings than not enjoying a contest. That is very inspiring Xellos :)
2s * 617sols * 50tests ~ 900 min testing (task C)
Where am I wrong?
Ok, I can't into parallel calculations and good solutions which work fast (or fail early), but it still slows testing, thank you for the limits
Am I the only one who mistakenly read the constraint in problem C as 2.5·108 instead of 25·108? The common agreement about scientific representation of real numbers is to use normalized notation and according to it the constraint in problem C should've been 2.5·109.
You are not alone)
And our solutions is very similar. We both tryed to solve it O(n*logn), TL.
At first I also misread it, but the points (1000*i, 1000*j) with 1 <= i,j <= 1000 are such that the shortest Hamiltonian path has length ~10^9
In fact it was possible to understand that you understood something wrong by noticing that for the 1000x1000 uniform lattice (all points of form (1000a, 1000b)) the answer has order of 10^9.
Nevertheless, you are right, writing 2.5 * 10^9 could've been much better.
UPD: oh, Nicolas16 said the same thing before me.
Well, the statement said "it's guaranteed that the answer always exists for given input" so I didn't worry too much about that :)
Yeah but then there would have been input where the minimal length is exactly 2.5 * 10^8, which means that we would have had to find the exact minimal path in this particular case (which did not seem to be the the goal of the problem).
However, I had to remark all these things during the contests and I lost some time before understanding I misread the bound, so I am not saying you are wrong :-)
I thought it was a trick to obscure the desired complexity. 2.5·109 looks pretty much like
while 25·108 is «what the wierd constant is it?!»
I really thought of it as a nice beautiful obfuscation, no irony here.
Too scared to look at my submissions page.
congrats you passed all three you attempted:)
Honestly, I would not have opened the page at all. Thanks for telling me :)
После конца контеста понял, что в C было манхэттенское расстояние(а не евклидово ;c)
Разве это меняет решение?
Да, кажется, вы правы
Опять не подумал прежде чем запостить :c
UPD: однако ж все равно подгорает :/
Those permutation problems are cool
What is special at test 9 from div1B? I looked at my source 10 times bbefore submitting it to be sure I don't miss anything. I've even hacked some sources=)))
Isn't this going to miss node 1 if it is not either nod1 or nod2?
Yes, it does...stupidest bug ever.Thanks.I don't know why I pressed 2
I might be the happiest blue coder to-be ever!!!! Should be out of green right??!!!!
seems likely all the best !
Thanks!! :)
"and it's strongly disadvised to skip it."
Nice trap
12936106 12937847 . по моему одиннаковые посылки
Look, the green coder latisel is the winner of a Div2 contest!, oh wait look at his previous contest here.
Worse than worse . Unbelievable!
some red seems to be having FUN!
I guess he did so because he was "only" second. That's crazy how people think they will become "famous" by winning a Div 2 contest...
Alone man who won div2 and became famous was just sorry_dreamoon.
I passed D with "bad" solution
:) Only optimization is order of for loop in matrix multiplication — I remember reading somewhere that you can make naive multiplication cache-friendly by switching order of for loops from i, j, k to i, k, j. And after that, all that's left is a trivial if statement that checks a[i][k] isn't 0 before multiplying it with the for loop with j.
I thought about submitting that, but I was pretty sure it wouldn't pass... Guess I shouldn't underestimate the CF servers after all :)
Looks like that is the wanted complexity... Makes me think D is a pretty bad problem now, is it just "submit the obvious solution and hope that it passes"?
There is a typo in editorial I think. It should be "it's not enough", not "now enough". So /32 was intended.
Yeah, it's definitely a mistake, thank you.
I think I have the same solution (12942073), but it got WA44 and I can't find the bug now...
Edit: You didn't clear "nextcur".
Oh, really, AC now. Thank you!
вот такие они, зелёные победители:
for DIV2 B: can any one find whats wrong with this submission: http://codeforces.net/contest/577/submission/12944993
What is this?
after putting number into buckets within %m.....
I am iterating over each bucket for count of #'s in it...this loop is for that....
Thanks for your reply...
I can understand if this goes on and gives TLE but i want to know why WA....
Hi....thanks again for looking into my code....it turns out just a shift of loops here and there and it got AC.
here is the submission: http://codeforces.net/contest/577/submission/12963454
Ясно с этим раундом, претесты проводят простой перебор на B, который за nm, но не проходит на полных тестах а дело то всё в том, что если мы находим ответ YES, то нужно просто выйти, если продолжать до конца(O(nm)), то будет TL
На самом деле если N >= M, то сразу можно выводить YES, а иначе O(N*M) не так уж много. Это можно доказать, но мне лень, но могу привести задачу с Тимуса, решив которую за О(N), вы поймёте примерное доказательство.
P.S. Знал бы ты, сколько я заведомо ТЛьных решений упихивал только за счет того, что когда мы нашли ответ, то стоит его просто вывести. Собственно, изначально ту задачу с Тимуса я решил, упихав O(N*N).
why does the use of pow function from math library give a WA while without that its AC... Ans 1 : with pow func http://codeforces.net/contest/577/submission/12941362 Ans 2 : without pow func http://codeforces.net/contest/577/submission/12947283
Its happening with me too!!!!!
codeforces is giving me this output for test case_ 7_**** 19 32 16 8 4 27 9 24 2 3 5 7 11 13 17 19 23 29 31 37
but my system is giving this output! 19 32 16 8 4 27 9 25 2 3 5 7 11 13 17 19 23 29 31 37
for me its test case 4... cf : n=15 -> 9 2 3 4 5 7 8 9 11 12 ideone : n=15 -> 9 2 3 4 5 7 8 9 11 13
Pow uses floating point values and you round them down when you convert them to ints. It should pass if you add an epsilon.
Try using powl()
al13n got 90 tests on problem E, but Endagorion got TL on 96 test, wtf?
We are already investigating this.
Fixed. That was not a judgement error, but only an error of verdict page showing information not for all testcases.
hi.. i think that there is something wrong with codeforces compiler this code gives wrong answer on test4 problem C http://codeforces.net/contest/577/submission/12937746 i tried the same input with the same code on my computer and on ideone (http://ideone.com/hIQ3BM) and it gave the right answer.. could any one pleas tell me what is going on?!!
You can't trust the pow function since it uses floating point arithmetics.
Thanks JohStraat..but i can't really understand ..is using pow function causes undefined behavior?? ..so what do you suggest instead using pow function in general?
as suggested by dushyant use powl or make your own pow it will be a short function
Кто-нибудь может объяснить почему в задаче "B. Сумма по модулю"
при параметрах 2 47 1 0
правильный ответ YES Я не понимаю как из чисел 1 и 0 можно сделать число которое делится по модулю на 47.
Спасибо!
эм, 0 на все делится
Div1 C checker is awesome!)
Deja Vu it seems ,Sir :)
I was thinking about this too when I saw the final standing. LOL
I didnt became div1, but I am too close. I hope at future to be :) Thank you for the great contest!
Finally got into Div. 1 ..
Thanks pretests...
2496501499 in C, seems legit :D
With 999 endings instead of 500 in 44th test it would go up to ~2990*10^6, buckets should be sorted to avoid that. Solution of Marcin_smu looks hackable too.
This is really bad in cf. TLE with cin and AC with scanf for div2 B. These are the solution links 12935258 12951554
My rating also went down. It could have gone up
First know how cin works vs how scanf works before blaming codeforces.
its good thing your rating went down.
Yes I know that but this almost never happens on codeforces. There are cases when 10^9 complexity solutions are also accepted
And part of competitive programming is knowing when it is and when it isn't.
Never a nice thing to say :P
Объясните пж, кому не лень, что за мэджик-ускорение в авторском решении С (div1)?) Попытался сам написать аналогичное авторскому решение за nlogn; оно пашет, но ТЛится на тесте с 10^6 вершин по непонятным мне причинам...
cin/scanf?
cin, ускорения scanf хватает?!!!
Если в задаче нужно считать или вывести более миллиона чисел, то стоит сразу позабыть о cin/cout. Разница по времени может быть в несколько раз (помню один раз в 6 раз разница была).