Moo! (Hello Codeforces!)
I’m very excited to invite you to Codeforces Round 621 (Div. 1 + Div. 2), which will take place on 17.02.2020 18:35 (Московское время).
In this round, you will be helping Farmer John and his prized cow Bessie cowmplete some fun tasks.
The contest will have 7 problems and is combined and rated for both divisions. The duration is 2 hours and 15 minutes. The problems are prepared by me (FieryPhoenix) and dragonslayerintraining. We tried very hard to make them interesting and hope that you will enjoy them too!
This round would not have been possible without the wonderful coordination by adedalic and cdkrot. Thank you so much to the testers as well for all the invaluable advice: tmwilliamlin168, walnutwaldo20, nikolapesic2802, bfs.07, Rods, lynmisakura, JustasLe, and hocky. As always, thanks to MikeMirzayanov for the best systems Codeforces and Polygon.
Good luck and more importantly, have fun and learn something new!
UPD: The scoring distribution is 500 — 1000 — 1500 — 2000 — 2500 — 3000 — 3500
UPD: Editorial
UPD: Thank you for participating! Huge congratulations to the winners!
"Moo" as greetings is epic move
Farmer John? USACO Web 1.0 training site throwbacks
i love you
Farmer John comes to codeforces! Anyway, thanks for the later start time, I know we’re pretty under represented here in the Pacific coast, but it feels really nice to finally have a time that is not before 6:30 a.m.. Hoping for a great contest!
The contests are still always in the morning for US people, which is a disadvantage for people who aren't morning people and people who have to work/go to class. It would be nice to change up the start times more like Project Euler does.
Today US people are grateful to George Washington for taking away that disadvantage.
btw, do you know any sites similar to Codeforces that host contests more accessible to Pacific coast people?
I always feel so grateful that there are always people dedicate their time and efforts and come up with cool problems and contests so we can all participate regularly enough. Love Codeforces, love you guys <3 <3.
william lin <3
S. Americans
Contest ID 1306 has gone..
The present contest ID is 1307 and the next contest ID is 1305 XD!
XD!!!
[deleted]
The "MOO!" is so kind! Hope for a USACO round!
Thanks for codeforces and authors of this contest!Good luck everyone！
Btw why it is combined?
I second this question. Combined makes hacking more extreme, adds two impossible problems for div2, while for div1 it adds two trivial problems where reading speed matters most.
I agree with most of the criticism, but a few counterpoints/clarifications:
What is wrong with hacking being more extreme? Are you saying this gives extra incentives for div1 people to focus on hacking rather than solving new problems? If that's the argument, then I think it's valid. But hacking as a general concept isn't bad, and it isn't immediately apparent why more of it would be a negative thing.
I agree that the problems added for div1 are annoying, but I personally know people who have studied algorithms to graduate level and beyond who don't often compete in contests that would likely not do well in a normal div2 contest because of slow speed, but may do better on a div1+div2 combined contest. Perhaps such people are not numerous enough to warrant the combined contest, though.
He didnt said much. There is a long discussion on cf (which I failed to find) with a conclusion that combined rounds should be avoided as far as possible. Both comments were made keeping that in mind.
In the end we decided to make round combined due to unique reasons relating to problem difficulties and contest duration.
My second contest! Hope, I will be "blue" after it
Good luck to all participants :)
USACO2020 February Contest extra round :)
Daily contest : CF Round 620 / ABC 155 / CF Round 621 :)
I think this is Div.3 because Div.1 plus Div.2 is equal to Div.3 :))
That's what you need
I know, it's just a joke
Hey guys why -32 ? it's only basic math My contributions are decreasing ;-(
You lied, your password is not SiRaC9871.
Did you try ? Why ? This is mine :))
What is the difference between codeforces global round and codeforces combined round?
I think the global rounds were a special edition sponsored by some company or something, the combined ones are regular rounds.
can anyone explain about problem hacking ?
hacking is to give a testcase that makes a solution to a participant fail(i.e Wrong Answer,runtime error, time limit exceeded)
who is the defender
the owner of the code that you try to hack
what does he do
he do nothing ,if his solution is absolutely correct then no one can hack his code
how to hack
On the dashboard, click the padlock icon for locking a problem (Note, that you can not send your solution for a problem after locking it). Then go to room results, where you can see roommates codes for the problems you've already locked (you can see a certain solution by double clicking on it in the room results table). After you've opened someone's solution, you can consider it and then hack it. When hacking a code, you're entering some testcase on which that code is most likely going to fail (it may be wrong answer, or running out of time/memory limit). When you want to enter a large testcase, you can send test generator instead of typing it. Test generator must be your program which produces a file with a testcase in it. After hacking a code, you can see hacking results. There are two possible outcomes: "Successful hack" — it means the code failed, and you're rewarded with 100 points for that. Otherwise, it's "Unsuccessful hack" (the code did not fail) and you get minus 50 points for that.
quoted from kingofnumbers
it was obscure to me thanks
God Bless Our King
Is one only vulnerable to hacking if he/she locks his/her own problem? Or is everyone in the room vulnerable?
if you lock your problem you can hack anyone in your room
As stated above, only those who lock their problem can hack (others in their 'room'). Conversely, you are vulnerable to getting hacked by those who do, regardless of whether or not you have locked your problem.
hope it will not include mo's algorithm as cow bessie is here .
You shouldn't have Bessie and Farmer John cowmplete tasks in a Codeforces contest.
At this rate, they won't have enough time for the upcoming USACO contest!
Finally a contest not during school!
What is "div1+div2"?
div3 obviously
That means, all contestants (both Div1 and Div2) will be able to give the contest as a rated contestant.
as this contest is for both div 1&2, will different rating algorithm be used for this contest??
When the round is (Div. 1 + Div. 2) is the levels of the problems Div. 1 or Div.2 or Div. 3÷2?
Find out tonight on the next episode of codeforces
codeforces Z
Is it rated?
Of course,and it totally has 7 problems to solve.Good Luck for U.
are you serious?
The time is not friendly to the Chinese
Score distribution??
Focus on the new red rating point!
Standard scoreboard
It have been long since the last time the standard scoreboard occur.
phục hận gang
let's help farmer and his cow xD
tourist isn't that good anymore lol
Look at yourself first before commenting on others !!
emilia_clarke isn't that good anymore lol
This is probably the first time I leave the contest in the middle just because of boredom. Thank you, problem E statement.
E was actually pretty nice imho. Even though it seems like some tedious crap at first, it turns out to have a clean non-trivial non-magic non-standard solution.
Did I miss something on E? It seems like the solution is just "choose one cow to be the cow on the left who moves furthest to the right" and do a O(M) scan to find how many assignments of cows satisfy that criteria. Implementation wasn't the nicest.
Then again, I probably missed some implementation tricks.
I did exactly that (more precisely, for each scan, look at each sweetness group, count the number of cows in that sweetness group that can go to the left, how many to the right and how many to both).
Idk, I thought it was cool. Implementation isn't nice, but I definitely wouldn't call the problem boring.
Yeah, you always have to choose the last cow from the left, but then you have the following problem: choose some points from the "left part" and "right part" such that for each given pair $$$(l_i, r_i)$$$, the situation where $$$l_i$$$ is chosen from the left part and $$$r_i$$$ from the right part simultaneously never happens, $$$S_{l_i}$$$ for all chosen $$$l_i$$$ are all distinct and similarly for $$$S_{r_i}$$$. The pairs are sleeping places of cows.
The implementation of the rest is simple (~25 LOC for me): group cows by $$$f$$$ and for each value of $$$f$$$, find the number of pairs $$$(l_i, r_i)$$$ that 1. lie in the (left part, right part), 2. (in the left part, out of the right) and 3. (out of the left, in the right part); then, the number of ways to choose 2 cows is $$$(n_1+n_2)\cdot(n_1+n_3)-n_1$$$, and if that's 0, then $$$2n_1+n_2+n_3$$$ is the number of ways to choose 1 cow. It's $$$O(N)$$$. The value of $$$f$$$ for the chosen last cow from the left is handled separately and even more easily.
I read it several times and still could not understand the setup :( Probably spent too much time at countryside to perceive cow problems abstractly...
Maybe I just had luck reading it. I agree that the statement is ugggh.
Bessie and John, come like a wind
Magically, stop right here
Left us with, a great contest
Chaotic, yet arousing.
Bessie and John, left like a dream
Where are you, the green of grass (AC)
Left us with, yellow results (WA)
Magically, rating gone.
(Written by a contestant, who find the beauty of Literature in CP)
P/s: We need a way to make a paragraph in CF comments, it will promote poetry in CF.
What the ...
MiFaFaOvO (or dls) AK this contest when there are still an hour to go?
E problem
The moment a cow eats hi units, it will fall asleep there, preventing further cows from passing it from both directions.
Meanwhile Indian cows: You guys can do that?
Meanwhile Indian drivers.
.... punished brutally by public before govt. ;)
hashtag TouristSoldier you're still number one in our hearts tourist
jqdai0815 for president!
This guy is though, after finishing the problems, resent problem D
One of my most bad rounds so far, predictor says aprox -120...
Was not able to solve B and not C. Feels sic. :/
Edit: And how redicolus simple the solution to B is, omg.
sometimes round comes unusual for everyone . sometimes you will solve more sometimes the other one will solve more..
Yes, sometimes you loose, sometimes the others win... ;)
Please explain me the solution for B . I am still not able to get it from editorial
see this comment https://codeforces.com/blog/entry/73954?#comment-581603
Hacks for B and D?
Pretest 9 for E?
what is pretest 9 in D??
Did anyone else solve problem D using binary search on the answer and segment tree? :( Overkill
do you mean C?
No, No, problem D, about graph.
Interesting... I don't know how you would use those for D but I feel like in general binary search and segment tree isn't TOO overkill for a D
I tried Segment tree, But WA on pretest 3. I thought it is overkill too. Why do you need Binary search?
You can check this out https://codeforces.com/contest/1307/submission/71320387
Can you please explain your approach?
I didn't use binary search but I used segment tree.
300iq did.
How to solve D?
Find distances from vertex 0 and vertex n — 1 to all the others using BFS. Now sort the special vertices according to the distance to source. Iterate over all the special vertices except the last one. For each of them find the best "pair" : the vertex that is not closer to the first vertex than the one currently being considered, and that is as far from the last vertex as possible (you can build an array of suffix maximums to do this step in O(1) ). Now using the distances we computed, just get the length of the shortest path with this vertex added. The rest is trivial.
what is pretest 15 in D?
Maybe it will be like this: Shortest path from field 1 to field n has no special field, but when added one road the answer charges.
When real master reveals his real ability
i just got lucky :p
There is a problem about problem E:
"Two sides" means which of the pictures below?
If I understand correctly, the "two sides" means the top picture.
In fact it means the first picture, and a lot of my friends including myself misunderstood the statement.
And in addition, You can pass the samples whether or not you misunderstand the statement. And you will probably get WA on pretest 9 if you misunderstand it.
What's the expected complexity in F? My $$$O((n+q) \cdot \log(n))$$$ times out.
I got AC (71329978) with $$$\mathcal{O}((n + q) \log n)$$$ in 670ms.
I had one HLD path query and two binary searches on the path array per input query.
Try to hack my $$$O(k^2)$$$ for D: 71334468
But why it passed as per constraints this must fail or time out. I do not tried just because I was not getting approach less than O(k^2) complexity!!
can someone explain why this solution gives runtime error on pretest1 .Solution using vectors... and the next submission using arrays passed please explain!!! Solution using arrays.
How to solve D?
What is the reason for 1 second TL for E? Can you please explain?
Absolutely +1 to this question.
Had to spend 5 minutes making non-asymptotical optimizations to my Kotlin solution.
Meanwhile, a cubic solution wouldn't fit into 2 seconds either.
There were a few $$$O(n^3)$$$ solutions with heuristics that we tried to cut.
With n=5000 and 1s TL? For real? Ok sir
It seemed tight to me at first too, but with $$$O(N)$$$ arrays + most passes being linear, cache efficiency is high and $$$N^2$$$ is just 25 million.
With modulo operations it does not work so fine.
25 million modulos = 0.37 s locally (admittedly 64-bit, but also weaker than CF machines) and that's supposed to be the heaviest thing in the $$$O(N^2)$$$ solution.
If 25 million modulos are a serious threat of exceeding TL for a solution that doesn't use anything else slow, that's a problem. Who knows, we'll see.
UPD: Yep, the same time for modulo and under 0.5 s worst case.
Isn't your solution complexity $$$O(N^2 log MOD)$$$ ? This is almost billion modulo operations, which is really big amount.
Nope, it's not. Values till n are memoized and I am counting inversed values only for these values.
Problem E:
Two sides, the left and the right. Hmmm...that's it!
And this can pass all 4 examples.
Have to say goodbye to legendary grandmatster :(
I am very sorry that this was unclear, and we did not receive a single question about it. Best of luck on future rounds!
tourist solved the first problem in less than a minute :O I didnt even read the problem statement in that time (probably my page also not opened by then :P )
I tried something different for G, I take the edges (u,v,w) such that d[v]-d[u]=w. Then find the mincut in this graph. This gives us the edges whose weight we should increase simultaneously to increase the length of shortest path. So if the remove these edges and again run a dijisktra than the distance of nth node should give us the weight until when we need to keep increasing the weights of the edges of mincut and we can stop this process if the nth node is not reachable. But this gives me WA on pretest 14. Any ideas why this solution is wrong?
You have to find the right min-cut:
5 8
1 2 1
1 3 2
1 4 4
2 5 4
3 5 3
4 5 1
2 3 1
3 4 1
Explain to me what your criteria is to say B was easier than C?
B is trivial implementation, once understood.
Can you explain logic behind solution of B.?
In one step the cow can jump at most max(a[]) distance. The last two jumps need not to be direct jumps, the cow can jump a bit left, or right with the first of the both last jumps.
See the tutorial for formulars.
That's not an explanation
Think of it this way: If D is already a distance that you can jump, only then will the answer be 1
Else, we have to create a polygon such that D is a side of it. The condition for any distance x being a side of a polygon is that it is <= the sum of all other sides
Therefore, just take the biggest element and the answer will be max(2, ceil(D/big))
Now this is an explanation (to y'all down-voter haters!).
Thanks [user:Aggu_010000101].
Do you know what about may be the 17th test task E?
Why does the code with complexity O(len(s)*26*log(len(s)) times out in C ?
look at this:
LL countGreater(vector<LL> arr, LL n, LL k)each time you call it, the vector
arrwill be copyed once. So you get a TL.Sorry for my poor English...
Thanks mate ! Passing arr by reference solved the issue !
Pretests for D seem a little weak, even some LGMs got problems. Actually, I expected this because the answer is just a shortest path length which in some (most?) cases will be not changed after the optimal edge addition. What was the reason for not asking for the optimal edge as well?
Awesome contest! I wish pretests were a little bit stronger for D, but you win some and lose some ¯_(ツ)_/¯
As time progresses, the frequency of WA in Problem D increases. Interesting...
In the announcement, it was written "positive difference" rather than non negative for question C. Then how are they considering single character occurence? The value of d is zero in that case. I got my solution failed in the main test because of their cheap mistake.
If you look below the sample input and output it clearly shows that zero difference is possible. That being said, the problem statement should have been fixed.
d can be anything in this case, but the sequence contains only the first element.
Still the announcement was quite ambiguous. Just look at the status of question C with Wrong answer at test 36. All the people are having same problem for case of n = 1
I think the statement was clear, it even explained the first example in detail right in the text. In particular, it says
and aaabb is hidden 1 time, suggesting that progression on size 1 is valid.On a separate note, I think it would make sense to have a case with a single character in the pretests.
Very beautiful problems
Congratulations awoo for becoming Red!!
Thanks! awoo~
It seems for D people who sorted special fields based on distance from field '1' (let's call this sorted array with special field indices as ar[]) and checked the shortest distance after adding edges between just ar[i] and ar[i+1] had passed.
Is there an explanation for this ? or is it due to weak tests?
For example, look at this submission.
Congratulations amnesiac_dusk for becoming International Grandmaster and First Rank in India!!
Are you getting paid for this?
No, I'm just happy for these guys.
Thanks!
.
.
Does that mean you failed system tests? That's a natural thing that happens to everyone..
hello everyone , I have submitted third question in this contest (621 div1 + 2) after submission it is showing runtime error on test 36. but in my compiler the answer is exactly coming what the answer of test 36 also on multiple online compiler like ideone.com but they are giving correct answer also i have checked my code there is no chance of runtime error on test 36. please anyone help in this matter ! https://codeforces.com/contest/1307/submission/71322234
Nasty mistake is here:
s.size() is an unsigned type, as a result, if s.size() == 1, i becomes 4294967295 (unsigned -1).
You can't use s.size()-1 as s.size() is unsigned number.
I am sad for you :( Your bug is in the line 10, s.size()-2 will give you RTE, so you should have cast it first. I ran your code after fixing this and it is AC :(
Almost <3 Good luck !
jqdai0815 is insane!
*is
Can anyone explain this logic for the D problem
If you are referring to why your solution fails, see my comment.
One of my favourite contests now.
It is unbelievable that following code can not AC;
include <bits/stdc++.h>
using namespace std; int n,x,ans; int a[100005]; void solve() { ans=0; cin>>n>>x; for(int i=0;i<n;i++){ cin>>a[i];ans=max(ans,a[i]); if(a[i]==x){ cout<<1<<endl;return; } } // cout<<a[0]<<endl<<endl; if(x<ans) { cout<<2<<endl;return; } else { if(x%ans!=0){ ans=x/ans;ans++;} else ans=x/ans; } cout<<ans<<endl; } int main() { int t; cin>>t; while(t) { t--; solve(); } }
Don't paste solution like this. Give link for solution. Also mention the problem no.
As far i understand it is a solution for problem B which was failed.
The reason is you must take whole input when there is multiple test cases. Suppose you have array of length 5 and you get answer after taking 3 input you get the answer. If you stop taking input here then 4th element of array will be n for next case which is not supposed to do.
E tests the participants' English level.
Yes, it was a little difficult to word the statement concisely, but we felt the problem was too nice to discard for that reason. I hope your overall experience was still positive!
Many LGM dropped. :|
I don't understand how complexity of F is $$$n*log(n)$$$. The number of non-overlapping rest stops for a given node can be very large, and I have a concrete counter-example for $$$O(n^2)$$$, if I understand the editorial correctly. Can anyone please explain proof of complexity.
The number of non-overlapping rest stops for a given node indeed can be large, but only if we consider the distance $$$k$$$. But there is at most one group of rest stops on distance $$$\frac{k}{2}$$$ and the author solution uses this fact.
another D : 1016F - Проекты дорог
Poor tourist :')
Codeforces translators:
EDIT: Uh, it seems I was wrong. I can't comprehend how "giving food" is the only meaning of "feeding" I can find, but at the same time Internet provides example "cows feeding in meadow" or "baby feeds one a night" wtf?. Who is it feeding? I would use "being fed"
Do you think the authors from the USA wrote statements in Russian?