다시 만나서 반가워요, 코드포스! (Nice to see you again, Codeforces!)
I'm again happy to introduce you to Codeforces Round #589 (Div. 2). Please look at following information for details:
- This contest will take place on Sep/29/2019 16:05 (Moscow time).
- The round will be rated for all Division 2 participants.
- There are 6 problems and you will have 2 hours to solve them. Score distribution will be announced later.
The listed handles below are contributors. Thank you for all who listed!
- Main author: McDic — I made and prepared all problems.
- Coordinator: arsijo — He is my coordinator again.
- Early phase testers: dorijanlendvaj tfg Lawali — They are early phase testers. They mostly focused on test data.
- Late phase testers: Kuroni imbr92 Redux Dr_Park Savior-of-Cross TOPCYBERFLOWER _overrated_ antontrygubO_o raiden1943 — They are late phase testers. They gave problem difficulty/quality feedback by virtual participation.
- Codeforces Team: MikeMirzayanov and his team — They are working super hard to make Codeforces and Polygon great! Especially I love Polygon's framework! Thank you!
For this contest, I tried to improve following things:
- Reasonable difficulty: At my last contest, less than 200 official participants managed to solve at least one of DEF. Especially, 1182D's problem difficulty rating is 2500 and 1182F's problem difficulty rating is 2900(no official solvers!). This is not good for Div.2 participants. In other words, my first contest was hell. So this time, I tried to make my second contest to have more reasonable difficulty than my first contest.
- Stronger data: There were 300+ successful hacks and almost 2000 sysfails at 1182B. At this time, I splitted testing phase into early phase and late phase. I'm bit worried, but I believe data will be stronger than my last contest.
- Compact statement: I remember many people complained about 1182C's super complex statement. I made very compact statements for this round. There is no problem with more than 10 lines of statement(except I/O section) in this contest.
I hope everyone can enjoy my second contest. Thanks in advance!
UPDATES:
- If you want to discuss problems in chat after contest ends, come https://discordapp.com/invite/algorithms and you can enjoy discussion.
- I have deleted my last problem(G) from this contest during testing period. I really wanted to include that beautiful problem in my contest, but nobody solved that problem for a week. That problem will be appeared in another Div.1 contest.
- Scoring distribution is 500(A)-1000(B)-1250(C)-1750(D)-2250(E)-2750(F).
- Editorial: https://mirror.codeforces.com/blog/entry/70162
- Congratulation for winners!
WINNERS (updated):
- PositionZero
- supy_2
- hitman623
- lzqaq
- cwise
- LittleBeetle
- Tsypkokokokoko
- i_love_gnar
- 8-_-8 (handle mentioning is not working on his handle)
- wdk1745
McDic orz. It will be a great round!!!!!!!!!!!!!!
i don't think so. my arguments: 1. one 2. dva 3. tree (derevo)
my arguments: McDic
McDic is geniosity O_o
McDic is so cute
aryaman is so cute
farmersrice is cuter
I like the compact statement part
The ghost is adorable awww
This what they call learning from your failures :)
Yup, this is the best example of learning from the past.
Ideal time! I wish good luck to all of the participants!
Wa! Another Korean round!
I can still remember the last round QAQ. I get a wrong understanding on B.
Congrats on your round McDic O_o
$$$\color{purple}{O \text{_} o \text{ !}}$$$
O_o
O_orz!
BOOBA
Another Korean round! I think this round is well-prepared. Wish your high rating!
I've never seen someone post about their previous mistakes on a round, and talking about how to make the next one better. What a good way of making the most of constructive feedback. I'm eager to see these improvements in the round. It would be cool if this example is followed by other contest writers. And by other writers I mean GreenGrape.
Thanks a lot:)
There is nothing better than Compact statement！
look forward to a wonderful contest!
My code was hacked for the first time in your previous round :). Hope this round will be fun.
Many successful hacks is not bad. As long as these hacks are not
if (n == 1).But 2000 sysfails in B are bad.
sounds like an awesome round Good Luck :D
GOOD LUCK
NO
Contributed to you being the lowest my fellow human :)
finally .... tow of my solutions was hacked last round ... thanks you ,,
I love how you are trying to improve your contest. Hope it will be a great contest! :D
Welcome back McDic after 4 months with a new contest;
thanks for the improvement :)
Thanks a lot for all the hardwork. Particularly, reflecting on the previous mistakes is great <3
Interesting blog . truly to say , I read every word of a blog (about contest) after a long time !!!!
so many world :D
Is this some special round? I have never seen such upvotes on any contest announcement blog before.
Twice the pride, double the fall
You dare question the power of McDic?
Is that a kind of fetishism?
No, he is objectively a god
First time to see someone writing on the past mistakes. Hope for a good round :D
McDic make me "out of competition".
Soo much upvotes before a contest. Seriously what if this guy(dude) is like a politician who's promising what he can't execute?
after all, he admitted his mistakes in the last contest and is trying to make this one better.That's why he deserves these ups.
Admittance doesn't matter, Results do. Y'all should at least wait and experience first. I guess that's why it's quite easy to scam y'all
I am in super pressure. QAQ
Hope there will be no fatal issue on my second contest.
agree.
why your comment has only 7 downvotes but still light coloured?
WTF? Why so many upvotes?
Давно не участвовал в раундах. Как я понял, граница див2 сдвинута от фиолетового выше? Где можно почитать про изменения? Быстро не удалось найти.
https://mirror.codeforces.com/blog/entry/59228
In ready to compete in excellent contest!
Imagine if after all the upvotes the round isn't better than the previous one lol that would be funny as hell XD (just kidding I think it will be good)
Thats why I always keep my vote till the end of the round
Ah geez, Rick, you shouldn't be so cynical
Am f***ing Rick Sanchez C137, I can be what I want :D
something new
nung nung
It seeming a well-prepared contest. I think it will be an enjoyable one.
I like nice weather :)
sorry
One of those rounds where the pupils do A,B and then keep refreshing the ranklist for 1 hr.
I hope you will not set problems with 4 levels of definitions in the future. And I hope coordinators will not approve such problems in the future.
All that I can do now is to vote a blog down, but it was boosted by orzing schoolboys to 1k+, so probably it won't get downvoted. Or can it? There are 13k participants...
you are salty
I have no problems with multiple definitions as long as each of them is clear enough. Anyway, if you hate definitions, you may enjoy this gem 1120A - Diana and Liana.
I have problems when the definitions are recursive. In today's problem we have 4 levels: 1) prime 2) g 3) f 4) answer. It is hard work to build a full picture of the problem in the head, it takes a lot more time than thinking of a solution and coding that problem. I think I'm not alone here.
The problem you mentioned have many definitions and it is bad, but they are parsed easily.
Fully agree with you
I think the examples given in statement does really help me understand how to connect all those definitions. I agree that it's not a good problem but your original comment seems to be a bit excessive.
McDic do you mind explaining why do you have to include $$$x$$$ and $$$prime(x)$$$ in this problem? I feel that it does nothing but add a negative value to the problem.
My original statement for C was full of math. I simply changed part of them to English sentences, step by step.
This contest brought to you by the number $$$1000000007$$$
And I used $$$998244353$$$ from my template in E, and could not debug that :( Otherwise the code was correct.
deleted
ARGH! Could you do less number theory problems next time?
By less you mean 0? I see 1 "number theory" problem.
C and E is pure math, no programming at all. F i dont know.
F is definitely not math.
Ok, I can agree that C felt a bit "mathy" and the statement was a little off-putting, but labeling E as pure math is just wrong.
It is about math, not about programming.
If you want to do a programming contest you can go to a programming contest site.
Oh, wait...
I feel like C's statement could be improved by using consistent variable names.
I mean sth. like
$$$\prod_{i=1}^{n} f(x,i)$$$ with $$$f(x, i) = \prod_{p \in prime(x)} g(i, p)$$$ where $$$g(i, p)$$$ is the maximum....
would be much more understandable, or not?
It is not understandable either way.
CF team requested me to use less formula, but use more english sentence
The first version of this problem by McDic was like this. However, not every CF user knows this. Since we wanted to make the problem clear for everybody, and in the same time short enough, we decided to rewrite the statement using simple English words.
Makes sense, but still could've defined $$$g(y, p)$$$ instead of $$$g(x, p)$$$ to be more consistent with the definition of $$$f(x, y)$$$.
calculate the number of N! for the prime P in X are NUM ,so the answer are the product of quickpow(P,NUM).
What was pretest 15 for C?
3 450283905890997363
answer is 137055211
Thanks, I get this
What the hell is pretest 5 in C
How to solve C ?
For each prime in the prime factorization of x, it will appear in the answer exactly k times, if it appears k times in the iteration of 1 to n, so for instance, if n = 8, and x = 2, then the answer is 2^7.
Now, how to count them fast? Simply count all n/prime^i, for all i, such that prime^i <= n. call this value sum. this can simply be done by calculating first n/prime, then n/prime/prime , etc.
After this, calculate prime^sum, multiply to answer. Iterate for all primes.
Unfortunately I'm getting a WA on test case 5, so I'm probably wrong somewhere, but I can't figure out where.
How to solve E and F?
If I sent two correct decisions, which one will count?
The most recent one I believe...
Modforces :)
actually ($$$10^9 + 7$$$)forces
I had to wake up at 5:50 am on a Sunday morning to write the contest, but it was (mostly) worth it!
Good job McDic.
Whats B pretest 6???
How to solve E, I tried memoization, for all pairs of n,m size of grid, got TLE though....
I found D's problem statement a bit vague, the line "All set should not be empty", I believe it could have been written as "No set should be empty". What about you guys?
Good English
What is pretest 4 in Problem B ?
4 4 2 0 3 1 1 3 0 3
I don't know why the answer is 0 instead of 4. Do you know?
Red is for row constraints and blue is for column constraints, check is where there has to be a black cell and 'X' is where there has to be a white cell so as you can see in the 3rd row 4th column there is a contradiction.
Hope this helps
Yes, I didn't get from problem statement that the input could be invalid. Thank you.
https://mirror.codeforces.com/contest/1228/submission/61492326 https://mirror.codeforces.com/contest/1228/submission/61490870 https://mirror.codeforces.com/contest/1228/submission/61490695 ???
https://mirror.codeforces.com/contest/1228/submission/61489289 ???
MikeMirzayanov isn't this code obfuscation?
Pretest 12 in D? how to solve D?
13444 Registered users, new Record?
what is pretest 13 in C?
Is the intended solution of E $$$O(n ^ 3)$$$ DP?
I saw someone passing E with this complexity, unfortunately mine TLEd at test 3.
submission: 61507994
Mine passed with that complexity, you shouldn't use fastpow in such a deep loop, just precalculate every power.
Thx for ur advice, the constant factor really sucks
To be honest, a 2000 ms would be more reasonable
As far as i know, TL is 1s to cut off $$$O(n ^ 3 * log(n))$$$ solutions.
Wow a log(250) is only 7, but it surely kills
Yes, it can be solved in $$$O(n ^ 3)$$$.
My code: pastebin
$$$O(n^2)$$$ inclusion-exclusion, I guess.
can you please explain your approach ?
It is somewhat similar to BZOJ 1801: [Ahoi2009]chess. U may read it’s solution if u know Chinese.
The idea is to calculate $$$f(i, j)$$$, the number of combinations such that there are $$$j$$$ columns having at least one $$$”1”$$$ after filling up $$$i$$$ rows. Then the answer is $$$f(n, n)$$$.
I believe u can derive the transition formula on ur own :)
61473445 61473656
I submitted the exact same code twice by mistake, and got -50 for it? :X
That feeling when you find out that your code actually matched the samples before the end of the contest but as a matter of fact you forgot what the sample actually was in the first place so you thought your code had mismatched the sample and didn't submit code
A life-saving tip- don't keep yourself unfed for 16 hours before any contest.
can someone tell me what's problem with my solution for problem — > 3 https://mirror.codeforces.com/contest/1228/my
dude, that link will send everyone to HIS/HER submissions page lol
it's cool bro. It show my entire mind and you need to find out bug from that.
not your mind, whoever clicks on that.
although this reply doesn't have a link, it sent me to google translate, and I still don't get it -_-
How come score 1250 for C while 1000 for B?
Is C seriously easy for 2500 contestant?
Well, yes
hi wookje i am your big fan
Such an awesome contest . I got to learn so many amazing concepts.
In Problem B Div 2, Please help me know why my code is getting runtime error in TestCase 6?
https://mirror.codeforces.com/contest/1228/submission/61498112 (commented code)
Although I had a terrible performance on problem D, I like the succinct Title Description very much.
The simpler the topic is, the more favorable it will be for those who are not proficient in English, and the more favorable it will be for fair competition.
Thanks a lot.
why this submission https://mirror.codeforces.com/contest/1228/submission/61492705 passed? Does here j var will not be overflowed?
The culprit is
oh, exact -_\
Thanks for 3 combinatorics tasks. I liked them a lot. I think every
mathcodeforces round should have 3/6 math tasks.Can you clarify to me which 3 tasks are combinatorics?
For problem D, you can also use this approach:
In fact, you don’t need to use hashing — you can just store set of vectors
Thanks for pointing that out. I forgot that
std::vectorimplements==and<operators.Wow that's really neat solution. Here's my solution using the above idea.
Please ignore my naive question in old revision.
How to solve D?
Wowwww... Great contest <3
D seems to be an easy version of DOOFST in Codechef September Challenge.
The round was awesome! But why would you warn the contestants about integer overflow in problem C? Isn't it a part of the problem to figure it out by yourself?
Many blue testers struggled in that. That's why I warned.
And why even have $$$10 ^ {18}$$$. Problem would have been equally interesting with $$$10^9$$$
How the System Testing done so quick even after such large number of participation
Lol.The question you asked matches the expression with your profile icon
Was the diagram for the sample input/output for 1228D - Complete Tripartite added partway through the contest or after the contest? I don't remember seeing it when I solved the problem.
I think it was kind of bug. That picture was here for eternity.
Ah, okay, thanks!
Thanks for the problem C test 3 overflow warning.
Can you please fix the problem D?
It mentions that "not all vertex sets should be empty" while it implies "all vertex sets should be non- empty" (which I figured out after the contest ended). Both statements are very different.
No, it mentions "All vertex sets should not be empty."
This doesn't mean All vertex sets should be non-empty. All vertex sets should not be empty -> There should exist at least one non-empty set.
At first I also thought that some vertex sets can be empty but not all of them.
Although a bit too many math problems, still a great round it was, I believe.
I really enjoyed problem D. I haven't solved problems that require sharp observations for so long.
Now I'm also curious about your problem G. Anyway, thank you for such a great experience!
I am literally losing my mind :/ , can someone explain why in problem C when in this code 61512229 I add this line "if (a==0||b==0) return false;" in line 10, I get WA in TC3? 61512212 , i mean it says overflow, but adding "if (a==0||b==0) return false;" should'nt give a different verdict in this problem :/ should it? someone pleaseeeeee help ;(
McDic first of all great contest thanks :D , second please help, seriously I am lost for words, I feel like the problem is from CF compiler itself, I am seriously losing it here...... I just added an "if" which doesn't even get to do anything there in TC3 but still get TC3 WA ;(
Position Zero! This is Tendo Maya. (((
Thanks to McDic, I'm purple ^_^
Great contest thanks to McDic. Hope to make another contest!!!!!
the system test of problem D is too weak.
UPD: maybe using "too weak" is unappropriate, but I think it's a big slip.
most submissions can't pass #48(it was added after system test).
input:
output:
I am sorry about such issue. I considered 7 types of graph and that was not enough :(
What happened to the candidate with 3rd rank.All his solutions are shown skipped?
McDic Thank you for this awesome contest.
How to solve B. I could not find any idea
The Editorial is Published . https://mirror.codeforces.com/blog/entry/70162
I have a headache of problem C statement and tutorial. Very hard to understand the problem.
Problem C.
Does taking modulo with LLONG_MAX really matters?
with %LLONG_MAX ACCEPTED
without %LLONG_MAX WRONG ON TC3
By the way in local compiler both code were giving same answer.
Signed integer overflow is actually undefined behaviour; in your WA example, the compiler notices that you're diving a*b with b and automatically replaces it with a, meaning that your if condition never triggers. When you're doing %LLONG_MAX the compiler actually calculates the expression.
But multiplication and division are in different instructions. So it should be like two long long int numbers multiplied and stored in another long long int variable(if it overflows wrong value stored here). Then in another instruction division takes place and should trigger if condition in my code.
Or may be codeforces compiler is more smart then my local compiler :( that it can combine two different instructions, which is unexpected.
REF. Same method for int is used here . Which should work for long long int also.
While trying to hack during the contest I came across these submissions and I feel like this submission and this submission is almost the same and has been purposely modified to escape plagiarism. I request the officials to take appropriate action.
For problem D,
I don't know how to prove it, but this seems to be a solution.
Observe a valid graph focusing on the degree of edges.
In common cases, if a graph is valid, it can be divided into 3 sets, and the degree of vertexes in every set is
n - size_of_this_set, and they should be the same. (so in a valid graph, it could have 3 type of vertex at most)When add all possible degree values up, the sum is
3n - sum_of_size_of_every_set, that is,2n.Denote all possible degree values as a set $$$S={ s_k }$$$ .
There are only four cases:
Seems enough , but I got Wrong answer on test 1461514754. Because it's not necessary and sufficient condition.
So, in case 3, I make a check of all the edges to see if it's not valid, and passed all the test cases (for now).
My solution: 61514951
BTW：Nice round.
BTW2：Sorry for my awkward expression...
Hi, How can I avoid overflow in question C?
if(((a*b)%LLONG_MAX)/b==a) then it doesn't overflow, else overflows...... check special cases a==0 && b==0 too so you don't get RTE for dividing a number by 0.
If you don't mind this $$$log(t)$$$ time, you can calculate the max $$$sz$$$, which satisfy $$$a_{i}^{sz}<=t$$$ , by the code below:
When you reach $$$a_{i}^{sz}$$$, there is no need to get larger. So this will keep all your variables below t(or some other threshold).
Thank you.
In problem D. I find number of connected components in complement graph and if this number is 3 then answer is yes and sets is this connected components. why is this solution wrong? I recieve wrong answer in test 11.
You also have to check that there is no edge between vertices in the same component
Yes. thanks. I got Accepted.
I am not getting my solution accepted[submission:61543290].As per test case 7,expected output is different from answer but I am getting correct output on my code using IDEYour text to link here...
This round is way better than the last one.
Could you please update tasks' ratings?
Do you mean difficulty ratings for my problems? It will be updated by Codeforces team, not me.
Can anyone explain the question D easily? I didnt understand the question for a long time. TIA :)
Make 3 vertices sets to make each pair of sets forms complete bipartite graph.