Hello, Codeforces!
74TrAkToR and I are glad to invite you to our Codeforces Round 662 (Div. 2), which will be held at Aug/07/2020 17:35 (Moscow time). The round will be rated for all the participants with rating strictly less than 2100.
The problems were created and prepared by AlFlen and 74TrAkToR. We would also like to thank everyone who helped us a lot with round preparation.
- Our coordinator 300iq for patience and help with ideas.
- Our dear friend lapochka_queen for the idea of one of the tasks.
- Our testers isaf27, Astralpirate, sava-cska, Siberian, voventa, romanasa, antontrygubO_o, DIvanCode, _overrated_, Mlxa, plagues, Prokhor08 for high-quality testing and valuable advices.
- And our team testers: ainta (ksun48, 300iq) и акацуки (p1rattttt, kostyamyasso2002) for proper testing.
- MikeMirzayanov for amazing Codeforces and Polygon platforms.
On the round you will be asked to help main ponies from My Little Pony animated series (Fluttershy, Applejack, Twilight Sparkle, Pinkie Pie, Rarity, Rainbow Dash) and to solve 5 problems, one of which has two subtasks. You will have 2 hours to solve them.
Score distribution will be announced shortly before the round.
UPD: Score distribution: 500 — 1000 — 1500 — 1750 — (1500 + 1500)
UPD2: Editorial
We wish you good luck and high rating!
As a tester, give me contribution, please:) UPD:( UPD1:)) Thanks you.
Unrelated question: How to become a tester?
I'm asking for real, not for gaining contribution. ;)
Basically, testers are friends of the authors. Also, some testers are people with a lot of contribution.
As we can see, people with negative contribuion can become testers too.
Aahhh! I see.
Going to google now "How to make friends in codeforces". ;__;
For making friends in codeforces there is a star in the profile page next to the handle!
More seriously, it is good to be a friend of the author IRL.
LMAO, I know how to add friends in cf lol. By doing that how will the other person know I've added him as a friend.
I was referring to getting in touch with contest hosters and problem setters.
err I think you got it wrong.
The reason testers have high contribution is because they gain contribution after being a well-reputed tester, not necessarily because they started with high contrib.Basically, testers gain contrib, so to say all testers need to start with high contribution is a logical fallacy.
You can ask about it MikeMirzayanov or if you know problemsetters you can ask they.
Cool.Cool.Cool.Cool.Cooooool.....
You mean like message MikeMirzayanov???
Yes.
Sent this message 4 months ago.....
It's like messaging Mark Zuckerberg on Facebook..... :D
become tourist. then everyone will want you to test. the end.
.
u dont have idea how ugly the question statements are and kind of worthless .
Shittttiest contest ever
writing this while contest in undergoing predict my frustation level..
You can't even solve div3 problems. stop bashing.
Yea i can see who is saying this the one having 12000 rank in prev div 2 contest .Keep up the good work .
At least I was able to solve 3 problems in div3 round where you cheated.
See how much spare time u do have checking on random peoples u wanna be one on one ping me we will talk there . Crybaby there is an iitian in the house
What's the point of being an IITian if you still have to cheat?
Maybe he is of reserved category, lol
Yeah i am if u are such a racist thiugh u should know in india caste discrimination is a crime .
Dude, you got the seat because of your caste. Why do you expect others to not call you a reserved category guy?
Deserving people sacrificed their seats so that you can study there.
sorry
thoufond
You know you can be punished under the provisions of the Scheduled Castes and Scheduled Tribes (Prevention of Atrocities) act, 1989?
Bro!! It is a humble request .. Please don't lower the standards of IIT's in our country unless you are from reserved category(PS: then you took the seat of other deserved candidates due to some shitty political policies). If you are an IITian.. good for you but then if you need a tag on your shirt stating that.. sorry bro you don't deserve it. PS: I was deeply frustrated after reading your shitty comments and so had to write all of it.
Does 'skipped' means that he cheated?
Yes
Ya ankit i respect your words but the thing is i submitted one of my friends solution coz i wasnt willing to go further in the contest as i got some work i heard somewhere that if you copy someones code the contest will be unrated thats all i did . And i dont know what is the point of this guy to just poke in my comment worthlessly out of nowhere kinda frustating already the contest was not up to the mark so thats all .. Anyways i feel bad about my prev comment :) thanks dude
yeah sure, you submitted for the 3 problems for it to be unrated and not for only one or two problems :)
Thanks, you helped me find my food.
It wasn't unreadable though..
As a tester , were u able to understand the problems ?
The Pretests of question number 2 should be strong. My code Passed pretests but failed after. I am just giving feedback and not complaining. It's real heartbreak to see that red written "System test fails"!
!
girl
Pony
Sexy !!!
SIMP!
LOL
ARE YOU A GIRL OR A BOY?
Boy
74TrAkToR, are you a boy or girl?
boy
there goes all hope.
What was this girl and that explanation mark and that pony, shit posting or something very deep?
Why 6 ponies but 5 problems?
The 6th one might be the over smart one creating a harder subtask.
The 6th is me : )
Did you change your dp for making that comment?
I use my little pony to denote my max delta.
before it was this, because my maximum was a pupil
The 2 of the ponies are twins as 2 subtasks.
Nice pic for seek attraction!!
I feel old now ;)
I love watching "My Little Pony" cartoons, so I look forward to this contest!
But I am not a girl ;)
Me too. It's great but seems not to have more stories :(
when a newbie like me see a contest has 5 problems, Oh no this means I will only solve 1 or 2 maximum :/
This cartoon is interesting and I hope the problems are short and interesting too!
As a participant , give me contribution .
UPD :(
What are all the possibilities when a contest submission gets "Skipped" ?
All possibilities except when no one cheats.
So if we ensure no one takes my code, it won't get skipped, is it?
Yes, avoid using online IDEs like ideone, because if you forget to make the code private by any chance, anybody can access it. Also, you mustn't intentionally give your code to anyone.
But how can anybody get ideone public links? The person has to share the link right?
No, I guess it's available on the site only, something like recent public actions is available there.
Actually it happened to me one time when I started CP and used ideone then. In a Codechef Lunchtime, after someday I got an email that my submission got plagiarised due to same code matching with 2 other person's submissions. When I took a look at their codes, their codes were clearly my code with some added unnecessary comments. At that time I came to know about this ideone public access thing.
Currently, Ideone has removed the pubic link of recent submissions which may lead to a decrease in cheating on CP platforms via ideone.
Ohh, I didn't know about that. Haven't used ideone for the last 4-5 months. Nice to hear it though.
If your code matches with anyone...if you copy from other or someone copy from you...both of you guys's submissions will be skipped :3
Is series is available in YouTube :-)
Typo: Pinkie Pie is not Pinky Pie.
Also that's a good theme! (I am a brony)
omg, I'm sorry... I fixed it by the way.
I like how people think memes will gain upvotes. THE MEMES HAVE TO BE QUALITY!!!
quality is a noun :v
Grammar...nah.
AlFlen If possible can you guys please add some kind of divider between the fairy tale and the problem statement so that people who are only interested in the problem statement can directly jump into it? no offense just a suggestion
We tried to make statements rather short. The legend doesn't occupy a noticeable part of statements so I think it'll be comfortable enough for you to read and understand them.
Thanks for a prompt reply!
LOL
Well, that like semi worked.
Thanks for making the statements really very short.
Never seen statements shorter than this.
one of which has two subtasks.
That's interesting !!The second pony from the left does codeforces rounds :GWagnwChinoWoah:
Orz
HEllO
i dont like pony
Hope it will be queue free contest..
Yeah, we don't want the system to stall.
My daughter loves My Little Pony, she should take care of this round...
Parents are doing codeforces nowadays. Damn! Thats why I love codeforces
from 5th standard Russian students to parents, from newbie to world top coders, you will get each category on codeforces. That makes competition more interesting.
Hi ainta!
As a testers, I'm not a tester :)
To my disgust, I actually thought those ponies were standing on two of thier legs and I wondered what that third thing was.. figured it out now.
I cant unsee it, it will haunt my dreams forever
I now must watch my little pony now to try to get a better score on this contest.
Woahh, it's so cute <3
NERD_MAX = Helping My Little Ponies on CF.
Oh god unfortunately I cannot participate in this My Little Pony round because something has come up. How do I unregister from a contest? I can't find it.
Go to the number of participants link beside the contest and click it. There will be a cross symbol beside your name. Just click on it. Moreover, you can also not submit anything during the contest. It won't affect anything.
weird flex but ok
rotavirus is weird but fine
Never watched My Little Pony animated series but the contest seems interesting!!
Behind this cuteness, I believe there will be some dangerous problems. Best wishes to everyone. Go and be high rated ;)
ofc there will be some dangerous problems if problemsetter is severe highschool girl from Chelyabinsk
bronies everywhere...XD
Will I be able to finally get my colour?
wow, a second My Little Pony contest since Codeforces Round 259 (Div. 1)!
And now I am super excited to help these little ponies. Aren't you guys?
Great, yet another Pony Round!
One of the pony has crush on author. But he/she doesn't know which one. Help him in finding it out. XD
I didn't see Rust in the registration email. Is that a mistake or is Rust really not available for this round ?
What are the things hanging between the legs of the ponys'?
other legs of ponies
I didn't know sparkle is one of the main ponies. Thank you for this round, I'll be waiting for some nice puns.
Wow!
The background looks so...cute?
BINOD
Finally... a perfect excuse to join a rated round after nearly two years!
Oh, it's Div. 2 only...
As a pony , I'll participate :)
when will codeforces support swift language? Sadlly, So many languages have been added to codeforces but not swift. Swift is really a elegent, efficent modern language! Hope administrator support swift someday!
when will codeforces support asm language? Sadlly, So many languages have been added to codeforces but not asm. asm is really a elegent, efficent modern language! Hope administrator support asm someday!
Are problems have been prepared on ponygon?
No, on Russian and English
Participating in this round while I have an exam tomorrow feels like suiciding
Well, it's your 189th. Your are clearly addicted.
My Little Pony animated series ...
A lot of thanks broh, now I can waste my next weeks n weeks watching them <3 =D
I am scared, I am noob and don't want my ratings to fall now.
Why worry? If ur rating drops, next time it'll be easier to raise them, never worry about that when participating in a contest.
Finally scrolling through a comment section where you can actually read the comments.
GL HF
Hey! Hello? Am I on the blogpost?
Well, guess what?
Yes, I am! And that's Awesome!
Problems setters, Pinkie loves you sooooooo much, too much that I want to throw a party!
Ready for contest!
I hate the story of problems! :(
For real...
This endless blah blah apple here flutterapple cakeapple there because fluttepie with cakeflutter there is only annoying. This is no fun.
Yup the cringe level was just off the charts!
No offence to problem setters ,but i am unable to understand the question itself.
wtf the statements say?)
Horrible statements. I couldn't even understand what was asked.
Can I get my ratings back by nothing playing this round :(
Yeah!! If you haven't submitted your solution even a single time, then you can leave the contest. There will be no change in your ratings!!
Is it an English Comprehension Contest?
Are we here to code or improve our vocabulary.Seems like its and Mock IELTS/TOEFL Tests.
Even they have to make 2 announcements for writing the correct question!! But till now I am unable to understand what they are trying to convey in the first question.
yea same with me...i cant understand how are the blocks kept..
yeah even i guessed about the question and solved according to that
Poor statements!! I am unable to understand even the first question !!
There was no need to have a sooooooo long story, it would be better to have a more mathematical statement than a confusing long story.
The names of the characters were so complicated to keep track off and the long stories. Sorry but not a good contest.
This isn't meant to offend anybody, I just posted it to make this very clear that problem statement is where one should give more time then framing story. No doubt problem statement could be better
This was just waste of time.... The problem statements were so confusing. Actually this contest was not of coding but english.
I dont care how pinky pie eats her patty cakes just tell me what I have to code for!
I hate the story of problems! :(
Not able to understand even first problem!
The statements should be simple. There is no need to always introduce a story in the problem. I am very disappointed after this contest.
Why the f*** do I have to see these DISGUSTING PONIES.
Why the fuck you want to include stories in problems, and these weird names- Rainbow dash, Flutter shy..... What do you think, by including stories, the round becomes interesting??
no more storyforces
How did all of the contest setters agreed to release these kind of statements?
Too much storytellings... Just give us simple statements please...
Contest in a nutshell: Read the stories and fall asleep. Setters be like.. Didn't understand the question? We did not want you to.
I don't like pony stories anymore.
It's really not that hard to write clear, concise statements.
It took so much time to understand problem A :-(
To the guy who designed the problem statements: Hats off! You've a tendency to play around with words and over-complicate easy to understand sentences.
I planned to watch My Little Pony when I was reading the announcement, but after this contest, I would say no.
How to solve A after the contest?
Do not discuss problems while contest is running.
Yes, I know. I edited the comment now.
clever
n/2 + 1
How?
make an exemple for n=4 and n=5 on the paper.In the first step you can color the "1st layer" (near the border). In the second step the second layer and so on.In the n/2th step you will reach the mid layer (+1 for the center).
Am I taking an English examination?
The statements are too long and there are too many unnecessary(as I think) stories.
And there was even a typo in the statement of problem B. As you can see in the picture below, the two phrase "After the sixth event" came out incorrectly as "After the second event"(Only true for the latter). Although the typo was fixed after a while, there wasn't announcement about this. Moreover, I posted the comment similar to this about 1.5h before, but after about an hour, the comment was deleted for an unknown reason.
Why couldn't no one find the typo before the contest? Why there wasn't announcement about the typo? And why my previous comment disappeared? Not pretty good. :(
This round tested our English rather than our programming skills.
Just asking. Are the top rankers(in this round) even trying problem E1 lol
I have tried very hard on E1 and nearly burned my brain
Now I got a reason to hate pony.
This is the reason I don't upvote before round.....LOL
Exactly
Was I the only one who found C way easier than B (At least on the implementation side)?
For me the number of unpronounceable word in statements defines the hardness of problem.
Enough grid construction and heavy weight english word exercise for today. I quit.
How to solve D?
here
Let $$$dp[i][j]$$$ denote the size of the largest rhombus with the bottom vertex located at $$$(i, j)$$$.
Suppose the colours at $$$(i, j)$$$, $$$(i - 1, j - 1)$$$, $$$(i - 1, j)$$$ and $$$(i - 1, j + 1)$$$ are all the same, $$$dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1])$$$ + (1 if the vertex opposite to $$$(i, j)$$$ has the same colour as $$$(i, j)$$$)
If the colours are not the same, $$$dp[i][j] = 1$$$
Now, just iterate over all bottom vertices $$$(i, j)$$$ and count the number of rhombuses using the dp values.
Code: https://mirror.codeforces.com/contest/1393/submission/89259501
Wow, never got the idea using 1 dp. I got idea using 4 arrays. up, down, right, left.
Recently watched a video of largest square in grid, and applied the same idea here
Pretty nice trick :)
Why the fuck memory limit on D is 256 MB
Because $$$30$$$ MB is enough.
A dp from every corner so 4 matrix of 2000*2000 ? P.S. that s 4*16 mb so nevermind
only 2 dp arrays are enough! from the upper and the lower side.
only 1 dp array will also do the trick. Just take the minimum in second pass.
Waiting for more.
Yeah got the idea now! :)
I thought 256 MB is a normal memory limit?
No clue, but you can code the same solution by just considering for each character one at a time, doesn't change total time complexity anyway if you were planning on storing pref[26][n][m] or something similar.
I agree. That and the tight time limit cost me a good 150 points and 20 minutes and it must have cost others points too. The constraints were way too tight.
I have O(n * m * k) sol, where k is alphabet, and I'm getting TLE. Perhaps it was supposed to stop rotation or even force O(n * m), but seems v tight for little reason.
I had done using only 2 2D array(one for input and other for DP). So, size is 2*2000*2000*4 bytes = 32MB.
Can somebody tell me the idea behind problem C? I tried like everything. Thanks in advance!
Apply Binary Search MySolution
the answer will depend on the maximum frequency of a number and count of maximum frequency. To notice that see that if max freq is 3 , it occurs twice , you can make ab...ab...ab , now just from this you can notice that ans would be (n-(mx)-(cnt-1))/(mx-1), as you need cnt — 1 spaces from the end and to populate mx freq you need mx spaces , out of remaining spaces you need to partition it in mx-1 segments like ab...ab...ab , which is optimal when we divide them equally or just division. Link — my solution
but why only max frequency is considered?
because numbers having frequency lesser than maximum frequency can always be adjusted in the middle without lessening min distance
Because for other frequency we can insert them in empty spaces between those of max frequency and they won't come out of the array because they are strictly less than max, for ex — if 3 , 2 ,2 ,1 is freq array and numbers for them is a,b,c,d then there are 3 a's , we want maximize their separation first, so we equidistantly place them , so a...a..a, Now every value has freq<=2, which can be placed in each of empty spaces between these a's, so their min distance won't decreas
I did the same.
I used binary search to look for the solution. My solution passed the pretests but gave WA on test 43. I don't know where did I go wrong. Link to my solution: https://mirror.codeforces.com/submissions/i_m_eshaan17# Can you please see what thing I missed out
Wow. Nice Solution.
Look u have to find frequency of the number occuring most number of times. now find total how many numbers are there having this frequency int val=n-maximum_frequency-(count of numbers having maximum frequency -1) val/(maximum_frequency-1) will give the right answer .
Let us see this with 2 different examples {1,2,3,1,2,5,1,2,8,1} Here the maximum frequency is 4 and the number having this frequency is 1 so we can see answer will be 2 Now lets take change the example a bit {1,2,2,1,2,5,1,2,8,1} Here the maximum frequency is 4 and the numbers having this frequency are 1 and 2 so now you can see the answer becomes 1 {1,2,1,2,5,1,2,8,1,2} can be one solution reason is that 1 has maximum frequency so we arrange array like 1....1....1...1 we put 1 at both ends to maximize the distance and put other elements between 1s but when 2 also has frequency 4, two 2s will start falling between two 1s(something like 1,2,2,1.... So,every time we encounter another number having maximum frequency we need to put it at last (something like {1,2,1,2,5,1,2,8,1,2}) Look at the first test case for a bit of clarification
Was it just me or did others find the wording of the first question a bit difficult as well?
Today I get to know why we were taught English first then programming.
Though the concept and problem idea is good, I suggest the Problem statements can be used for essay writing competitions.
I'm doubting my English skill after this contest
I solved C and still can't understand A
I made upto 6 X 6 grids to understand the common pattern between them xD
Red is first step, blue is second, green is third...
upd: Its wrong
what is the pretest 5 of problem D?
Pretest 5 cost me 2 WA, but it was my silly mistakes...
Try this:
The correct answer for that pretest is
26
, right?Thats what my code is printing as well.
I was able to fix my code for that problem.
For those wondering, the pretest I used was
However I believe maksio's test should provide an error as well. The only change needed is change it to a
5 * 5
matrix ofa's
I see you have done DP similar to me too. The issue in your code seems to be that you are wrong in up and down dp.
You can see my code, bam is similar to left, dan is similar to right, up is dp1, down is dp2.
Basically, c should be updated as 1+2*min(bam, dan) and and d should be up[i+1][j]+2, not 1.
Bye Bye rating
The problems were good but the wording of problem A messed up my tempo. Also the names of the characters (i assume names of ponies ) confused more from understanding the problem statement. I would recommand using some common and familiar english names.
No comment
.
Look she has a rating which is much higher than mine and I am gonna get about +120 after this round but seriously this contest could have been better and what the fuck are you even talking about
She confused the contest with the storybook
You can choose to become a writer rather than a contest designer
What is the correct approach for C??
bsearch answer, then for each iteration, always greedily put down the number with the largest remaining frequency that is available.
Can you please, share your check function?
89248346
Where my check may fail
vector<int> v
is vector of frequencies of every element that appears more than once89275212
can you plz plz check this function https://mirror.codeforces.com/contest/1393/submission/89275288
can you please explain the logic?
no need to use bs :v
i mean sure, but for me it was easy to see a bsearch solution, and it fit in the TL.
My approach:
Count the frequencies of each unique element.
Note that if there are multiple most frequent elements, you can discard all but one unique element. If both
1
and2
appear as frequently as possible, you can just do1 2 .. 1 2 .. 1 2
. This reliably increases the distance between alike elements by 1.Note that the optimal arrangement for the most frequent element will always be
1 .. 1 .. 1
where1
is the most frequent element, and you fill things in the middle.All remaining elements can be inserted into the
...
spaces in some way (proof is left as an exercise). So we just count the number of how many things there are that aren't the most frequent, and divide by the number of spaces (the...
).What if the input is 112233. Optimum distance is 2 and it is achieved with 123123. But if we start with 1....1, then we can't get distance 2 anymore. The possible ways to fill the middle are 2233, 2323, 2332, 3223, 3232 and 3322, but they all fail.
I mention that in the earlier case -- because they're all the max frequency, we can treat
1 2 3 ... 1 2 3 ... 1 2 3
like1 ... 1 ... 1
and just add 2 to our final answer.You only need to fill things in the middle if their frequency is lower than the maximum, if they are the maximum you can handle them earlier.
Final answer is the sum of all frequencies $$$< maxfreq$$$, divided by $$$maxfreq - 1$$$, plus the number of unique elements whose frequency is $$$maxfreq$$$, minus $$$1$$$.
Binary search
Codeforces be like lets have a new member in the family : PonytaleForces !
storyforces
Lol what the heck was this contest
It was a english grammer contest,this contest increased my english reading skills :XD
what's the idea in problem C
Kindergarten question designer is better for you
I saw this coming thats why I tried confirming it here , looks like they were joking back then.
!
Seriously, they couldn't have given a more ironical reply
Write stories if you want, but please at least give us formal definitions for the operations to be performed.
What is the approach to solve D?
for each cell we calculate the number of ways to form a pattern with center is the cell.
$$$up_{i,j}$$$ = Number of cell with same color above this cell
$$$dn_{i,j}$$$ = Number of cell with same color below this cell
$$$a_{i,j}$$$ = $$$min(up_{i,j},dn_{i,j})$$$
$$$b_{i,j}$$$ = max size of left half of a rhombus centered in this cell
$$$c_{i,j}$$$ = max size of right half of a rhombus centered in this cell
$$$m_{i,j}$$$ = $$$min(b_{i,j},c_{i,j})$$$ = max size of a rhombus centered in this cell
$$$ans$$$ = sum of all $$$m_{i,j}$$$
it should be $$$min$$$
Thanks. Fixed it.
Notice that all squares can be treated as a rhombus of size $$$ 1 $$$ and count them. After that remove all squares that can not be a center of a rhombus of size $$$ 2 $$$ add those left to the total number of rhombuses. Do this again for size $$$ 3 $$$ and so forth.
How can this be done?
Notice that a cell can not be the center of a rhombus of size $$$ n $$$ if there exists a cell of a different color such that the Manhattan distance between the two cells is less than $$$ n $$$.
Using this fact we can implement a multi-source BFS from all cells which have different colored neighbors and in each round count the number of cells that are not visited. (Be aware that the memory and time limits are quite tight).
Interesting point of view. Is it $$$O(nm)$$$?
Yes, because this solution is almost only BFS and the graph that the BFS is run on contains $$$ nm $$$ nodes and about $$$ 4nm $$$ edges. Therefore the complexity is $$$ O(nm + 4nm) = O(nm) $$$.
However the constant factors are quite large and I lost a good $$$ 20 $$$ minutes and $$$ 150 $$$ points (due to submissions) trying to optimize them. IMO the limits are way to tough and a solution with the expected complexity should pass immediately.
It's a competition where I've got the best result I hope I won't be hacked
When will the Editorial be published?
By the way, the contest you prepared was great!
My video editorial for Problem A and Problem C
why we can not paint 4*4 grid in two step
Because after two steps not all fields are painted.
why we can not paint cell (1,1),(1,3),(2,2),(2,4),(3,1),(3,3),(4,2) and (4,4) with one color in first step and all remaining cell with other color in second step
We want to have chessboard as result. So first is (1,1),(1,3),(1,5).... on all four sides.
Second is the fields in between of the ones from first, and every second fields of row/col 2,n-2. And so on.
You can't paint (2,2) in the first step, as it is not
neighbouring to the last painted cell
, Read the question statement again you missed this point.why only the elements with max count are required?
If you try to spread the elements across the array the ones with max count would end up closest.
Lets say freq of max element is 5 then u have X__X__X__X__X and u can place all elements of lower freq in different spaces so they will be atleast as far as a pair of X.
Because we are essentially dividing the array into groups right? So for the element which has max frequency
n/(fr[x])
element will be minimum hence the least spacingWhere I am wrong in Problem B!, I just counted number of active planks , with updating frequency table for each plank entry as entry and exit happens and also in this frequency table maintaining the maximum value and number of odd and even values, now the answer is YES only when maximum value in frequency table >=4 and also total planks %4==0 and no odd frequency is there in the frequency table else answer is always no.?
Where I am not getting problem statement please tell my mistake!
Thanks in advance.
You have to make only 2 storage.
You only need planks (a,a,a,a) and (b,b,c,c). {here a,b,c are sizes of planks}.
In total you need just 8 planks.
This is nice explanation. Knowing that the problem statement is understandable, too.
Thanks I think that I misunderstood the problem as in total we can more than one rectangle and square storages, confused with the word storages in the problem statement. Thus just one change of making count to 8 will make my solution pass, I dont know what is the sense of such problem statements and what they checked. Facepalm after losing 120 Rating again I gave the contest today as my mood was bad and I thought of freshing up my mood but Now I cant describe to what scale the statements worsened my mood again.
Did you read the announcement? I did exactly the same as you before reading it and it cost me 3 WA's and half an hour. :(
I didn't do well in this contest but could solve B.
Here is the way I did it, keep 4 sets (two, four, six, eight) two => freq[2, 4) four => freq[4, 6) six => freq[6, 8) eight => freq[8, inf)
Now as queries come, these tables can be updated on the fly in somewhat O(logn)
You can build when
8 has >0 members (2 squares)
6 / 4 has >1 members (2 squares)
6 has >0 members and 4/2 has >0 members (1 square, 1 rectangle)
4 has >0 members and 2 has >1 members (1 square, 1 rectangle)
the overall complexity is O(nlogn + qlogn)
You are basically missing lots of cases and also not all planks are required to be used, so the %4 check is completely incorrect
You can do it with much more simplicity. Just maintain a map to count the frequency of each element. Now take an array of sets with size 2 :
set<ll> cnt[2]
.In the
0th
position, insert those elements whose freq is >=2In the
1st
position, insert those elements whose freq is >=4Now, for each query do the following:
If we need to add/remove something, update both frequency map and the array of sets (check the count and see if we need to remove or insert something in
O(log N)
.And to get "Yes/No" we have 3 cases :
1. If
cnt[1].size() >=2
-> YES (we have 2 squares feasible)2. If
cnt[1].size() ==1
a. If the freq of the element is >=8 -> YES (we have 2 squares feasible)
b. Otherwise, see if you can construct 1 square and 1 rectangle by checking the size of
cnt[0].
3. The answer is
NO
.if we have 4 planks of length 1 and 2 planks of 2 and 4 planks of size 3. so total no of planks is 10(toatal planks %4!=0) so it will give no according to your code. But ans is yes
I think I misunderstood it as all planks must be used too bad mood today thanks buddy for figuring it out!
I thought C problem was easier as compared to the B problem or did I overcomplicated my problem B solution?
Can anyone plz tell me why getting WA on C https://mirror.codeforces.com/contest/1393/submission/89275288
i m using binary search to find the answer in binary search i m putting the no.s with greatest count first then the no.s with smaller count can anyone plz have a look
Try this !
This test case is wrong since: 1 <= a[i] <= n
Was there any edge case in B.I tried every possible combination still it gives wrong answer on Pretest 5.
Try going for 11111111
Really a lengthy and messy one , please keep to the point questions
Can someone please help me to figure out this issue. This was my cf submission 89275621 but in local PC my answer as was different.
Your go out of bounds on your A vector (you can start with only 1 type of plank).
can someone tell what was the pretest 4 in problem B ??
why only the no. with max count are required to find ans in C?
_pastor_
So it was a right decision to leave the contest after reading the first problem. XD
I appreciate the problems, but does anyone find that it was more unnecessary story, and had lots of ambiguity, specially problem B ?
Hoping to see Editorial without ponies.
Story forced me read the examples and guess the problem.
5- Ponies ✓
There should be some background stories but not that long.
5 — Fast editorial X
Problem D is very similar to this 1015E2 - Stars Drawing (Hard Edition)
I remembered that problem too, and I actually got a WA in contest because I implemented biggest star instead of biggest rhombus :P
(surprisingly, biggest star passes all sample tests)
biggest rhombus can be checked using 4 adjacent square values.