I had difficulty understanding B. When you say all possible integer values of k this means -10^9 <= k <= 10^9 and for all these values the given equation should hold. The problem is — lets just say k = ai then |ai — k| becomes 0 and in this case |aj — k| basically becomes |aj — ai| will always be either 0 or or positive and equation doesn't hold true so for every index it becomes 0. Do they mean that for any k if the equations holds true then we can count it? I found this statement really confusing :(

Wasn't this contest div-3? Am I hallucinating?

Okay I got this. Also the editorial's 3rd and 4th paragraph could have been made a lot simpler rather than just confusing math. The thing is you filter out the numbers that have different last bit because they can't be the last Pn number because at least one bit is different. We will follow this approach till the highest bit and generate the number.

Late to the party but can someone explain the solution of D. I got the gist of the solution but unable to understand 3rd and 4th paragraph of the editorial given. Why do we discard the elements that had different bits in the previous calculation?

Got it. Thanks mate.

I did that only but couldn't pass pretests... what's wrong with it https://mirror.codeforces.com/contest/1919/submission/240551011

Is C literally that easy? How to do it?

I agree. Even i tried couple of times but returned back seeing we have to download some software or something to participate(I'm not really sure if its software) and can't see the info regarding contest easily on their website. I must agree its not user-friendly and which is why i've never participated.

I've a feeling that radewoosh might be 2nd only if mifafaovo doesn't go in god mode.

Ohhh. I got it.

Why Radewoosh dropped to 34th place from 2nd place after getting perfect 100? same with firefly?

Okay, maybe I'm salty because i couldn't solve it. I'll try to read problems better from next time.

but this means every a_n is a prime number which is similar to what i said.

It consists of 0, 1 and ? means that the string would have atleast one 0, one 1, and one ?. I understand it this way. So many announcements in between contest means its not only me who didn't understand it rather many people understood it different way. That doesn't change the fact that it was poorly written and explained.

I checked the examples and then the confusion persisted and then those announcements in between contest divided my attention. You can say I'm saying this because I couldn't solve it. But to be honest even after half an hour after the contest I am not getting it i just find it hard to understand and that makes it uninteresting for me.

Okay but it is still the same thing. it consists of 0, 1 and ? implies that it consists of every character that is mentioned.

They say the string is beautiful if it contains 0. 1. and ?. On the other hand is 0? is an example of beautiful string and it doesn't contain 1. It is confusing for at least me, don't know about others. They could've written 0, 1, or ?

I see a lot of specialists there, including me, failing sys tests in A lol guys.

I agree, I've given many rounds and i don't say they are bad just because I performed poorly but today's C problem statement was totally shit ;( they could've explained it in a better way.

I got rekt ;(

There was a time when I used to get frustrated by the cheaters but I learned this "YOU CAN DO ABSOLUTELY NOTHING". So now i don't care about them.

I literally have seen someone bragging on linkedin as soon as him became candidate master and when i checked his profile he has solved only 250 problems where 170-180 problems were less than 1300 rated and only 50-60 problems of 1500-1700 rated and that same guy in his intial contests fells on pupil. I was really thinking, Is becoming CM that easy? but then I realized he cheated. But you see you can do nothing except improving yourself. which is what everyone should do.

I've written only 1 comment, now 2, regarding this matter ever since. while someone else has written multiple comments different times clarifying Problem vs Question. So we have an idea about how much it affects and whom does it affects.

Peace.

I have not commented on radewoosh's blog but as you have created a separate topic for this so I'll comment here.

"Well guys, don't get so easily offended by small things, you don't need to start arguments online to spread hate or prove your point above someone else's."

Of course it is a small thing to get offended but let me tell you an even smaller thing to point out continuously which is "Problem vs Question"?

Does it matter if I say a question instead of a problem. it doesn't. You are correct that most people here address it as question (some people address it as Problem too) but again it is a very small thing that radewoosh keeps on pointing out. its not the first time he has written it. Also regarding correcting someone, I absolutely love getting corrected but do you really think that it is such an crucial topic where you HAVE TO correct people or someone else will die it doesn't. Give it as a suggestion and let people take it. You have said it and people have got it. The first time I read it I understood it but seeing it multiple time again and again from the same person definitely makes me (offended) wonder why would someone keeps on doing that.

I'm not against his point of saying problem vs question. But if you're literally writing 50s of lines of commments describing difference between Problem and Question or keeps on saying this multiple times then my friend god helps you.

My B failed (-_-)

I never thought 6 months ago that I'll be able to even maintain a lower specialist. But alas my dream come true and If all my 4 solution passes, I'll be an expert.

It gives you an idea about the level of the problem. Though it is not always accurate but most of the times it is. For example B problem might be a bit hard today as compared to other div-2's B problem but again it might be easy too. You can never tell you can only guess.

Me being a 'specialist' calculating my probability of winning a PS5 in a combined round. But I forgot I'm bad at probabilities and even CP (-_-)

I forgot to edit this. The main issue was that I was taking the 2nd input in the wrong order.

Please read my comment above you. I tried something similar, can you please help?

Can you please help me as why my dp solution for D doesn't work?

Logic-
$$$dp[i][j][0]$$$ -> score of 1st player at $$$(i,j)$$$ travelling from (0,0)
$$$dp[i][j][1]$$$ -> score of 2nd player at $$$(i,j)$$$ travelling from (0,0)

now each time when $$$(i+j)$$$%2 == 1 means it is the turn of 1st player to arrive at $$$(i,j)$$$, now he can come at $$$(i,j)$$$ either from $$$(i-1,j)$$$ or $$$(i,j-1)$$$ but he will come from path where difference between scores of players is minimum since 2nd player would have played before him and 2nd player wants to minimize the difference.

if $$$(i+j)$$$%2 == 0 it means it is the turn of 2nd player to arrive at $$$(i,j)$$$, now he can come at $$$(i,j)$$$ either from $$$(i-1,j)$$$ or $$$(i,j-1)$$$ but he will come from path where difference between scores of players is maximum since 1st player would have played before him and 1st player wants to maximize the difference.

Here's my submission it fails in only 3 test cases ;(

I think you meant problem E.

I'm also doing the same thing, why this does not work?

Looks like my dream of becoming an expert will always be a dream :(

Would this work?

first sort all the portals by minimum distance of getting their from $$$(1,1) + a[i][j]$$$(value of portal) put them in list-1 say.

then in list-2 sort all the portals by minimum distance of getting their from $$$(n,m) + a[i][j]$$$(value of portal)

then we can pick the first item from both the list (if they are not same portal otherwise we will take 1st item from 1st list and 2nd item from 2nd list or 1st item from second list and 2nd item from 1st list and select whichever gives the minimum answer)

Can you help?

Can you explain the transitions? i might not solve it on my own.

Well here's what i did for pretests(don't know if it will pass or not)-

if $$$l==r$$$ then count how many numbers are same in both $$$l$$$ array and $$$r$$$ array call this count and answer would be $$$ans = r - count$$$

if $$$l!=r$$$ then we are sure we need to shift $$$abs(l-r)/2$$$ elements from larger array to smaller array to make size equal, add it into the ans and now before shifting we will first remove those numbers from both the arrays which are same (as shifting them would cost an additional money to change the color) after this we shift those elements from larger array first that are similar to each other so that 1 copy of that element stays in larger array and 1 copy in smaller array and we don't need to spend additional money to change the color, even after this if elements are not same we will change their color and add it into the answer.

consider this-
14 10 4
1 1 1 1 2 2 2 2 3 4
1 1 1 1
we will first remove all the ones as they are present both in $$$l$$$ and $$$r$$$ arrays, after this its better to remove two 2s from $$$l$$$ as it will prevent us from spending extra money on them by changing color now the arrays would become-
1 1 1 1 2 2 3 4
1 1 1 1 2 2
now we just shift either 3 and 4 and also change its color.

true :(

Is it only me who can't do anything for 1 hour before the contest and keep switching between different tabs until it starts?

You guys are solving 5000 pts problem :(

Can you tell me how to do D without extra memory?

I agree, even i find that c and d problems of ABC sometimes involves good math skills. Atcoder really test your maths skills too.

I am solving this problem but got WA on test 5. I can't figure out what's wrong. Here's my commented code, if you get free time then kindly help.

Submission

That was a nice proof, thanks for writing it.

Thanks for the words. Will see how it goes.

Will do this and see how it goes. :)

I realized today CP is not for everyone. Even after 7-8 months I can't maintain specialist. I know nobody cares and its fine but I'm really devastated ;(

Me before contest- "Hope I'll become expert today for the first time"
Me after contest- "Nevermind! I'll regain my specialist in next contest" (-_-)

I think setters should again write a correct validator in problem A, invalid test cases are showing hacked in A.

Can you please help me with the idea behind C. I solved D and understood it but I don't understand C from the editorial. I know that first and last character of string s should be 1 so that we can make both a and b balanced but I'm not getting as how to proceed from this.

Any help would be appreciated.

XD, See you soon in 705, though I know you will beat me easily but I won't mind trying :)

I would like to add spookywooky in this list. I like competing against him :)

What i'm trying to say is sometimes the solution of a problem doesn't strike to someone and its completely okay but a tougher problem requires more time and skills and that's why it should be more rewarding than the easier ones. This works perfect and that is why div-2/1 and global round problems have increasing points.

I don't think it is same with other rounds because in normal div-2/1 and global rounds the scoring distribution are in increasing order and difference between consecutive problems are greater than 250(most of the times it is 500) which gives you enough time to race ahead someone who didn't solve that problem at all.

I know it might be out of context but I wanted to say this for a while.

I think the point system in educational round(also div-3) is a bit unfair. All of the problems are assigned 1 point even though they are in increasing difficulty. For instance if somebody has solved problem A and C but not problem B (unlikely but still happen sometimes) then his ranking would be similar to someone who has solved A and B but not C. Even though the first person was able to solve a tougher problem(theoretically and practically) he is still in the same position as the second person which seems unfair to me.

A problem with higher difficulty should have more points, For instance the score distribution in Edu and div-3 contests should be 1,2,3,4,... so on. What's the problem with this score distribution? Maybe I'm missing something.

Open to criticism :)

I got it, thanks.

Yes I understood it, sorry for the silly question.

Got it, thanks for the response.

sasuke_uchiha Priyansh31dec well it is indeed $$$O(N^3)$$$ sorry for the silly question I just figured it out, poor me (-_-).

Why brute force in C doesn't work? I just start from index 1 and make this value 1 by just doing what's stated in the problem now as not to surpass time limit I check whether i+a[i]>n or not, if it is true then I bring a[i] down to n-i so that i+a[i]<=n (add n-i in answer) and as n can be 5000 at most the complete algorithm would be $$$O(N^2)$$$ but it gave me TLE on pretest-9 can anybody help?

Here's my Submission

Edit:- Its $$$O(N^3)$$$, I got it thanks for the response.

Poor me created 5 cpp files for the contest and I only solved A (-_-)

I only reach upto value of b in 6th step, couldn't go further. Thanks for the explanation.

The risk I took while submitting C was calculated but I forgot that I'm bad at math (-_-)

God knows when will I learn to handle doubles ;( Can anybody help where might be precision errors in my Solution, I got 2 WA constantly.

Can someone please provide me a case where my Solution of C is failing? I tried for 45 minutes but couldn't find one :(

I once implemented two segment trees to find minimum and maximum element in the range related problem of the array. It was a sorted array (-_-)

Fixing the server is okay, but in cookoffs its too irritating that you can't even submit the solution in a time based contest, sometimes servers works for a moment where somebody else submit the solution and you can't because either you were solving some other problem or you IDE didn't initialize. Forget about queues.

Servers just crashes in the starting hour of contest and everyone knows even 1 minute of time penalty gets you punished in ranking. The same happened in dec and jan cook off and then I stopped using it since last week. glad that I didn't participate today. They have the same story every time.

Yes, I iterated through k!, the unnecessary loop didn't strike me ;(, Thanks :)

Can somebody please help as why my recursive solution is giving TLE in problem C? I don't understand.

I did same still got WA on test case 3, Can you help? The code is easy enough to understand.

You are running the first for loop (inside int main function) only upto 100005, change it to 100020 too.

I got the idea in the contest but was unable to find the formula for that. which hijibijee provided.

Thank you for the explanation and the link. I got it.

Thanks for the help.

The problem is with the size of your fac array which is 100005 but according to the problem n<=10^6 which makes n+k-1<=100009(and it is less than 100005).

I changed 100005 to 100020 and it got Accepted

Thanks for the formula, I got stuck at this and couldn't find this formula. Can you please provide me an explanation or a link where this formula can be find? Thanks for the given problem too.

Codechef is a joke nowadays. Only 2 short contests per month and that too getting server errors a lot, you can't even open IDE to submit the code forget about long judging time, similar thing happened in december as well. No wonder why CF is 10 times better than CC.

Really very nice and smart solution of B. Thanks

A big NO to CodeChef from today. BYE (-_-)

Problems like B make me quit CP. such a shit problem, learned nothing and wasted my time. Don't know it was a beginner contest or what. Absolutely frustrated.

I gave 4 WA in problem A and I really wanted to save my ass from getting -140 or something that's why I went with this and didn't implement a shorter approach out of fear of getting WA, looks like it worked and gave me +39 instead.

My solution of Problem B of yesterday's contest perfectly describes Meme#2, XD.

Ohhh! I just read it thanks, Would this functionality of changing handle will be available this year too?

In problem C I found the max h[i] and then started seeing whether it works or not. Here is my submission. Can anyone help?

Yes, I just understood it. Thanks for the info.

Yes, Got it, thanks. Just looked at your solution, it was easy and excellent.

In problem B I picked median of the array a let's call it 'X' and then assigned value of each b[i] depending upon a[i]-
1.) If a[i] is X then b[i] is also X.
2.) otherwise b[i] is either 1 or any multiple of X that minimizes (a[i]-b[i]).

Can anyone explain, what's wrong with it?

Its weird how newbies and pupils most of the time gets downvoted because of their comments (which I agree are really bad sometimes) but from last few contests high rated beings just commenting literally anything like "As a tester" comments and still getting upvotes.

Like once errichto said- "This comment section is shit"

It passed :)

I submitted C in last 2nd minute but the judgement didn't came in contest. If it gets passed. Will it be considered in rankings or not?

Its okay, even most of the indian coders are frustrated from this cheating behaviour of fellow coders. Codechef long challenges are prime example for that.

Yes post it on youtube so that we can refer to it in future if we need. Thanks :)

Can anyone explain why my dfs solution for C is giving wrong answer on pretest-2 here's my Submission.

I've tried it on some other test cases and unable to find any mistake. Can anyone help?

What's wrong with 1 test case of problem C? Can anyone help, Here's my Submission

Ohhh, yes I clicked on UK flag and it worked. Thank you.

Thanks, Got it.

I know this is not the right place to ask but I'm facing problem with codeforces. My codeforces from last night is loading in russian and every time it takes few seconds to translate the page into english but its happening every single time for every page of codeforces.

Also i'm seeing few keywords change in codeforces like "Accepted" to "Complete Solution" and "Submission" to "Attempts". Can anyone help me out? Apologies for posting it in this blog but this blog is active so I asked here.

In problem D- I first calculated the maximum population amongst all the leaf cities lets call it $$$maxele$$$ and then I filled up all the non-leaf cities' population in all the leaf city and made population of all leaf cities equal to 'maxele'

if after all this I've still population of non-leaf cities left then I'll distribute it equally amongst all leaf cities and my answer would be ->

but I'm getting wrong answer on test-5 now test-5 is quite big so I can't decode it, Can you please help?

Here's my Submission

He must be using this much of t-shirts to mop his floor I guess.

Poor me, didn't find it. Thanks man.

I know its an old thread but I hope you would help, I wrote the solution of D2 by making three offset string RGB... GBR... BRG... and comparing them with original s.

But I'm getting this unusual error of uninitialized value usage in my solution of 4th test case, cf online judge is highlighting the line but I'm unable to crack it. Can you please help?

Here's my Submission