Codeforces Round #251 для участников из второго дивизиона стартует в среду 4 июня в 19:30 MSK (обычное время). Традиционно мы приглашаем на внеконкурсное соревнование участников первого дивизиона.
Раунд был подготовлен мной (PraveenDhinwa). И это первый раз, когда я выступаю в качестве автора Codeforces Round. Я очень старался сделать условия задач как можно более понятными, надеюсь, что раунд вам понравится.
Отдельное спасибо Геральду (Gerald) за помощь в подготовке соревнования. Также хочется поблагодарить Pratik Moona(pratikmoona), Varun Nitish(JuanMata) за тестирование раунда. Их помощь была неоценима! Благодарю Devendra Agrawal(devu) и Utkarsh Lath(utkarshl), они помогали мне верифицировать правильность идей в задачах. Спасибо Михаилу Мирзаянову (MikeMirzayanov) за создание этой замечательной платформы для поведения соревнований.
Задачи сегодняшнего контеста посвящаются моему дорогому другу Devu (devu). Однажды он сделал задачу с названием "Churu — вор". Churu — это мой ник-нейм. Теперь пришло время отомстить!
Распределение баллов по задачам будет стандартным: 500-1000-1500-2000-2500.
Еще одна хорошая новость состоит в том, что разбор задач будет доступен сразу после окончания контеста.
Желаю всем высокого рейтинга, удовольствия от решения задач и множество взломов!
UPD
@PraveenDhinwa I guess you are the first Indian Problem Setter (that too from my college :) ) on Codeforces (at least from the time I have joined Codeforces) .. Congrats .. Will definitely participate !!
LOL score distribution's available from the beginning :D
And editorial already written? I'm impressed!
The coders were fast too.
%50 of submissions was in first 25 minutes.
AFAIR, devu named it "Dhinwa Chor" not "Churu, the thief", which was later renamed "Dorsey Thief" before the contest.
For Non-Hindi speaker, Chor == Thief
Yes, you are right :) I forgot the actual wordings, I only remembered thief :P
I was about to change before the contest churu. Please do not take revenge .. Please :D :D
You have already verified the problem statements, So it is similar to axe one's own feet :P
BTW, here is another problem dedicated to devu. Devi ji, you are so famous.
Congrats PraveenDhinwa will surely participate :)
I hope this round problems can be described more clearly. It is important for me to start the contest and I am raring to go. :)
is devu the author (or tester) of the problem Devu Vs Police? i really liked that problem! :)
He was the author of the problem :)
Thanks :D
actually, thank you for creating such an awesome problem. it was by far the hardest i have ever worked to solve a problem since i started competing in online contests.
and as u can see from my AC solution, i used CRT and ETF (two concepts i barely knew, and had no pre-written code for), along with a few small "tricks", to solve it. was that the intended solution?
In my opinion, CRT is unnecessary — you need only fast modular exponentation and ETF.
Of course (from Euler's theorem) we know that
. So, for example, φ(10) = 4 and then
In your task you can see that (if n ≥ 2)
So you need to do only the following things:
compute k = φ(n).
find
(use the modular exponentation); let's say the result is e.
find
(again modular exponentation).
But it can happen that (a, n) ≠ 1 and so, your idea will not always work.
My idea was to factorize n and do some stuff which I forgot(and don't understand from my code) :P
Oops, true. I didn't notice the lack of the assumption :D
However, I'm almost sure the following trick works: we can write a = xy, where x contains all the prime divisors which are both in a and n (for example, if a = 2734527 and n = 233911, then x = 2734 and y = 527). We do the same for n: n = zt (in the example above, z = 2339, t = 11). Result is then
We can compute second factor as I mentioned previously (just because (y, n) = 1). What about the first one?
I hope it's understandable (and moreover, that it's true) ;)
Everything is happening quickly of this round.. :)
quick announcement, quick score distribution & quick editorial too... :)
hope, will enjoy this contest... :)
Hope Quick System Test :D
And hope quick updated rating too... :D
And hope quick AC too :) (for all participants)
updating rates is too slow :D :D
I guess the problems are going to be hackable :D
Actually all problems are hackable
ifpretest cases are weak... :)That's what I meant.
I can't wait to hack many solutions!
I could hack 9 solutions for the first time. So nice contest!
REALLY A LOT OF HACKS.
The prose in these announcements is getting better over time. Wish everybody high scores. Happy coding!
Just look these unrated registrants
I really try to be dewy-eyed and think all the 400 unrated users that register for every Div2 only contest are real...
Maybe it's kinda good because it slows rating inflation.
If I have registered but I can't participate any more will it affect my rating? Sorry for newbie question...
No, it wont.
Only if you have no any submission behavior.
Your rating wont be affected until you make a submission.
If you want to be 100% sure, you can find your nickname in the list of registrants (it may be easier if you sort the list by rating) and then use the red button to unregister ;)
Much easier — to click "Friends"! :)
no
an unrated user named smart_lovely_JuanMata is currently leading the Standings.
seems like a fake account to me, but i can't say for sure now.
I don't think so. Just look at rationality. It's his second CF round, however he leads there.
my reason for making that assumption is not because he is unrated and leading the round.
it is because of handle alone!
Nice to meet you, young boy~~~~
Oh, now i see. Sorry :)
As the round closes, I'd like to commend the round writers. Even though the contest was slightly easier (I, who usually gets only one problem, solved 3), I loved the problems and how each and every one of them were easy sounding but had something to figure out.
Thanks for my favorite problems so far!
Обожаю раунды с возможностью с лихвой поломать решения конкурентов! Thx PraveenDhinwa
Когда меня взломали, во вкладке задачи она была зеленая. И еще было бы круто чтобы в кларе был вердикт взлома.
Did anyone who solved D used Binary Search?
I solved using Ternary Search.
EDIT: Previous posting is wrong.
I solved D using Binary Search (using lower_bound and upper_bound from STL, actually).
I tried to solve with the same method but got WA on test 8.Whaat wrong with that test?
Just checking all the possible number x, such that making all elements in a is not less than x, while all elements in b is not larger than x.
Here all the possible numbers are the elements in both a[] and b[].
У меня на контесте 2 возможных расклада событий:
Я либо решаю A, B, C, не делаю взломов, а потом огорчаюсь тем, что их было так много
Или же решаю A, B, жестко туплю на C и делаю +6 взломов :D
А как взламывали на сей раз?
Вангую, на Б куча переполнений. (В условии даже сказали, мол, осторожно, long long, lol)
Только сейчас заметил эту приписку)
не могу понять, почему мне никогда в комнате не везет на вот таких вот?
B. 1 взламал на тайм-лимите, а то участник решил присоеденять по одной каждую часть предмета, два for'а. A. 2 взламал на том, что некоторые вместо >, писали >= .
Как решать D?
Я написал тернарный поиск по числу-разделителю, т.к. для конкретного разделителя необходимое число изменений вычисляется за логарифм...Посмотрим, зайдет или нет :)
Что делал при равенстве ответа на концах проверяемого отрезка?
Блин, забыл про это :( Значит, упадет.
Хм...Зашла..Наверное, потому что до отрезка длиной в 50 шел, дальше перебором по нему...Кажется, это можно поломать...
Я рассматривал отрезок длинной 3, у меня тоже зашло
При равенстве не принципиально, какой отрезок брать следующим. На ответ это не повлияет.
почему функция не может быть вида 2 2 2 2 2 1 2 ?
Will DmitriyH count how many hacks were in this round?)
Really nice contest :) I think problem D should have had a 32-bit integer overflow warning...
Any ideas for problem E?
I used inclusion-exclusion principle. And it passes the sample tests :D
I count number of bad distributions, like distributions that can be divided by 5, 7 etc. Then using IE principle I exclude 5*7 divisors etc. This works in O(Q*(2^7)). the number 7 is due to the fact that 2*3*5*7*11*13*17 is bigger than 10^5.
But I was not able to submit in time :|
There is at most ~7 prime numbers which divides n.
Tip : Solution is q * (2 ^ 7).
EDIT: i did not saw Dixtosa.
I think about the following solution but I got WA2. First of all, lets calculate how many solutions has quality n = a1 + ... + af , where ai > = 1. We can do in C(n - 1, f - 1) ways(this is well-known problem). Then if gcd(ai) = x > 1 then x|n. So try to iterate all dividers of n, and for all such x, subtract from our answer C(x - 1, f - 1). Is it correct?
Quite simple if you use Möbius inversion formula. There are much harder problems on SPOJ, as PGCD, and so on....
I think that many submissions to Problem B will fail the system test because of integer overflow, both a[] and x should be long long.
not both, only answer can be long long. We can use a[i] * 1ll * x
at least one of them should be long long, or both int but using ans += a[i] * 1LL * x;
superround, thanks for authors!
System Tests. Please
It's not as fast as the other contests!
Быстрый разбор-это очень хорошо.
in this round 251 div2...i submitted the problem Devu the dumb guy and got all pretests passed....nd got score of 680....but in few minutes i saw the status of my submitted problem as hacked....finally my score dropped to -1.....what it means...??how to prevent it>> ????
It means someone else from your room who also passed pretests and after locking his/her solution , the person went through your solution and maybe found some mistakes in your code. He then made your code go through his custom test , which your solution failed . :( To avoid this situation make sure your implementation is absolutely correct or no one is able to guess the mistake in your solution.
how to view the code of a person who s n my room?? is it posible to read the code wen the contest is goin>??
Yes , you can view the code of other person in your room after passing pretests and locking your solution . Keep in mind that you can't alter your solution after locking.
but you can't alter your solution after locking!
good tricky contest ^_^
Hey where is the editorial? It is disappeared!
I guess the formulae were not displaying correctly (the LaTex part), so they are editing the editorial :)
I think it should be accessible now :)
I really wish people would stop using the anti-quicksort test. I'll agree it's a valid hack, but it's something that shouldn't disqualify a correct algorithmic solution...
the Best and Most Secure way for problem B: #define int long long
=))
long long main()
Would that work? :D
GNU C++ :
main ( )MS C++:
void main ( )Nothing is impossible!
:D
i tried to hack ur solution 6789141 in yesterday's Testing Round because i saw u using
inteverywhere.TROLL level
long long! :Deveryone in system test
copycat! :D
This is how I solve hard problems :D
user "rationality" alone has +18 hacks!! o.O
Hello, I'd like to bring attention to the following code, it's for problem B with complexity of O(NlogN). But it got TLE, I can't find an explanation for this behaviour. My code template is rather large but it is ok, you can rest assure about that since I'm using this template for last 10+ contests. Only getInput() and solveCase() methods are relevant here.
http://codeforces.me/contest/439/submission/6799372
Even qwerty787788 got TLE with more or less same code as mine, also on the same test case. Here is submission link:
http://codeforces.me/contest/439/submission/6797936
i also got TLE for the same................. need to use objects rather than primitive now.............. http://codeforces.me/contest/439/submission/6809882
It's become popular to use an anti-quicksort test to break Java solutions. Arrays.sort() uses a variant on quick-sort that has a worst case of O(N^2) for (very) unlikely testcases. However, if they can choose them, they can make your program time-out due to sorting cost.
Use ArrayList and Collections.sort() if you want to avoid it, or just use Integer[] instead of int[].
I got the same problem! I would really like to see author commenting on this — if he crafted an anti-quicksort on purpose — I think it's a disgrace! Those kind of conducts should be prohibited!
I agree, it's quite frustrating to always remember to consider that someone may try that, but unfortunately it's a "valid" hack, so I doubt they'll fix it. Someone hacked my B and D, and I was required to resubmit both at the ~1:50 mark.
Can you show me this popular anti-quicksort test?
sorry, i finded it.... http://codeforces.me/blog/entry/2298
Oh, I didn't know that. I'll switch to object rather than using primitive data type.
Switching to objects sucks because under normal circumstances Arrays.sort() works substantially faster on primitives.
Было бы круто, если бы при онли див.2 раундах для учасников из первого дивизиона висело напоминание о регистрации. Оно вроде бы и фигня, но я так уже не первый контест провтычил =(
So many solutions of Problem C failed in system test. So spectacular...
Не видел еще контест, где там много валится на систестах)
How can I calculate my new rating?!
do nothing wait system
Problem B was really easier than problem A! Pretest 3 was ... I regret why i didn't go to solve B before A.
Why there are so many hacks on problem B? I can't find any tricky test cases :(
If you store x in int and array a in int, then despite storing answer in long long, your solution will get overflowed.
int overflow.
Also, see: http://codeforces.me/blog/entry/12518#comment-172587
Офигеть, сколько WA! А у меня вообще ошибка исполнения :)
Can someone tell me, is there any test in task C with K = 0? I found it, when i had got only five minutes left before the end of the contest, so i lost lots of points...
No, but p could be zero.
Oh, it's very sad... OK, thank you!
who can tell me why my solution of C my solution wa on 58 test
I have the same WA on test 58 (my solution is similar to yours). No idea, yet...
i've just found it XD. if p=0, i guss ur program will output a zero in the last line. u may try this data 10 10 0 1 3 5 7 9 11 13 15 17 19
winoros, thank you.
thanks for this example!
I will forget int in C++ and I will never use it again. By the way, Do you know what data type is int in C++, because I only know long long data type.
Problem C rocks!!
The most interesting contest I have ever solved! Amazing! I was really enjoying while solving problem C! Really unexpected idea! thanks authors for the contest!
Agree about the most interesting contest. I've never been so interested during systests (especially about C). But I can't imagine pleasure while solving C, it was so annoying for me.
Damn . I failed system test on problem C , just because I forgot to comment one line while Debugging .
It was surprising to find that it even passed the pretests with that terrible mistake .
It is so frustrating to see that the after that commenting that line , the code passed all the system test cases. I just missed an oppurtunity to go blue .... :(
But you are blue :)
Can anybody tell me what is wrong with my C solution. The judge says "wrong output format Extra information in the output file" in test case #58 and I can't see any problem with my solution. Thanks in advance.
I had the same problem.
check your program when p = 0
the same problem (wrong format, extra output).. :(
What the ...
Wrong answer on test 71
A corner point that I thought about that but got confused with parameteres while coding
A line was needed to accept C
6809803 -> 6811297
What a stupid mistake :(
Someone helps me. I'm really sad :'(
Don't get upset man, sometimes we all make mistakes .
Thank you man!
Both for your consolation and good problems ;)
I hope reduce these stupid mistakes
Don't worry brother .. I too made the dumbest mistake .. Forgot to comment one line while debugging .. Surprisingly it passed the pretests .. but failed system test .. 6809400
mistake : Line 97 .. comment But later after commenting that line it passed the system tests.. 6811176
Same thing happened with me @BiMokh , :( 6805185 -> 6813772 It's not new things for me, same thing happened with me many times in codeforces.**Its not a reason to be sad. Its just a warning for improvement on coding.** I think i'm a stupid coder :(
problem C
http://codeforces.me/contest/439/submission/6807018 plz explain why my code gives wrong ans . thnaks
You fail if there are no even numbers enough to fill some arrays, like in this case: 5 5 2 1 3 5 7 9
I locked my problem from dashboard and then went to standings to hack solution. But I was able to open hack window for my submitted code. When I double clicked on someone else's solution then it just showed pretest passed,etc.. Clicking on submission number didnt open the hack window. What was I doing wrong?
You should go to room instead of standings
Thanks
Failed problem D because of implicit transformation of an integer and failed C because of i failed to copy paste some validation made on the even numbers to the odd numbers... Missed the spot 45 because of two errors...
Anyways, congratulations because of the contest, well made, i understood without any trouble all statements.
There's an hour passed but there is no rating updates! Why..?
I was just going through different submissions of problem C, and came across this solution 6802980 which shows wrong answer for test case 44, but the output seems correct. Could you kindly tell how is that answer wrong?
Got it Didnt see the number of elements :P
my best contest ever, that's actually the first time i solve problem D in a contest really hats off to problem setters!.
i still wonders why a lot of participants failed in problem C?
Lots of people forgot to add some conditions, in my case, i forgot a lot of things, such as considering all odd numbers or all even numbers, etc... I failed because of failing one simple validation... So i think many people got the C wrong because of not thinking all possible cases that could be evaluated with.
Congratulations on your result :)
yes i think the hard part in the problem was about considering cases
thanks a lot :)
For problem C, I am getting following output on my machine for test #3
YES
2 7 5
2 1 2
1 3
But the judge is showing NO as output. Can anyone please help me to figure out where is the problem? Submision ID : 6809178. Thanks!
judge is showing answer "YES", but you are showing answer "NO".
Sorry I meant the same. On my machine I am getting the output I mentioned in my earlier comment on test 3 but don't know why my answer is shown as NO.
The Answer is NO too in my Machine what's the compiler you use
g++ (from mac terminal).
Rating is updated... :)
seems your wish has suited me a lot... :)
thanks for nice contest... :)
Congratulations for the round! I loved the problems because they were more idea-based than algorithm-based. Also, I liked E because I don't find as many PINEX problems as I want to usually, so thank you!
Finally , I reached DIV1 :D
Problem C : I Got "Runtime error on test 60" :( in this 6806998 . What is special about it? :'(
Check this case
2 1 0
2 1
The problem is at one of the for loops around line 40.
You calculate j % p, and this crushed when p = 0. Test 60 also has p = 0.
Silly me :( Thanks HidenoriS:)
No problem :)
there is a bug in your code
p can be 0
Thanks :)
Не заметив этой строки, попробовал 3 взлома на переполнение.
I've got RTE in problem C (test 20). I used queue with operations push and pop. After the contest, I changed queue to vector, only operation push_back, and I've got AC. Why RTE? Link to my submission: http://codeforces.me/contest/439/submission/6805127
I modified your solution, and got AC.
Basically the size of queue changes, so you should keep the original size as a variable.
Thanks! I forgot that I really had to keep the original size.
Enjoyed the contest. Specially problem C though failed on test 24.
Thank you. :)
Can one look at my submission and see what's different from PraveenDhinwa's editorial?
My submission: 6799361 Praveen's submission: 6814439
both look functionally equivalent to me but, I got WA
Never mind. I was reading in x as an int.
When I submit the solution: the status is "in queue", waste many time. Can you fix it :D
How can i delet this cm? :|
Where is DmitriyH statistics? I missed them :)