Привет, codeforces!
Рад пригласить вас на рейтинговый раунд #493, который состоится в Jul/01/2018 17:05 (Moscow time).
Авторы раунда — Ильдар 300iq Гайнуллин, Григорий vintage_Vlad_Makeev Резников, Михаил MikeMirzayanov Мирзаянов, и я, cdkrot.
Большое спасибо Shiqing cyand1317 Lyu, Андрею GreenGrape Райскому, Ивану isaf27 Сафонову, Алексею Aleks5d Упирвицкому за тестирование раунда. Михаилу MikeMirzayanov Мирзаянову и Николаю KAN Калинину за помощь с подготовкой раунда.
А также Михаилу MikeMirzayanov Мирзаянову за системы codeforces и polygon.
Как обычно, в раунде будет 5 задач на 2 часа. Надеюсь, что вам понравятся задачи, и желаю удачи!
Разбаловка будет опубликована незадолго перед раундом.
UPD: Разбаловка выглядит следующим образом:
Div1: 500 1250 1500 2500 3000
Div2: 500 1000 1250 2000 2500
Возможно, вы также хотите обратить внимание на этот пост со стримом-обсуждением после контеста.
UPD2: Опубликован разбор
UPD3: Поздравляем победителей!
Div1:
Div2:
Пересекается с матчем Сраптак М — Авангард (Курск)
Wow you've mentioned mike three times.
Then Mike declares this round is triple-rated
Holy Trinity of codeforces
because "Mike WiLL Made It"
Почему было не провести раунд на 2 часа позже, чтобы все успели насладиться игрой лучшей сборной мира, а потом и задачи порешать?
Испания — лучшая сборная мира? Очень спорно, были на этом турике команды и получше.
Да, еще есть Бразильцы, Французы.. и пара команд, не имеющих шансов на титул.
P.S.: сейчас бы минусовать за футбольные предпочтения на сайте по олимпиадному программированию
При чем тут Испания?
Раунд начнётся на 5 минут позже, чем игра. Видимо, организаторы соревнования считают, что через эти 5 минут всё итак будет понятно и можно будет спокойно идти писать КФ.
Если бы перенесли раунд на два часа, то мы бы не увидели самое интересное
Кто же знал, что все так пойдет?
Are we allowed to code in Q#?
we are allowed to code in C# :p
5 problems in both divisions?
5 problems per division, 7 in total, 3 shared.
I love it when codeforces community downvote for no reason at all.
Me too XD
You are god _/_
Cool, we get to see 5 minutes of Spain-Russia.
Unusual time for World Cup. :'(
Have to solve all problems within 55 minutes to watch second up fully. :P
Finally Green GreenGrape!
I see what you have done with HTML ( ͡° ͜ʖ ͡°)
The dream comes true!
Actually there are also purple grape that matches your rating
My solution for Problem 1000A -Codehorses T-shirts
https://coolforces.blogspot.com/2018/06/1000a-codeforces-codehorses-t-shirts-solution.html
1000B — Light it up
https://coolforces.blogspot.com/2018/06/1000b-codeforces-light-it-up-solution.html
Can you tell us, why do we need this information on page related to completely different round?
I posted it here by mistake..I meant to post it in its round page,but i made a terrible mistake,sorry for that.
hope this contest has a lot of hacking stuff...:)
Upvote if you think the main characters of this contest should be Messi and Ronaldo.
Hey mate! I totally agree with you.
I want Mourinho and Guardiola
GreenGrape не ученик. Он кандидат в мастера и активный пользователь Codeforces.
Три контеста за 2018? не очень-то и активный
456, 461, 471? :3
c:
Hope the statement be as short as the announcement XD.
icpc_expert said the same and got a ton of downvotes,...
It's a cruel world, isn't it? :D
Auto comment: topic has been updated by cdkrot (previous revision, new revision, compare).
Is It Rated?
Hope the statements is as short as the blog.
remember, I'll hack you!
Many Russians and spanish won't participate in this round..#world_cup
?detaR tI sI
I would like to know from the community that is it fair that a re-submission which has the passed pretest should be considered for deducting points in a contest?
I had submitted one solution which i didn't think would pass the pretests so i re submitted with minor change before the result of first one but both the submissions passed the pretests, so i would like to know WHY or WHY NOT points should be deducted for the second correct re submission?
Because there are system tests and only your second submission will be considered for system test.
I m sry but i didnt get ur answer's relevance to my question and nor the point why only second one would be considered for the system testing?
Btw do u mean my second submission or second solution which has passed pretests?
The only situation when you actually have to resubmit is when you find a bug in your code after passing pretests. It's fair that you lose some points in this case since you didn't solve the problem correctly.
In your case you were taking a conscious risk when resubmitting, since you hadn't seen the verdict yet for your previous submission.
Fair answer
But then why should the first solution that has passes the pretest be skipped? what if that solution had passed the main test cases...? why shouldn't i been given points according to that?
cause there would be lots of such solutions, which CF would have needed to test, and that would take a lot of time.
Because then sometimes I would submit 5 different solutions to a problem hoping that one of them passes systest.
Whats the problem in that?
U may deduct point for that during contest for multiple solution
but if ur first ans is correct one out of those 5 then why shouldn't u be given points according to that? The system testing then can skip the rest of them.....
Here's another problem specific to CF. Some people can troll by intentionally making holes in their solutions and make a bunch of pretests passes, then other people would benefit a lot from just hacking their solutions.
Ya that can be difficult issue to deal with....
I think that's it...
Thank you all for your time
MathForces
Is it ridiculous to have two counting problems in one round?
3 in a row
Not the kind of problems that I hoped for
I finished A~D all within 31ms and 12KB...What a strange contest!
omg just don't tell me that this actually solves div1B/div2D
You only have to use the first 11 elements. I mean:
It is correct, see editorial (coming soon) for proofs.
I hope not, because I did that but got WA on pretest 9 :(
RIP forgot to cast to a long
Me too. I used %d instead of %lld and got WA. FML
int is too small
I have #define int long long
How did you get this equation?
I found this by looking at the brute force and finding pattern
I watch at it and didn't find anything for about 1.5 hour.....
Look at difference of f[i+1] and f[i] for first 30 numbers for example and you'll easily see the pattern.
What is the brute force for this ??
Something like:
Deleted
can you explain this in some simpler words? what are we trying to do here
We just enumerate every possible combination of I, V, X, and L, and count the number of numbers we can represent.
Can you tell your approach? Did you know from the beginning that a pattern should be found out?
I wasted about 30 minutes trying differences and things on OEIS. Then I just said "wtf" and input 100 to my brute force and I was surprised at how small it was. Then I tried incrementing by 1 and noticed that each time it was always 49 increase. So I got to this solution
I found that LIIIII && XXXXXV represents same number so, we need to subtract all the numbers containing them and then a got a weird recurrence relation but did not got the idea of find a pattern.
На чем ломали A?
Многие писали что-то в духе
cout << min(cnt * y, (cnt - 1) * x + y);(cnt — количество блоков из нулей)Соответственно, на тесте, где cnt = 0 и x > y, такое решение выведет отрицательное число.
Why are there 2 combinatorics problems in this round, and why can B be solved with brute force observations?
Because combinatorics is fun. Isn't combinatorics a very wide notion that can capture majority of CP problems?
1908 solved C, 344 solved D
The problems were not measured correctly
cheating ??
Stecher
div2E/div1C was a hard one, IMO...
could somebody give a hint on its solution, please?
Use inclusion-exclusion principle.
how do you reduce it to O(n) though? When I tried inclusion-exclusion I had to do cases on # of equal columns and # of equal rows which is O(n^2)..
(for example when there is at least one equal row and one equal column, I got
)
Fix r and use formula for (a + b)n
sorry, but I'm a little bit confused :(
shouldn't it be
?
oops, i replaced r,c with n-r and n-c (it doesn't change the value)
makes sense ^_^
thanks :)
if you don't mind can you please give me some advise on how to think in such kinds of problems?
thanks :)
It makes me incredibly happy that I (probably) fixed all the sign and off-by-one errors in C at 18:07.
Is there any way to hack consistently with regard to a segfault? There were a few times that I saw people accessing, say, s[n] when s only had n elements allocated to it, which should cause a segfault, but because of the magic of operating systems, segfaults only happen sometimes. These people will probably fail during systests, but I can't reliably hack because even if I submit a hack, the OS might not complain about a segfault and I'll get an unsuccessful hack. Is there any way around this or should I just not try to induce a segfault in a hack?
I also faced this issue. I think there is no way to hack such solution surely. I hope MikeMirzayanov may do something to handle the issue, for example, some cases may be added so that such solution don't get accepted. But by this way solution may not even pass the pretests and thus no way to hack — I am not sure though.
By the way, you may create a blog post regarding this.
nice algorithmic problems :p
Streaming now! Check out twitch.tv/ttocs45 for problem discussion.
Биткоины звучат круче чем берубли или бердоллары:)
too much math
shouldnt be a problem for the great mathematician qkxwsm
So much counting problem :(
I bet a lot people tried oeis for div2D/div1B
Yes I did. I took first 10 numbers as sample and that was a mistake.
I misread problem A, and I thought it was asking about a split in which the sums are equal (instead of unequal). So, I asked them about the second sample why there is no answer for such case and their response was:
They said "that one is also OK" and the correct answer should be -1, that made me confused for a lot of time at the beginning of the contest.
Ouch, it is my mistake.
I misread you question as regarding first sample, I am very sorry.
constraints of div2 B should be bigger
i was trapped by the constraint i thought it's using DP. until the contest ended and i realize i could solve it using greedy approach which took 15 minutes earlier for me to code it :(
with these constraints it became a lot easier too .
It can be solved with DP too.
i know, but it took me longer to solve it using DP. cuz i've just started learning DP hahaha
what are the states for this? should I solve for every B (from 1->b) and in the end return?
States are [pos][bitcoins left][previous cut].
http://codeforces.me/contest/998/submission/39832055
Can anyone prove the function of problem div2_D / div1_B ? Please help me.
What's wrong with Errichto?
and dreamoon_love_AA
What's wrong with you? Why are you cyan?
When will we get data structures, graphs, etc , and not only math problems?
It's luck to compete in two math forces round 492 and 493... Lol, should run away from it for a short period.
Just find we can open the round, count number of math problems, then decide if we play it or not.
Contest was completely Fine, But I honestly think codeforces should limit the math/geometry based problems to atmost 1..cause This is codeForces not MathForces
Any reason why system testing has not started?
Always a common scene after 20-30 minutes it will be started judging. What is the problem? -->After two hours contest, contestant are waited more than two hours before got rating. Hopefully, it will be fixed soon.
There are many possible reasons why that happens.
For instance, sometimes there are successful hacks on solution that is passing systests otherwise (note that if the load during the round permits, some or all solutions are run on systests during the round). As this is suspicious (it might happen that the hacked solution is in fact correct, and the reference one is incorrect), it needs some manual inspection before starting the systests.
I don't get it how the hacked solution could be correct?
Sometimes the problem setter and tester do not aware that they also get into trap, say they get a straightforward idea, but do not prove it and unfortunately their idea was wrong. An example : http://codeforces.me/blog/entry/57192?#comment-408304
Поздравляю всех Россиян с победой!!!
ЛЕГЧАЙШАЯ ДЛЯ РОССИИ
Round was ended earlier than Russia vs Spain. What a surprise.
In div1.B, we should count how many difference a+5*b+10*c+50*d, where a+b+c+d == n.
We can notice that
if b == 1 && c == 5, a == 5 && d == 1, then a+50*d == 5*b+10*c && b+c == a+d;
if b == 9 , a == 5 && c == 4, then a+10*c == 5*b && b == a+c;
if c == 9 , b == 8 && d == 1, then 5*b+50*d == 10*c && c == b+d;
if we avoid all (b >= 1 && c >= 5) || (b >= 9) || (c >= 9), we can get the answer.
the answer is C(n+3, 3) — C(n-3, 3) — 2 * calc(n-6) + calc(n-7) + calc(n-11) = 49*n-247
sorry for my poor English :D
if b == 1 && c == 5, a == 5 && d == 1, then a+50*d == 5*b+10*c && b+c == a+d;
if b == 9 , a == 5 && c == 4, then a+10*c == 5*b && b == a+c;
if c == 9 , b == 8 && d == 1, then 5*b+50*d == 10*c && c == b+d;
How did you find these relations? Did you use any specific technique?
For Russian Celebration, Mike should increase all of our rating :3 :3 (Rus Vs Spa fact)
Can you explain 7s TL in D ?
39833354 — O(n2k)
39838295 — O(nk2)
It was hard to distinguish?
Because we expected an
solution, actually.
Aargh, I wasted so much time trying to micro-optimise my O(n2k) solution which was within about a factor of 2 too slow (on my local machine at least), and then ran out of time when I saw how to do it in O(nk2). I had a working solution about 5 minutes after the end of the contest.
I am very disappointed that MrDindows didnt solve this problem :(.
I wrote O(nnk) first, but didnt manage to make it run faster than 17s. I was also confused by this TL.
Sorry, my bad :(
Hackforces!!
Does anyone like me WA on A,B,C and AC D :(
2
3 10
1
1
4 8
1 2 10 11
1
5 10 1
11111
0
Just a small typo in A
Should be 1 1
Awwwew how careless i am, i printed 1 a[1] instead of 1 1 ... Arghhhhhh in B i missed a "=" in my if statement T_T rip me
Same hea :(
Why are there always math questions whenever greengrape is associated with any contest, be it testing or writing? Because of her, i am always fucked in the contests. My cumulative decrease in rating is now 400 in contests related to that idiot greengrape.
Can’t wait for people to start referring to me as “it”, lmao
What's the test 16 of Div2/C?
I hope you enjoyed the contest!
The editorial was published! Check it over there
The contest was nice.
The following submission for problem D in Python3 gives wrong answer:
39842076
Whereas the same submission in Python2 passed:
39846023
Why would this happen? Can somebody look into this?
I am not sure, but maybe because of division? In Python 2, "a / b" is integer division if a and b are both integers, but in Python 3 it instead performs "actual division" (i. e. returning a fraction without rounding).
Really, that was my fix for C between pre-tests and AC...
Use
scanf(" %c", &c)(note the space before the format) to read a character after skipping whitespaces. This might save you a lot of trouble in the future when it comes to input :)I used
getchar()in hope to "optimize" my solution. Btw, unwanted char wasn't space, it was\n:D.The term "whitespace" includes all characters such as spaces, endlines, tabs, carriage return, etc.
Your crafting.oj.uz ratings are updated!
I was looking forward to rating changes in comparatively easier Div 3 contests coming up soon. Alas!!
I don't know if this is the right place to comment about this or will make things better or worse, but I am commenting anyway, so I can say to myself that I at least tried. Codeforce has deemed that my solution to today's contest's div2 D has too many similarities with some other accounts and hence ruled me out of this competition, of course due to my own mistakes.
I just want to clarify that (no matter the result of it): I thought up, figured out and coded the solution of that problem all by myself and did not take any help from anybody or any other resources. Initially, I wrote a bruteforce code but it took up a lot of time when it was running for n=15. but n=11, 12, 13 and 14 were enough for me to figure out my solution based on pattern. my codeblocks was still busy with my bruteforce code so, I used ideone (and stupidly, it was public) to check my code for errors. and the rest is as it is now.
But of course, words are just words. I don't have that hard evidence that it was my own code. But I do have some points to show. Do note that it's not contest rating or such I am worried about, I am not blaming anyone other than me or asking for any sort of rating recovery. It's the reputation and shame that matters more to me. Right now, people who know me and friends can look at my profile and think I cheated, and that really hurts. If only at least that could be solved, it would mean the most to me. Without further ado, I will present the points which -might- prove that I didn't cheat at least.
This should clear up that despite my mistake of using ideone in public mode, I at least didn't cheat and solved the problem myself. And I will make sure that I will never make such a mistake again. But the consequence of this naive mistake, the shame, that's what's killing me. If only there was a remedy to at least clear my name... :(
I am also adding my bruteforce code from which I found the pattern, not that it's any kind of proof or whatsoever.
Aw. That's really unfortunate :/
Knowing you irl, I knew something like this probably happened. Hope things work out for you, don't let it keep you down too much.
afaik codeforces won't block you, just disqualify from this contest. So you shouldn't worry much about this situation, as well as you shouldn't hope for not disqualify — it's your responsibility that someone was able to steal your solution. In your place I would say "okay, today I learned something new, will be more careful next time".
I definitely learned something new, and I sure as hell will be more careful next time.
P.S.: The purpose of this comment is not to hope any reconsideration or because of fear of disqualification. I understand that the ideone debacle is completely my fault and don't blame anyone else. I just wanted to clarify myself in this comment.
I have seen people using two IDE's on their PC for this kind of situation. I myself use Code::Blocks and Visual Studio. nsf25, you can take note, brother. :)
Thanks, vai. I never faced such a situation during an individual contest before hence the mishap. I'll use a secondary IDE if the need arises. :)
Is it normal to show top 10 instead of top 5? :)
I think it was a good decision in this case.
duliu math problems
can anyone explain me div2 B cutting problems.
if i cut at a position So i get two sections,So does the both section need to have same the numbers of odd number and even number.
like :
6 4
1 2 4 5 7 7 what's the output of this one?
1 2 | 4 5 | 7 7 is it possible?
The problem statement states
"There is a sequence of integers, which contains the equal number of even and odd numbers."
Did the author intend any pun when writing problem B statement by writing 'cut "the rope"?
Yep =).
Share the reference or joke please!! If you dont mind :)
This is not exactly joke, but reference to the cut the rope game
It helps me a lot, I hope to get better and better.