Hi everyone!
I would like to invite you to my fifth Codeforces Round, that I set with my friends FastestFinger, Vivek1998299 and ridbit10.
We are excited to bring another contest within a week :D
With that said, I bring to your attention our new Codeforces Round 648 (Div. 2) that will take place on Jun/07/2020 17:35 (Moscow time). If your rating is less than 2100, this round will be rated for you; otherwise, you can participate out of competition.
I would really like to thank:
- FastestFinger, Vivek1998299 and ridbit10 for helping with preparing problems and giving new ideas.
- 300iq for coordinating our round.
- Um_nik, antontrygubO_o, ksun48, Jeel_Vaishnav, aryanc403, Savior-of-Cross, KonaeAkira, _Aaryan_, Ari, Devil, lavish315, AmShZ, Shuba_Buba and smartnj for testing the problems.
- the_hyp0cr1t3 and BarseSnow for testing as well as proofreading and making suggestions for the problems.
- MikeMirzayanov for Codeforces and Polygon platforms.
You will be given 7 problems and 2 hours 15 minutes to solve them.
Good luck! :D
The scoring distribution will be: $$$500 - 750 - 1250 - 1500 - 2000 - 2500- 3000$$$
Upd: Quick Editorial — Hope you guys enjoyed the contest :D
Contest quality certificate by antontrygubO_o.
When I see this blog, I thought Mike already made you coordinator
Oh Yeah! Here we go again...
Meanwhile antontrygubO_o with this comment.
.
<tester's-comment>
As a tester, I found the problems diverse and very interesting to solve. I think this is will be a fun round for many. Participation is recommended :>
</tester's-comment>
I second this, problems are genius
Usually I would upvote the announcement after the round but this time I will take your word for it. Legendary lineup for problemsetters
BG
What's a BG?
Best Guy , Arsenal_FC knows better
As someone who is neither a tester, author, coordinator, friend, or involved in the preparation of this contest at any level, I can confirm problems are genius.
So I guess "genius" is a keyword!
Monogon when will you host your next round?
Your first round was genius, although it was destroyed due to long queues :(
may be the fastest scoring distribution ever
If this is the fastest score distribution ever then what's about Codeforces Round 639 (Div. 1) which was written by Monogon !
Deleted
Ah, shit. Here we go again.
This blog is still not in home page, I wonder what happen after couple of hours :P Comment box will be flooded with those "proud" comments like previous round xd
Ah shit. Here we go again!
plagiarism detected :P
Yes that level of spam will happen here xD
Definitely, I think I will come back every few hours just to look at the comments lol XD
Hahaha, honestly didn't notice this.
I just thought it to be an appropriate meme to comment, so I did. :)
Btw, why will I farm contribution even after this? :)
I did not want to accuse you of plagiarism or contribution farming. All I was trying to say was, the recurrence of "Ah shit here we go again". aaargh. nevermind. All fun is lost when you have to explain the joke.
i dont know why but whenever i read this line anywhere Gta San Andreas music sound starts playing in mind
Seriously your dream was having 2 Indian rounds in a week ? Congratulation in that case.
If that is the case, why not take a div-1 round in parallel with 3 shared tasks (Div.2 C, D, E) ?
They need to get Div1 D,E,F then. Which is not easy to make
They already have 7 problems. Both Div-2 and Div-1 would have 5 problems each with 3 shared.
That fits the contest problem-count wise. But what u are asking for is making the last 3 problems of div2 (which authors think are fine for div2) to last 3 problems of div1. They obviously won't be difficult enough.
I have solved C, D, E. I am not at that level so I can solve Div1ABC, so for Div1 this problem would be very easy.
I regret saying what I said. He said the tasks would be interesting for Div-1 users so I thought that maybe they would be hard. Turns out it was a speedforces with an easy F..
Is it just me or are others too wondering where Ashishgup and friends have been during the last few months?
Easy. Busy with his GF.
Oooh! But are you sure? I wrote "Ashishgup and friends".... They're all busy with his GF? ;)
ridbit10 was busy with some other girls.
Can you not pls
How do you know? Were you there?
So many problems to solve on codeforces and in life, but people have to worry about who was where with who, why and when. Human Brain is so damn weird.
XD
Was confused how did the comments from last Ashishgup's contest announcement changed only to find out it was a new contest XD
goodbye rating.
But it will be tough for everyone so it should not affect your raking as it is relative, what was the point as if it is only tough for some, not all
I'm so tired and sleepy right now that I read it as..
You will be given 2 problems and 7 hours 15 minutes to solve them.
everything is possible:)
Why is this blog still not on the main page yet?
I want my daily dose of cringe (from the proud Indians in the comments) and i cant wait any longer!
You're looking for quality cringe in the wrong place. Better search TikTok for quality cringe.
Pretty sure i am at the right place looking at the comments on the last blog by Ashish and some comments on this blog.
Edit — Turns out, not wrong at all. Here we go again — https://codeforces.me/blog/entry/78406?#comment-637124
That comment actually looks sarcastic
.
Wait what? How does Ashish come into the picture? I am talking about the cringy Indian comments on his blog the last time around, and it has no relation with the points you are making.
Improve your comprehension skills, and have the courage to put your name and college on your profile.
PS — I am proud of Ashishgup on what he has achieved, being his wingmate and batchmate for 3 years and watching him grow was a pleasure. So sit down, online troll.
that C looks hard
Thanks Ashishgup and Team For this effort.
We are also excited to see another contest within a week :D Thanks
I hope after the contest Ashishgup will be one the top ten contributors(as he has +155).
[deleted]
are chill it keeps happening
Can be before the contest also as he is much like Indian code celeb.
[retracted]
[retracted]
It's just a downvote. Don't take it too seriously.
If someone holds the record for most downvotes i want to beat that.
Did you just use "reverse psychology"?
It didn't work
Yeah it didn't work .
Ashishgup be like : "yalgaar ho"
Does that score distribution mean that it will be a speed-forces? With an easy D?
no speedforces with an easy F
Eagerly waiting for the div 2 A. It was pretty nasty and amazing at the same time, the previous contest by the same authors.
Also this time we expect memetorials.
CF-Community
"We are excited to bring another contest within a week :D" Cool.
Truly said — I become more excited when I see the score distribution like this way..
Is score distribution related to the rating of the problems ?
Since you seem to be an old CF contestant, this question is a little bit of weird!
ohh god..once more contest prepared by[user:Ashishgup]...amaizing previous contest #646 ...does anyone remember "Guess The Maximums" problem ?... a very tricky one...hope to see more good problems this time also...
Back to back Ashishgup rounds, nice :D. You are a nice motivation for me to prepare nice contests.
I'm so curios, how many hours a day you spent for your contest? And so, how many hours it took to prepare this one?
Can i please test your next round?
Hi! I estimate that it took us an average of $$$2$$$ hours per problem to come up with it, and roughly the same amount of time to prepare it on Polygon :)
So around a total of $$$4$$$ hours per problem
@Testing, sure! We'll invite you to test our next round :D
Wow man, you guys have FastestFinger s, it took about 40hours for me to prepare my problems (probable because i checked everything 4-5 times at least). Thank you ^-^.
That's the case!!! You have to give good enough time to make balanced contest, with 2 hour you make E sillier than A,B.
DeadlyCritic Hey man,
Are we expecting a Div 2 round soon for the problems which you prepared?
Probable . . .
Can somebody please tell me what information can we infer from the scoring distribution?
You can sort of guess the relative difficulty.
Please make a contest like last time.
.
Namoosan vote up konid
Translation(not that much accurate) : Vote up FFS.
Sick mind man :/ — But something like that :)
MikeMirzayanov- I think you are about to add another standing to CF's home page called most hated users. — You know, every single comment of mine is disliked for at least 30 times by default — And also CF has blocked me from commenting twice :) — However I'm too polite :/
To find most hated user on last page of Contribution Standing
6 years back a visionary leader by the name of Honorable Narendra Modi democratically became the prime minister of the world's biggest democracy. His vision of Digital India to transform India into a digitally empowered society has certainly lead us to this proud moment where an Indian becomes the first person to hold 2 rounds within a week. Certainly its a proud moment for all the Indians on codeforces today. So excited...Jai Hind !!!
Just Shut up.
bi adab shodia :)
As a fellow Indian, I request you to pls stop posting cringe content on CF. It only degrades everyone's opinion about us
This was cringy af.. to the next level..
I'll take that as a complement.
Indeed. The best thing a quality cringe provides is the firm belief in itself. You embrace it and take everything said to as a compliment. Thanks for THAT quality of cringe. Now I'll make myself believe that I indeed gave you a compliment and then replied with a greater cringe just to show you what cringe of the first water can do to someone. No Offense.
P.S. I think I failed with the quality of cringe but nvm.
Wow, I didn't get that but I liked that.
Wow, I didn't get that but I liked that.
I feel the exact same when I read the explanation and code of some F or G.
Lol. I'll suggest writing down an array and trying the shifting operations. Understanding how it can be done in 3n/2 operations is definitely difficult, rather first try to understand if it can be done. For G, initially don't think much about what a submask/mask is (those words are heavy and intimidating for me too). Just try to think about what bits are different. In the last part, they have said about using 6 bits, which might further intimidate you. But if the explanation were to be more complete, it isn't that difficult to understand. The reason is that there are 13C6 numbers which have 6 bits on and no two could be submask of each (note that the submask thing is necessary only for the second approach, not for the suboptimal one).
Welp.. I think u took it too far.. But thanks tho.. ur explanation is GREAT and I'm looking forward to solve that question with this. (y) Cheers mate!!
But what I meant there was just an analogy to SOME F and G :)
Have a good time. X
Oh lol okay, no problem. Have a nice day, you too.
.
Cringe on CP platform is just something to be cherished. Cannot find it anywhere else!
we dont't do andh-bhakti here....(Indians can relate)
Damn. The bhakti is strong af. Never knew we had middle-aged Indian uncles joining CF.
Never knew we had dumb kids who cant understand sarcasm joining CF.
Nice Score distribution .
Excited for the Indian Round!!
The scoring distribution makes me happy and afraid at the same time!
Contests of Ashishgup always offer really good graph problems!
Ashishgup is now in top 10. Great!
Is there something wrong with problem's div1D checker? I got AC, but when i look at test logs i see stuff like this in several tests
82738980 -> link to my submission
It's okay. The relative error, which is $$$|1 - \frac{pa}{ja}|$$$, where $$$pa$$$ is the participant's answer and $$$ja$$$ is the jury's answer, is indeed less than $$$10^{-6}$$$.
[DELETED]
.
That's a truth...
Congratulations to Ashishgup.I think you are first Indian to be in top 10 in contributors in code forces.
Not the first time for him.
He was among top 10 contributors ~19 months ago.
Шутка смешная, а ситуация страшная.
How is contribution calculated , i mean Ashishgup has +162 and BledDest has +126 ,But BledDest has authored many contents than Ashishgup
https://codeforces.me/blog/entry/8963
awoo takes most of my contribution for rounds' announcements
is it rated?
nah
Of course not. No contest in the history of Codeforces has ever been rated.
Is it only me who feels that 1st question is comparatively difficult to other Div2 contests when there are Indian setters!
Hello, MikeMirzayanov my net connection got lost. So, I can't compete now fluently. Moreover, I have submitted A and B. Please make the round unrated for me
What you want ,, Actually not possible .. Many people also face this problem regular .
"Hello, MikeMirzayanov,my girlfriend broke up with me in the middle of the contest.So,I couldn't concentrate. Morever,I have submitted A.Please make the round unrated for me."
If he replies,please forward my message too.
come on, scarlett is not a pedo!
It takes a rating of 1800 just to understand your comment.
or
A genius like me.
shahil_005 is neither.
People call this a burn,but the contest has already blazed me down completely,Your efforts are in vain,So sorry(Sad Reacts).
The world needs more people like you.Take a upvote.
But monica is ♥‿♥
wtf do you mean Richard, with the fancy moustache?
Ashishgup you should stop making contest. Your constest aren't good at all. It contains very weird questions. Please codeforces don't let your status go down because of them. Many people registered for the contest but a lot of them just backed off. This is sad. Your Div 2 problems are interesting but it doesn't qualify for the real contest maybe a unrated one (practice round) would be better. :)
Div. 2 contests are targeted towards somewhat experienced programmers. If you feel like div. 2 is too hard for you, there's no shame in starting off in a lower division. I recommend participating in the division you can comfortably solve at least 2 problems during a contest (if you want some challenge) or the lowest division that is still rated for you.
Regarding practice contests, you can always participate in old contests virtually (basically a simulation of the real contest) or just solve old problems until you feel like you are ready to take on div. 2.
I am seeing Experts with 1800 rating and CMs not being able to solve A in my friends list. While the entire contest may be good, A is certainly overkill for a div2.
Personally, I have not been able to solve a single question till now. While I cannot claim to be good at CP, I have generally been able to solve AB in div2 at least.
A is not overkill. its just difficult and require more logical thinking than other As. What is the point if all the Div2 As are cakewalks ?? sometimes its refreshing to see questions which are just not speed test and requires you to think for some time.
Sorry, but contest was too easy for div2, i think it's div3 level. if u cant solve so easy problems u should just practice a much better
Hi!
Unfortunately, CF-Predictor may not be able to handle as many contestants/users as we have today. I have an idea for the optimization that should resolve the issue, but
If the extension or usual website (http://cf-predictor-frontend.herokuapp.com/) go down today, feel free to use another replica
This round sucks!!!
Wired Contest. I can solve ACDEF, but just can't solve B.
The trick is to notice, that you can get any sequence, if you have both kinds of b (0 and 1).
You are right. A simple '0' or '1' could change a lot.
Do we also swap value of b[i] ?
Yes.
This round will teach most of the new comers that logical thinking is the first step in competitive programming, not the knowledge of all the data structures and algorithms. The first thing you need to develop is logical thinking. The one contest comes where you need to think instead of use some tricks or data structures, do not complain about the lack of it. Logical reasoning and thinking is an important part and should be treated at such.
Also the problem difficulty is increasing uniformly, which has somewhat become rare in recent contests. Kudos to setters !
.
Can someone tell me whats wrong with following logic for D ?
I take count of bad and good and if good person are zero, answer is always yes.
If bad persons are zero, check if all good can reach the end or not.
Now I check if any Bad person has a good person immediately next to him. If yes, then they cannot be blocked and answer would be No. If all the bad persons can be blocked, I block them and then check if all the remaining good persons can reach the end or not.
Any idea what I can be missing ??
WRONG EXAMPLE
This is an invalid example, because the statement says 'It is guaranteed that the cell (n,m) is empty'
Yes thats what I also did and it passed pretest. I block by putting wall on 4 side of B.
Your idea is right but you did something wrong on implementation.
dx
should be{0,0,1,-1}
.Oh thanks. :(
You have to block all neighbours of bad persons also. This is clearly necessary, and we can prove it is sufficient.
Maybe you made the same mistake I did. I didn't notice that if a cell has a bad person then you can't block that cell.
After E:
.
.
After knowing E solution:
How to solve E??? I know maybe it uses greedy strategy, I tried something with choosing numbers with highest bit set and then choosing atmost 2 more, just random submission. So someone give a subtle clue please!
Just choose maximum or between 3 vals.
There always exist an optimal solution with $$$k <= 3$$$
$$$n = 1$$$, ans = $$$a[0]$$$.
$$$n = 2$$$, ans = $$$a[0]$$$ | $$$a[1]$$$.
else ans is triplet with maximum or.
Can you show example when we need triplet, not just maximum element?
If I understood you correctly.
3
1 2 4
Oh, maybe I misunderstood the question. What output will be for this example?
Should be 7 which is the OR of the 3 numbers.
But we can just take the k = 1 and sequence {4} for this example, and we get the same answer, no?
I think you misunderstood the question. If we take just the 4 answer will be 4.
In the case of 3 numbers with "independent" bits, like $$$2^0$$$, $$$2^1$$$, $$$2^2$$$ it is optimal to choose all 3.
How to find the triplet with maximum or?
Brute force, O(n^3)
Umm, then I want to die.
This don't pass.
Why do you call f(y)? Just use y as is.
Oh god, I'm stupid.
You where more near to the solution than me ;)
the best way to make a set is using K=3 or 2 or 1:
if u choose 3 number and trying choose 4th number to change anything, 1st 2nd or 3rd must constain some bit that u find in 4th number. but u already have this bit, so u dont need k > 3
Oh my god I was thinking about that max(1, k-2) condition and choosing 3 but thought $$$n^3$$$ wont pass. Maybe it can be done in $$$O(n^2)$$$ but I get your point, nicely said.
O(N^3) will pass
Mine did not :thinking:
I looked at your code, you should simply have used or operator
|
rather than looping over 60 or so bits! I guess that lead to TLE.Yes :facepalm:
Oh yes you are correct I calculated operations as $$$500^3 \times 64$$$ (64 for the bits of numbers) but I think its not like that
to don't get this mistake again u can calculate time of work (kinda), if u have n'3 with n = 500, code will make 1,25 * 10^8 operations. we have very weak operations and c++ can make 4 * 10^8 of weak operations (if u use pragma u can reach 10^10 op.). c++ can make 10^8 of big(idk how say it) operations (like n log of segment tree). => u code will pass the pretest in this problem
why is this true?
What is the solution for G?
Assign id to each position such that all ids are distinct and for each $$$id(i)$$$, there are exactly $$$7$$$ 1-bits. Since $$$ncr(13, 7)\gt 1000$$$, we can assign the ids to every position such that $$$id(i)\lt 2^{13}$$$.
We can then do $$$13$$$ queries. The $$$i^{th}$$$ query will contain position $$$x$$$ if $$$id(x)$$$ & $$$2^i$$$ is not equal to zero. Let's store the query answer as $$$val(i)$$$ for the $$$i^{th}$$$ query.
For every pair of $$$i, j$$$, since the ids are distinct and all ids have exactly 7 1-bits, $$$id(i)$$$ will be different to $$$id(j)$$$ for at least one bit. We know that the answer for position $$$i$$$ will then be, or-sum of $$$val(x)$$$ such that $$$x$$$ & $$$id(i)$$$ equals to zero.
any hints for A and B?
For A
take all the rows and columns which are all zeros.
now whenever you make a move, one row and one column is reduced. so the max number of moves possible are minimum number of available rows or columns. That numbers decides who wins the game.
For B
If there is atleast 1 element with b_i 0 and 1, you can always sort the array. Other wise check if it is already sorted or not.
Can you sort this test case by your approach ? 3 2 1 0 1 1
Swap 3 and 1 since they both have different b_i values.
The worst round i've ever seen. ABEF — is like A, but many participants can't solve just because it's E,F and can't be so stupid. ABEF is much easier than CD (bcs here u need some brain)
Exactly!!! Again disappointed with this guy!
I solved C faster than A and B. But got stuck in E, was not able to see the simplicity.
I got two WA in A and one in D -_-
Nice problems!
May be Fastest Editorial overall ..Thanks
Took me 6 attempts to realize.. Just one dfs call was required in D. facepalm
Great round! Excellent variety of problems. Finally doesn't look like mathforces/bitforces and real algorithmic round.
Though I did not give this contest I can tell that this is the best div2 round ever.Ashishgup orz
Definitely one of the best rounds I have ever participated. I really enjoy these problems which emphasize the process of thinking and proving special properties, instead of the boring implementationforces.
F was so easy for me, and was a 2-liner, why was it kept before E? I would've got F much earlier but I couldn't get E and so went on to G as it was interactive, and read F only at the end of the contest. So unlucky :(
WTF was testcase 38 in F?
I think in that we needed to check that array a and b are actually permutation of each other, i.e. no extra element is present.
No
My solution also failed at test 38. I was using a set. Got AC by changing it to multiset
that's what I suggested in comment above from 6 hours before your :-)
Was G something like there are only 63 elements we care about at most so pick random subset of half the remaining elements to narrow down where it could be? Only other idea I had was parallel binary search but couldn’t narrow down past 20 queries with this
Yep, i guess it should work, i was trying to code it but unfortunately i couldn't come up with a good implementation, so i ended up with half of a spaghetti-code.
I have an idea, but couldn't implement it in time. Here it goes:
Idea is similar to Hamming code.
Queries are like this(blue means queried, white not queried)(every line is a query):
You can see every position has covered by unique combination of queries:
$$$p_i$$$ would be equal to AND of these queries
Right this is the parallel binary search I mentioned. I actually don’t think you can do better than 20 queries with this method, but I could be wrong. One way to describe your queries is that the i’th query contains all elements with the i’th bit set to 0. I think the problem is that you only get information for the entries that you didn’t query. So if the first element has a lot of unique bits then they won’t be detected ever, I believe. So I think it is possible to create some adversarial cases that force you to use more queries. You might be able to prevent this through randomization, but not entirely sure.
You are right, other entries can mess with answer, thanks for finding the mistake
Nice contest. I enjoyed solving all :p
why the downvotes?
No idea
Hey nice problems, thanks!
But one suggestion. In A text goes like "...and does not share a row or column with any...".
The usual wording is more like "Does not have a row or col in common". The word "share" is most of the times used to denote borders of cells next to each other. Since as a problem that would make sense, too, it is missunderstandable.
Guess who wasted 1 hour interpreting the question like that?
You.
My whole contest got fucked up due to that. It mislead me that they do not share a common edge. Now i realised he means that cell(i.j) can be occupied if and only if ith row and jth column is unoccupied.
And the edge problem is much harder... ;)
You can always ask the problem setters to clarify during the contest.
I you missunderstand something you can not ask, because you do not know that you did missunderstand it.
Bro how can i know if i would have known i could have solved other way around. I know about this feature i knew if after i read editorial.
Both phrases are synonyms of each other. It is mathematically correct to use either.
Yes, of course it is correct.
How do you downvote an announcement after upvoting it :-/
Make new account and give Downvote .. But I think, this contest does not deserve downvote .
I really liked the problems, nice job Ashishgup, indeed it was never a normal div2 round, i think they were very nice for IQ/creativity test. They were like problems in first round of Computing Olympiads in Iran, but indeed they were way harder. Thank you all(authors, coordinator and etc) for such nice problems.
Statement of A could have been more clear else i like the contest
After a lot of wrong answers,the pretest passed in last 12 seconds for D xD
may be swap(A,B) better ..i think B is more easy than A.. :3
Adhoc Forces How to downvote an announcement please say
Observation Forces I'd say
Ya every problem involving a lot of observation Observational Problems till A and B are OK but when C and D and E involve it then it becomes shit ,hope setters in fututre will keep it in mind!
The what, so all div1 contests are shit because their DEF div1s usually involve a lot of observations and that should only be limited to AB div 2s instead?
Can anyone explain E for test case 2 1 1 4 1 8 how can we get 14 , if i take both 2 and 8 there will be 3 ones which don't have their 2nd and 4th bit-set so how is the condition "at least max(1,k−2) (max(6-2,1)=4) elements of the subsequence have the i-th bit set in their binary representation" is satisfied for the 2nd and 4th bit?pls explain
choose the triplet $$$2$$$ $$$4$$$ $$$8$$$.
0010
0100
1000
bits with i = 1, 2, 3 can be taken since they have atleast a one in their binary representation and since k = 3, we need atleast just 1 bit so our answer will be 14.
Take 8, 4 and 2. Then k = 3.
k is the length of the chosen subsequence (k = 3), the length of the main sequence is n (n = 6).
Nice problems! Sorry to bother, but could someone please help me understand why I got a runtime error on prob A pretest 1 82790397? I see nothing wrong with it, also it runs fine compiled on my machine. I ended up rewriting the code in python to make it work. Thanks
I think it should've been "col(m), row(n)" instead of "col(n), row(m)".
(Since vectors reserve a bit more space than you asked for to allow amortized O(1) pushback, making this mistake doesn't necessarily cause a Run Error (I think), that could be why it worked on your machine but not on the server.)
... aaaand you are right. Embarrassing mistake. Thanks a lot for checking!!!
Problem E i submitted it using DP with 500*3 instead of BF (500)^3 but it gave me WA on TEST 6 can anyone explain please the code
Nice problems but I feel like the difficulties (from problem to problem) could have increased a bit faster — with such small increases it felt more like Div. 3 to me (that is, more stressful than Div. 2 due to needing to solve more problems to stay in the "positive rating change"-range).
Problem D video editorial: sOlUtiOn
My idea for the solution to D is check if the bad guys can reach the end, if yes, then block all the neighbouring cells. Then check if all good guys can reach the end. Why does this fail on pretest 7?
Link to my submission : https://codeforces.me/contest/1365/submission/82872417
If there is a bad guy in a neighbour of the destination cell, then your code is blocking the destination cell. In such cases, if there is a good guy in a cell reachable from the destination cell, the answer should be "No", but you code prints "Yes". See this case for example:
There's a typo in my code. That's why it fails. But for your case the answer is YES right? because you can build a wall above and below the bad guy.
Yes, for this test case answer should be Yes.
A request to future problem-setters, please try to break a long sentence into several sentences. For example this one:
Yep for the first 20 mins I was like I need to do summation of 2^i for each element or essentially the sum
The whole contest gets ruined if the first problem does not go as planned and the statement was quite misleading. I solved the whole time considering border should not be shared for each cell. Even any announcement was also not made to clarify the statement. Is it enough reason to make round unrated as a lot of participant wasted a lot of time on this which was rather a very easy problem ? PS — I completely understood the problem only after reading editorial otherwise it was a mystery to me.
There was nothing misleading in the statement. It was written that you can only claim cells which do not share a row or column with any already claimed cells.
There was no announcement, because there was no need of an announcement.
C-Constructive
Does failing on sample tests counts for penalty??
If not then for me, It's showing 3 penalties even though one of the wrong attempt is wrong answer on pretest 3 (last sample case)
I think only test case 1 is counted out of penalty.
No hacks at all in this contest O_o
Ashishgup contest exist !
For those who didn't solve, you just had to go through all the possible triples (x, y, z) and look at the maximum among x | y | z.
I hope for a div. 3 round before the next educational one or in place of it. Anyone agree with me?
Very nice problems and strong tests, congratulations!
To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove the cheaters, fix wrong division cases and update ratings them again!
I see you provide this feature for Ashishgup 's contests and not on all contests XD
I do it every time I do not have an opportunity to quickly deal with cheaters.
Please Mike, why you keep saying you care about cheaters? If that were true you would do something about this https://codeforces.me/blog/entry/75610 for example. And at least add a way to actual report this people. But no problem, keep ingoring users that only want fair contests ...
Click 1
Click 2
Click 3
Click 4
Click 5
Any idea why i am getting TLE on this? It is the same idea as in the official solution...
For every 'G' you are Calling bfs i.e. at max n^2 times. But what you should be doing is calling bfs one time from the final cell and count how many 'G' can be reached from there.
yah..figured it out afterwards.. thanks anyways.. but btw i could run bfs from every g if i would use dsu :)
I think u have the same problem that I had on contest. You have to mark cells you were and don't start bfs from all good persons "G" (if you elier were in this cell "G" and you could arrived to cell (n, m) you don't should to check this again).
yah... this is one way to optimize.but it is not optimal i will implement tomorrow both dsu and bfs from (n,m) :))
Can anyone tell me why my code gets "Memory limit exceeded on test case 8". I first mark walls around 'B', if there is a 'G' sharing a side with 'B' code outputs 'No'. Then do a reverse traversal from destination (n-1,m-1) using bfs and mark all reachable nodes. If a node is 'G' and not reachable i output 'No' else 'Yes'.
Link to my submission — https://codeforces.me/contest/1365/submission/82880705
_Nice problem set.I hope everybody enjoy this round _
Enjoyed the contest, thanks!
Of the problems I worked on: A, C, D were very good. I did not like B. In general I hate these problems with one-line solutions. Anyone else?
No, only you
Isn't it allowed to hack a solution after the end of contest? When I click on hack it! The page shows "You can not hack the submission".
In Div2 you can only hack during the contest.
can anyone help me with why my algo for prob E is wrong-
we need to take only 3 elements to maximize the value, so for first element we will take the maximum one as it will give the best result,now we need to care about all the unset bits of the first element as the set bits will be set in our final answer too, so we change the rest of the numbers of the array such that for any number in the array, at position i if it is set in our choosen first element and it is also set in the number of the array we unset it.
In this way we will get an array which will be devoid of all the set bits of first choosen element then from that array we can again take the maximum element as it will be the biggest contributor, again we can do the same operation to take the third element.
I think this should work. Have you got a submission to check?
This is the link to failed submission solution
1100000 1000001 0110000 0001000
it would be better to choose last 3, but your solution chooses first third and fourth
Thanks, got it
no problem :)
@Ashishgup
Test cases for F is not strong enough.
I believed I hacked some AC submissions using this data set. Obviously the right answer is No, but they all returned Yes.
1 3 8 9 8 9 8 9
Submissions:
https://codeforces.me/contest/1365/submission/82823958 https://codeforces.me/contest/1365/submission/82854157
I remember as a master you can hack other's solutions after contest.
I tried and the verdict is the inconclusive "Unexpected verdict" :-)
Oops. I think there must be collision between judge solutions. Call for Ashishgup.
What is the resolution of this?
Became Candidate Master. Wait! that may have already vanished while you are reading this or soon going to be.
Solved 6 questions. Pretests passed. Not celebrated, as I miss corner cases many times :|.
System testing passed! Still waited for rating updates.
With gain of 93 points, became Candidate Master for the first time. Celebrated hard!!
Now, I came to know that I missed a test case, which was probably missed by author too.
Tragedy!!
That's fine, I'll try my best next time! ;D
At last, good questions. Kudos to the setters and also to the one who pointed out the mistake!
Likely you will be fine. This is an "uphack" so history won't be rewritten. Best of luck!
Thanks :-)
greedyforces
For problem D, something seems wrong with the judge. The solution that I submitted shows few accepted test cases(as it eventually gives a TLE). However, those test cases should also not pass as the output of my code is completely different.
Judge — https://codeforces.me/contest/1365/submission/82901062
Ideone:
- Test Case 3 — https://ideone.com/Rfss7o
- Test Case 4 — https://ideone.com/heJHCG
Can someone help me in understanding is something actually wrong, or it is just me.
Can you explain what type of difference you have noticed?
Input data is not enough. You can see that the three dots at the end are not part of the input.
Sorry, I didn't pay enough attention. I thought dots are the last line of the input(since dots represent blank spaces).
Anyone solved E by DP ?
I tried but stuck in time limit that its is taking O(n^3*64) which is not acceptable
My idea is store dp[i][j][k] where the i is index that till ith index what is the maximum value of length j and for the corresponding bit k.
But this is 64 times more slower for this problem
Ashishgup are you an ididot or what
Problems are really enjoyable to solve
Is it just me or does anyone else also feel that problem C is the new B and Problem D is the new C in the recent rounds?
It's enjoyable round.But,I couldn't solve any of this :( Will try next to do more better :) Anw,Should i learn C++ or keep going with python3?
This round, I did everything in Python 3 except E. Last round, Python 3 was too slow for A which really messed me up (I could have just translated it to C++, but I was too stubborn).
If you don't know C++ yet, it never hurts to learn. But use the right tool for the right job: if time limits aren't tight, a package like itertools can save you a lot of programming time.
Learn C++ and quit python as early as possible.
You might not understand why I say so and python might seem very easy to code rn but you will sure face difficulties (like recursion limit in python or TLE with same logic that gets accepted in cpp) as you continue to grow. Although you can get it accepted in python as well but it becomes very troublesome and requires some extra effort. Also, there are some questions with zero accepted solution in python. I wrote the same logic in cpp and it worked but no one could get it accepted in python because of TLE.
So, why not just write in cpp and avoid many issues. Speaking from personal experience. Good luck :)
I agree with your points, see I have only used Python till now in contests but now I am converting myself into CPP bcoz it's the best tool for Competitive programming. My strategy in contests is to use Python for constant time or linear time algorithms and switch to CPP for tree and graph-based problems.
D solved using dsu (disjoint set union) if anyone needs it : SoLuTiOn