Unfortunately, due to Internet provider network issues, we have to postpone the round. The current plan, that the round is postponed by 24 hours, will start on May/05/2021 17:35 (Moscow time).
Hello, Codeforces!
<almost-copy-pasted-part>
Hello! Codeforces Round #719 (Div. 3) will start at May/05/2021 17:35 (Moscow time). You will be offered 7 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating 1600 or higher, can register for the round unofficially. The round will be hosted by rules of educational rounds (extended ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round, it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.
You will be given 7 problems and 2 hours to solve them.
Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.
Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as trusted participants of the third division, you must:
- take part in at least two rated rounds (and solve at least one problem in each of them),
- do not have a point of 1900 or higher in the rating.
Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.
The problems for this round were invented by MikeMirzayanov, Supermagzzz, Stepavly and Aris.
Thanks to Gassa, BledDest, Programmer, bugdone, ruban, RedAnt, songsinger and Gornak40 for help with testing the round.
Thanks to MikeMirzayanov for platforms and coordination of our work. Good luck!
</almost-copy-pasted-part>
Editorial is ready!
Most awaited round of the month.
wow how ironic now that the round is postponed.
My first rated contest pretty excited :)
First rated contest with a new Alt? :P
My first unrated div 3 :)
Everyone !! Did any Rating changes occurred I am unable to see any rating changes for me, So here I am asking ! -_-
Same here, and even it is showing in unrated contest in my profile
however I am on official standings
Can't wait for rating changes.
Until rating is actually credited/debited in your profile, Every contest is shown in unrated.
They just did another system testing. Wait for 2 hours now and hope no more system testings.
Tom's smile always kills me LOL : )
Tom's movements and expressions are best ngl xD
do it again,contest postponed :P
What about ratings. been staring at screen since morning
Sorry but I don't really understand the trusted rules :( Does that mean I can't use clones?
Div. 4 when?
What is div 4 ?
Does a contest always mean solving hard problems :)? Even a div. 4 contest with easy/tricky problems can be fun at times.
What I think is, coding is not always about solving hard problems, let there be fun.
I can't disagree, but what's the point of solving easy problems if they don't bring you any benefit, just a waste of time? is not it ?
I think solving easier problems(which we can solve faster), can be a really good warm-up.
Sometime when I feel dull, or like I am unable to perform well, I go for solving some easier problems. That really helps in gaining pace.
yes, agreed but most of the people asking for div 4 are generally doing it just in hope of positive rating.
nice argument
Funny calling him noob when he has a rating higher than you.
Why did you get downvoted ur saying facts
I didn’t call him a noob, I asked him
The power of the edit button
Really excited for my second contest , hoping i would cross 1000 this time. Any tips are welcomed. TIA
Enjoy beauty of contest, never think about rating and never go for cheating.
thanks buddy, really a well defined ans.
WTF! You solved 4 in Global round and still got a positive delta of only 600?
sed lyf bro.
how to become red coder in 1 month???? any tips and tricks???
Yes, just win every contest you step in and you'll be red within a month
Wait for January 2022, you will don't have to wait a month, 1 sec would be good enough. xD
why, what will happen then?
Magic!
Codeforces allow user to change the color of their usernames every New Year,it called "Magic".
Then, we see some grandmasters with 8000 rank LOL!
And they solved problem G
I became a LGM in January and posted on social media just to baffle my friends.
start in December and when new year comes, they will give you an option to change your color for few days. That's my secret of becoming a red coder.
yes, there are two ways either you paint your laptop screen with red colour , or solve 3000 plus questions in a month ,lol
Few years ago,when the initial Rating was 1500,LxL became gold only after three div.2s.
Becoming red in 1 month? Just go to bed and have a good dream. There is everything in dreams.
Hmmm, why aren't we seeing vovuh as a problem setter in recent div.3 contests?
Stepavly contests are like the old DIV 3.5, Vovuh DIV 3's were, indeed, a bit tricky especially the latter problems.
Hope to see a cool problemset. Best of luck, All.
As a tester I can assure you the problem set is cool :)
Also be sure to read all the problems. Setters often write this, but in Div2 I think most of the time the last problems are really hard. But for Div3 I think it's really worth doing it (at least reading the first N-1 problems in a N problem set).
why doesn't this comment has the number of upvotes it deserves.
Hmm note that testers are usually part of conspiracies. So the N'th problem could be the easiest, we should try to solve that first.
One more new author of div 3 *o*
Hope I become pupil again
I still remember the time when vovuh was a coordinator of Div3, it has been so long.
*has, try improving your grammar. Would really go a long way in interview preparation.
try not correcting others' grammar errors. would really go a long way in your interview process if interviewer's grammar isnt that great:)
please schedule the contest 1 hr earlier as it perfectly ends before dinner and good discussion time before going to sleep
You don't know how many time zones in the world, do you?
most of the contestant are from india i guess :}
Then...?
This request is the perfect definition for self centered.
...
Again, that's impossible. If you have good delta you have bad delta. If you have extremely good delta, you have extremely bad delta.
I can leave a message again Yea~
can i say that div 3 is the best training contest for who is less than 1600 rating and will be better if problem standard
Oh I thought, Div 3 = Div (1 | 2). lol.
Oh I thought, Div 3 = Div (1 ^ 2). lol.
It seems that the queue is really long......Can this round hold on time?
Verdict: In queue
There is a problem with submission, it shows the "In Queue" verdict. Wish this will not happen in today's contest.
Anyone else getting Bad Gateway errors lately?
Yes, I think there is a server issue on cf.
Hope this won't occur during contest , DIV3s are imp for beginners.
Notice unusual change in schedule.. :(
I think it's better to have a postponed rated round than an unrated round
(it doesn't matter to you as it is already unrated for you :D)
Delayforces!!! :(
It's been an hour since I submitted a problem. Still in queue :(
Yes! my submission is also in the queue. :(
um so how many registrations will this round have now?
Maybe 35K registrations ;)
The least they can do is to reset the participants so that there won't be another 30k contest and it becomes unrated, seems like no one cares about div.3 contests.
What do you mean by no one cares about div.3 contests?
It's my first time to see a 24-hour delay here.
But it is ok then a unrated contest.
Nooo :((
Peeporiot ;-;
Better delay than unrated :(
So,30k+ participants this time?
round is postponed, I was waiting and refreshing every 1 minute to see how much time left. sad life.
Since the contest was postponed, can you please open the registration again?
Div 3 — Let's rock today.
(postponed :{ )-
Let's practice today :}
can't even practice
due to long queues :(
due to Internet × wait until the registered participants over 30k √
I finished my talk over phone with bae just 5 mins before the contest only to know this... (Cry Emoji)
downvote this guy.
Yes please add salt to my wounds... Sadists
You doing the same to us.
All this time.. i was refreshing my browser..thinking issue on my side.
The round has been postponed- NO WORRIES
IPL has been postponed- CRY, CRY, CRY :(
postponed for 24 hours! I will never participate in a CF contest if this contest has been postponed again!
my exact reaction
Stepavly please enable the register button so that the people who have not registered and are the official trusted participants can register !! ** Thanks in advance ** !!
UPD : THANKS !! I have successfully registered now !
when I finish my dinner fast for the contest...
Unfortunately, due to Internet provider network issues, we have to postpone the round
.
you are genius bro!
and then 24 more hours for ratings change. I don't know whats there in calculating ratings that takes 2 or more hours.
Verdict: No Color! :(
Cf: Hmm you're mad because we delay the round for 5 min sometimes WEll How About 24 hours !! Muahaha
Really excited for the contest , hoping I would cross 1100 this time. Any tips are welcomed. TIA
Good luck to everyone!
when you heard the round was delayed
This will be my second contest. I participated in last global round and I still don't know how the score works perfectly. In that contest I think they gave me less points for a problem with previous wrong submissions. Here when it says there's a 10 minutes penalty for wrong submission, is it saying that I will lose 10 minutes from the total 2 hours of the contest for every wrong answer?
You are judged by number of solved problems, and penalty points. Foreach AC submission you get 1 solved problem, and the number of minutes from start of contest plus 10 minutes per wrong submission of that problem as penalty.
Thank you. I thought it meant I would have less time to solve problems, misunderstood that
i have a feeling that site may crash !!!!!
yes it has already started lagging.
Why on equal rank in div3 contest gives less positive delta then div2 on same rank. Suppose x rank in div3 will give less positive delta than x rank in div2 ?
coz having the same rank in a more difficult contest(since better rated participants are rated in Div2 contests, than in Div3) is better.
So , greater number of participation theory fails here!
Hope the contests won't get unrated because of long queue, we are reaching close to 30k , at this rate we might be reaching around 32k easily
Got It.
no score distribution in div3
It's starting finally: the most awaited contest since yesterday :)
Cheers Codeforces for 30K registrations once again!!!
my code is running from more than 10 min, i also tried to cout<<"HELLO"; but it also taking more than 10 min ; MY internet connectivity is good. i also tried to logout and log in
Is there any queue issue :( , my code is in the queue for last 20 minutes
It seems that my submission for G is executed twice, is this right...?
G has 100+ test cases wtf
On 60th and hoping, been 10 minutes.
And yet, even so many tests were not enough to cover incorrect TL solutions. (Lots of hacks)
Including my solution lol
you guys should give atleast some weight to out-of-contest submissions. It's not like everyone participates in div3 :|
;
THE QUEUE IS TOOOOOOO LONG I CANT STAND IT PLEASE MAKE IT UNRATED
got WA on test 1 after that !
Unfortunately, I got WA on test 2 not 1
After waiting for 4-5 minutes.
WA on test 1
Queueforces :(
No way this can be rated!
It has to be...you are slow.
Interactive is not good when long queue time is there.
This Contest should have been extended by 15-20 min to compensate for long queue
what if some people have work after it ? Extending round is always a bad idea. They can keep it for 15-20 min extra but it should be announced before the contest. for majority of people queue time didn't matter much and it was fair for everyone since everything was same for everyone.
Actually, there have been situations in which the contest was extended due to long queue. I think it wasn't a really smart choice to put >100 cases in G considering that both F1 and F2 were interactive, though.
I agree that people may have other commitments after the contest but extension has been done many times during some the previous Div 3 Rounds and extension gives relief in some sense . if you have another work just go for it , there will always be some contest in a week after it so you can make a comeback in it to recover your rating loss
I am eagerly waiting to see test case 5 of problem "D".
For me the trick was storing the frequency of the difference as long long.
I got wrong on test 5, then I changed my min=1e18 and it got accepted... :)
C,D<A<<B<<<E,F1<<<<<F2<<<<<<<<<<<G I know the number of solves indicate otherwise (difficulty distribution linear from A to G) But just look at the number of wrong answers and solution size.
Can someone confirm if problem G was dijkstra ? I just submitted it and excited if my approach is correct.
No. Brute force Dijkstra should TLE because the complexity is of the order $$$\mathcal{O}(E(G)) \sim 10^{12}$$$
dijkstra is O(ElogV) and not O(EG) if you use min priority queue
How is $$$E(G)$$$ not $$$10^{12}$$$? If you directly bruteforce from each teleporter you have $$$mn \sim 10^6$$$ edges from each node and so it behaves like Dijkstra on a complete graph which obviously exceeds time limits. I just dropped the $$$\log V(G)$$$ factor because removing that doesn't make my argument fail.
there is actually a better way to do this, you can add a dummy node to which you connect all teleporters (from), and then you connect the dummy node to all teleporters (to). So in this Case you only have O(E) edges
Sorry, but I don't see how that's an improvement in the complexity.
Like floki said, each cell has 4 edges going out of it (up, down, left, right), but also for each teleporter you add an additional edge to a dummy node (at most $$$nm$$$ more edges), and an edge from the dummy node to each teleporter (at most $$$nm$$$ more edges). So the total number of edges is at most $$$6nm$$$, which is reasonable but still hard to get to pass on this problem.
Google-forces
So, I waited 10 minutes to get a TLE on test 114 of G after the contest had ended already . LOL
I got TLE at TC-69
sounds kinky (•◡•)
Same problem as E
How do you guys get so much time to find similar problem in google during the contest!
Actually I didn't search I knew I had done it before
SlowForces
Waiting for this comment. In queue
WHAT A BAD ROUND!I must wait 8 minutes for the result of my submission.
I remember getting up for Kickstart round H last year, quite early in the morning, I think it was worth getting up. But not on that that day, its today, cuz problem E is literally this lol. Also Thanks to people like Galen, Ecnerwala, Neal, who posted solution to (problem E) that round that day. High rated people do have time machine xD.
F2 was an absolute bomb. It's been a while that I see such a beautiful problem.
Agreed, the rest of the problems felt very standard and paled in comparison to F2.
Depends on your solution... Mine was using something like SQRT decomposition and was really boring. But the intended soln is indeed beautiful.
Bad internet situation.
Problem B : https://www.geeksforgeeks.org/count-of-numbers-with-all-digits-same-in-a-given-range/
I forgot to delete a part of my code in F1 that I used to verify my solution, but since I was still in the queue I did not realize it, I feel very bad :(
same here i also face same problem in c i printed NO instead -1 :( when i realize contest is over :-(
yes, and the worst thing is that my solution was correct :(
Can anyone explain problem F2 and G?
F2: You can query each prefix of the array with step of 8 (that is, 1, 9, 17, ...) and store the number of zeros in it. Now to answer the query, you must first binary-search these prefixes (takes 0 queries), and then search among the remaining 8 elements using exactly 3 queries. Now what happens when we change some 0 to 1? Some suffix of our array with prefixes has to be decreased by 1. To perform these operations quickly, you could use a segment tree. BIT and sqrt decomposition should also work.
The total number of queries is t*3+n/8 ~ 5,5*10^4 < 6*10^4
IDK if this solution is the same as the author's one, but this one seems really beautiful to me.
G: Notice that you either don't use the portals at all or use them exactly once (since we can omit the intermediate steps). The variant without portals is solved using trivial BFS. About the case with portals: you first go from (1, 1) to a portal, then pay its cost, then the cost of the second portal, and then you go from portal 2 to the end. You can compute these sum of the portal's cost and the cost to go to this portal from (1, 1) and select the one which minimizes this quantity as the first one. The case with the second portal is symmetric.
For F2, you can break the interval into blocks of size 32 ([1,32], [33,64], ...) and query the number of 0s in each of them. This takes roughly 2*10^5/32 = 6250 queries. Then you can answer each k by finding its appropriate block and binary searching on it.
Each answer will require 5 queries, so we use at most 5*10^4+6250=56250<6*10^4 queries.
The advantage of using blocks instead of prefixes is that we only need to update a single block after each answer. Also, since we chose a block size of 32, we can directly iterate to find the block that will contain the answer (since 10^4*2*10^5/32 = 6.25*10^7).
My sqrt decomposition solution of F2 is giving wrong answer on test case 21 (queries limit exceeded). has anyone done using sqrt decomposition
for me, taking block size as $$$n^.5$$$ failed on TC 21, but taking block size as $$$n^.25$$$ worked.
thanks bro it worked
Taking block of sqrt(n) will not pass. In worst case with block size of n^0.5 length will be 450 and log of 450 is 8.8 ~ 9. so for 10^4 tests atleast 9*10^4 queries will be made.
It's helpful. Thanks !!
For G using k+1 portals is never more optimal than using k portals. Hence we shall use either 0 or 1 portal. let cost[i][j] = minimum cost to move from [i,j] to n,m using only adjacent moves. Now for each portal do cost[i][j] += matrix[i][j] and find the minimum cost to travel from a portal to n,m. Let this value be equal to min_cost.Now the answer to the problem would be minimum cost to reach from a portal [i,j] to [1,1] + min_cost + matrix[i][j]. Which is equivalent to moving from [1,1] -> p1 -> p2 -> [n,m]. Dont forget the case when you use 0 portals.
Please make this round unrated. Couldn't solve the problems on time due to the waiting thing.
It took 10 mins to get the final verdict to one submission.
Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600 or greater than 1600 or even equal, then the round will be un-rated for you.
Someone confirm I'm not blind, this was the sample shown for problem F2:
So this seems to imply that you have to read in a 0 after each test case, which is a thing that some interactive problems make you do. But not this problem. When I tried to read in 0, I got runtime error on test 1, and removing that worked. So did the samples lie to me?
The first '2' query (line 2) is actually the value for K for the first test case. It is only to be read, it does not correspond to any output line :)
Ah I see what happened, ok thanks.
In F2, There is also an input for 'k' after running for each 't'.
Please check this submission for F2 :- https://codeforces.net/contest/1520/submission/115329302
Task E : https://leetcode.com/problems/minimum-adjacent-swaps-for-k-consecutive-ones/description/
There should've been extra 10-15 minutes for such a long queue!
Not "such a long", it was less than 4 minutes u should say. Thats fairly normal considering the huge number of participant
In last 5 minutes, I faced around 7-8 minutes long queue! Considering every last minute matters, it was huge for me! Submission link: https://codeforces.net/contest/1520/submission/115324831
Site was down for the last few minutes.
Did CF copy almost every problem today?
B — https://www.geeksforgeeks.org/count-of-numbers-with-all-digits-same-in-a-given-range/
D-https://www.geeksforgeeks.org/count-the-pairs-in-an-array-such-that-the-difference-between-them-and-their-indices-is-equal/
E-https://leetcode.com/problems/minimum-adjacent-swaps-for-k-consecutive-ones/
Solving problems is faster and exciting then finding it on google! :)
Exciting- Very true
But any regular CP-er has already practiced these common problems and knows where they can be exactly found.
That's our weakness that we didn't practice those problems. Right? :)
If you have already seen those problems somewhere before then gj here's a candy
Let us (newbies) enjoy those quality problems.
also imo, adding classical problems in a div3 is actually a good idea as they are hosted to improve your skill not the ratings
but hey! you can switch the platform whenever you feel like ;)
Started the contest 15 minutes late, but still managed to get till F1 in 1 hr 30 minutes. My best performance so far, thanks for the round and hope it remains rated.
" Started the contest 15 minutes late "
lol, you made 2 submissions before starting, thats so cool!!
Anybody else think that solutions should be regraded for problem G with an easier time constraint? Maybe it's just java idk :P
frog ORZ FROGGY FROGGY
Can someone tell me whats wrong in this code 115328097
answer can be greater than INT_MAX. initializing mini with some bigger value should work.
If long queue would not have been there then I could have got F1 and F2 right in time.
Did someone got G?? I got WA on test-26
At least there should have been a 10/15mins extension of contest duration was needed due to the long queue problem. I just needed to change the answer from int to long long to get problem E AC. :(
I'm so stupid!!! I used INT_MAX as infinity value in problem E :(
"wrong answer 1st numbers differ — expected: '62517316129', found: '2147483647'"
same here !!!!
too many copy-paste problem :(
Did anyone else get WA on test case 37 for G? My submission if anyone wants to check it out.
My approach:
Do Dijkstra's algorithm, and find the shortest path to enter a portal (call it $$$P$$$). Then, run a multi-source Dijkstra's, with each source being a portal, and the starting distance to the portal as $$$P$$$.
In my code, the priority_queue stores
<-distance, pii{i, j}>
, and the distance is stored as negative, because Dijkstra's uses a min heap, while the default priority_queue<> uses a max heap.The dijkstra lambda function is just so that I don't need to copy-paste the code.
The portal variable stores the shortest distance to a portal.
Maybe the optimal answer may not contain a portal? It depends on how you wrote your code
That's not it, because I only update a node if it has a new shortest distance.
That's the purpose of the
if (dis[i][j] <= -d) continue;
code.Weak test cases for problem D. Disappointed :|
Nice problems, but really bad problem statement in F, especially F2, description is hardly understandable, and description of input simply wrong.
I am shown as +100, but would rather see it if it were unrated.
Also the queue was slow.
How to check expected rating change before official changes ??
download an extension
which extension?
It is called "CF-Predictor", should be available by google search.
I use Carrot, and it works really well. Idk why it's named "Carrot" though lol
Carrot is better than cf-predictor... (i used both)
Totally agree about F2
It is rather confusing to say the least
First there are too many letters to be easily comprehended. But that's not the only problem
For example at some point they talk about "requests", then there are "queries". You would think it is different things,
Then right after the description of the output format there is "In case of an incorrect query, -1 will be displayed" and you try to match with the format, thinking that maybe you need to read some confirmation code after you cout the answer because it is natural to think outputing the answer is a kind of query
Finally there is brilliant statement "Then t lines follow, each of which contains one integer k". I don't know about others but for me it means that at this point I can read t lines.
Yes, it is possible to figure out what was meant by rereading the samples and 1KB statement a few times or by requesting clarificiation, but I find it rather inconvenient. It is especially inconvenient when the server barely works.
Can someone please help, why is this giving TLE in test 3 ? 115323338 , 1520F2 - Guess the K-th Zero (Hard version) Thanks ! UPD: I got it, since I used RUPQ Fenwick tree I forgot to update(r+1,-v) when I update(r,v)
Not only the blog was almost-copy-pasted-part. But also the problems. Idk what did the testers do really test. And did not report for such well known problems.
I've just started getting the knack of codeforces. And I was able to solve A, B, C, D in this contest. But I was slow to think of the approaches and hence my rank is around 6k. Hopefully, I will get better at thinking fast about the solutions. If any tips that may help, please do tell me cause that would be great.
Practice
What helps me to solve problems faster is to get better at math, especially competitive math, because the easier math problems have similar styles to the first few problems in a Div3 or Div2. Also, solving Codeforces Div3's and Atcoder abc's (Atcoder Beginner Contest) was one of the biggest factors in my speed. Now I just need to improve on actually getting the solutions...
how to solve F1?
Binary search the answer. Let's say you know sum(1,cur), then if cur-sum(1,cur) (which is the number of zeroes in that range) is greater than or equal to k then you know that the kth zero should be in the range [1;cur]. Else if n-sum(1,cur)<k then the kth zero is in the range ]cur;n]. So binary search over cur. 115289534 PS: sorry for not using LATEX
Explanation for Problem F1
What is the intended solution for F2???
It seems that the author's solution is just do binary search every time and avoid query one segment twice.
But there's another very beautiful solution that divides $$$1$$$ to $$$n$$$ into blocks of $$$8$$$ and use data structures to maintain.
What is this technique of division to 8 blocks called?
It's not a common technique.
That solution is only used for F2.
It's kind of a sqrt decomposition, but it's better to use $$$8$$$ (or $$$16$$$, or $$$32$$$) instead of $$$\sqrt{n}$$$.
I maintained blocks of 32 and each time just iterated through each block until the total zeroes greater than k. Finally a binary search on the block
That's the solution i mean.
Iterate through each block is about $$$1e8$$$ so it can pass.
Suppose there is a full binary tree with 18 layers, total nodes are (2^18 — 1) > n. We use this tree to do the binary search.
So the problem is, the start node is root, find k end nodes, is it possible to cover more than (6 * 10^4) nodes?
The optimal method is to make the k end nodes on the leaves. So the maximum covered nodes count is min(2^17, 10^4) + min(2^16, 10^4) + min(2^15, 10^4) + ... < 6 * 10^4. So the answer is no.
We can do the binary search with simply cache to solve this problem.
Can someone help me figure out whats wrong with my code for F1: https://codeforces.net/contest/1520/submission/115338765
It gives a weird error for test case 2
How to delete this comment.
'0' initially stands for string it will be hidden for us so its length would be given, read the test case as 1(length of the string) 1 1.
Ok , now i get , it was not the input that i was getting from the grader , i was thinking that is the input that i was getting from the grader initially.
Could you explain again please? I didn't quite get it sorry
I initially thought that , the input section of test case is same as the input that we will get from the interactor. I was saying now i understand where i was wrong.
Now as for your initial question , intially you are quering with the indices as 1 and n/2 , but what happen when n was 1 , you will get 0 as a result of n/2 (integer division) but index zero is invalid in this question because indices start from 1.
Ah i see... Thanks Silly mistake cost me again
.
Normally people who had a bad contest, always ask for unrated, Its their habit
The solutions were already available online, this is a major point for making the contest unrated
.
Interactive problem in cf == Binary Search
Not always: https://codeforces.net/contest/1504/problem/D
HackForces (+51 successful hacks)
Can anyone share a python solution that can pass problem G? All python solution are either failed or being hacked.
For what problem?
G
Just wait for pajenegod to AC it. Until then it's unsolvable in python.
There we go 115352307. Definitely wasn't unsolvable.
Is it only me or anyone else who found E way much tougher than number of submissions of it during contest?
It was a classical question I think. Most of the people have already done some similar kind of questions which involves taking median as a optimal strategy.
bruh taking median is not optimal strategy i brute forced on all possible groups such that groups on the left are joined to this group and groups on the right are joined similarly and took minimum of all
Yes your method is also correct. But taking median of indexes of all the sheep present initially to be the median of newly formed group works here. You can check my submission[submission:115335739]
Its super easy dp. Sorry for my english
123 pretests for G, still got hacked :(
When will the ratings be updated?
How does hacked works here? Can anybody explain. Thanks.
The standard tests are not always perfect and may miss some problems in the submitted solutions. Your solution for problem D has a bug, because
arr[i]-i
may be negative and sobrr[arr[i]-i]++;
results in accessing memory outside of the array bounds. Someone noticed this flaw and submitted a new testcase, which triggers this bug in your code.The text for 1520F2 - Guess the K-th Zero (Hard version) is very misleading:
This is a hard version of the problem. The difference from the easy version is that in the hard version 1≤t≤min(n,104) and the total number of queries is limited to 6⋅104.
and adding this to the end of the problem:
To make the game more interesting, each guessed zero turns into one and the game continues on the changed array. More formally, if the position of the k-th zero was x, then after Polycarp guesses this position, the x-th element of the array will be replaced from 0 to 1.
Thanks for the problems.
My rating is only 386. Why it's unrated for me?? Tell me, please.
What makes you think it is unrated for you? You are on the leaderboard, it is rated for you. Dont Worry
I think that round should've been extended, due to long queue a lot of people lost the time waiting the submission verdict.
Can anyone explain why this code is giving TLE on test 125?
It's taking a long long time for system testing.
The simplest solution for problem C according to me is just print all odd numbers from 1 to n^2 and then print all even numbers. And for n = 2 it is not possible.
I did the same :D
I submitted the solution of problem B during the contest and the verdict showed me accepted. Now in my submissions list it's showing that my solution is still in queue. How it is done please someone elaborate, I'm new here. This was my second time participating in any contest.
System testing is carrying on now. It will execute all submissions again. You just have to wait until the system testing ended.
Hello!
I've submitted 3 solutions for F2 with C++17(64) and C++14, but it kept on giving me "in queue", did I do anything wrong? I tried to submit another problem with C++17(64) and it worked correctly.
Here are my submittions: 115402170 115401934 115401509
thank you!
UPD: It's fixed now, thank you!
Is the contest unrated ?
Why haven't the ratings been updated yet? It's not like the contest has been made unrated: there's no official announcement.
when there will be a change in ratings ?
when will rating come ?
I have a rating < 1600 but somehow i didn't get rated for this contest.
just wait for it, nobody received the rating changes yet
Felt unpleasant for G -_-#
I suppose it will let solutions with correct time complexity but huge constant pass ......
I need to use
-Ofast
to pass with time 2994ms ......Is the round unrated?? If so then atleast give an announcement. People are waiting since yesterday
its not the good thing that now above 20 hr completed after round start but ratings are not yet given
You can use CF-Predictor. If you not cheated and the round is rated your rating change will be approximately the same as CF-Predictor says. Don't worry your rating will be up today.
for unexpected queue i coludn't find my wrong for problem F1 otherwise I could solve it
System testing is happening again. Isn't it already happened 2-3 hours ago?
I think it's happening again because all the hacks weren't processed by the time previous system testing happened.
testforces
If the round had to be unrated they should have announced during the contest ,so now its confusing seeing the contest in unrated section xD
Dream has reached the goal [The System Testing...Again...]
Hopefully, they finish System Testing before tomorrow's round :(
Why are sources evaluated that many times?
The first system testing forgot to add hacking testcases,so they have to test it again...
Again system testing!!! I am eagerly waiting for the rating update.
Me too...
Will we get three times the delta as well :p
Contest 1 days postponed:....:
Rating update : Hey I am following you contest
System tests have finished.....**FOR NOW**
Is it rated?
yeah, just wait for rating
They have performed system testing twice. Obviously, it's rated but probably there's some technical fault in testing procedure today.
Ratings aren't coming because there are still some codes in the hacks section IN QUEUE
They are in queue from last night and still its going....
.
what does this mean +40 in delta section it's showing for 2-3 minutes and then going off
It means your rating can go up by 40.
Your change also visible?
Yes, The ratings are updated.
My solution for D failed system tests, I can't seem to find the bug in my code, can anyone help? I tried the same approach as in the editorial
115278462
a[i]-i could be negative .. you have to use a map or shift all elements +n to make them positive
Gotcha, Guess I should've paid more attention, Thank you!
115437739
Hey MikeMirzayanov! Can you please check these 4 submissions? 115269387, 115321811 115286392, 115315037 I think it's obvious that these two contestants are cheating and the system did nothing about it!
How is the rating calculated?
Can someone tell me why I got a 'failed system test(tle)' using trivial BFS for problem G? And the same code got an AC just by using a different compiler. GNU C++11 998 ms AC: https://codeforces.net/contest/1520/submission/115447927 GNU C++17 (64) 3000ms FST: https://codeforces.net/contest/1520/submission/115322035
Upd: The same code passed using fastio. I dont think it is good to enforce user to use FastIO for a div3 round. https://codeforces.net/contest/1520/submission/115449785
Me too bro, I use Ofast to get pass ......
Just fell upon a question very similar to q4 of this contest-- https://codeforces.net/contest/1398/problem/C