### vovuh's blog

By vovuh, history, 2 years ago,

<almost-copy-pasted-part>

Hello! Codeforces Round #570 (Div. 3) will start at Jun/26/2019 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) 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 rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-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 6 or 7 (or 8) 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 a 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.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</almost-copy-pasted-part>

UPD: I also would like to thank Ashishgup and kocko for help with round preparation and testing!

UPD2: The contest will be extended for 15 minutes because the problems are more interesting than we thought. We also advise to read all the problems because some of them may have the same difficulty and we cannot know which one will be easier for you than the other.

UPD3: Editorial is published!

UPD4:

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Mbah1937 8 248
2 rtbmnie 8 450
3 BaiBatyr 8 455
4 LJF007 7 305
5 old_boo 7 322

Congratulations to the best hackers:

Rank Competitor Hack Count
1 MathY 120:-90
3 yzm10 36:-2
4 csegura 31
5 shaker007 30:-11
798 successful hacks and 492 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A blast 0:01
B Kirill_Kudr22 0:04
C I_love_HellHoleStudios 0:04
D divya_rawat 0:10
E llbra9z 0:13
F FlyInTheSky 0:42
G Mbah1937 0:27
H UMP45 0:25

• +177

 » 2 years ago, # |   -8 why I m struggling in Div.3 ? how can I improve my DP & graph solving ability?
•  » » 2 years ago, # ^ |   +28 Maybe this can help: https://codeforces.com/blog/entry/47516
•  » » 2 years ago, # ^ |   +7 You can follow my DP lists to practice Dynamic programming.
•  » » 2 years ago, # ^ |   +2 hack this submission if you can :) 56132099
•  » » » 2 years ago, # ^ |   +5 Done :)
•  » » » » 2 years ago, # ^ |   0 what about this one? 56133777
•  » » » » » 2 years ago, # ^ |   +18 Hacked
•  » » » » » » 2 years ago, # ^ | ← Rev. 3 →   0 not any more! 56136001 (ps: I just uniqued all numbers)UPD: definitely not this one 56136056
•  » » » » » » » 2 years ago, # ^ |   +9 I think that this last one is fine. At least I cannot hack it.
 » 2 years ago, # |   +1 Hoping for a good contest!! Was awaiting Div3 eagerly.
 » 2 years ago, # | ← Rev. 2 →   0 "You will be given 6 or 7 (or 8) problems and 2 hours to solve them." It is so vague. Though It'll be decided later.
•  » » 2 years ago, # ^ |   +11 The contest is running with no problems showing, i guess they still couldn't decide ;-)
•  » » » 2 years ago, # ^ |   0 ddos attack
 » 2 years ago, # |   +36 Div.Vovuh xD
 » 2 years ago, # |   -36 I hope to become purple after this round!
•  » » 2 years ago, # ^ |   +1 If you solve all problems and take first place, that might be possible
•  » » 2 years ago, # ^ |   0 I hope to become red after this round!
 » 2 years ago, # |   -18 you can safely stop doing these, they are useless. stop spamming the website
 » 2 years ago, # |   -22 I find difficulties of problems from Div 3 are as same as Div 2!
•  » » 2 years ago, # ^ |   0 Why do u think so?
•  » » » 2 years ago, # ^ |   -12 It's from my experience from Div 2 and Div 3 contests I've participated.
•  » » » » 2 years ago, # ^ |   +5 I dont think so. Probably, u cant solve 3 problems sometimes even when ure blue, but in div3 u can
•  » » » » 2 years ago, # ^ |   0 I used to think the same when I was around your rating, but once you reach somewhere around 1500, you will notice you are able to solve 4 or more problems in Div 3.
•  » » » » 2 years ago, # ^ |   +10 experience ?!!!! you mean solving at most 1 problem in more than 15 minutes in less than 10 contests ? are you sure you know what the meaning of experience is ?
•  » » » » 2 years ago, # ^ |   0 maybe it's right when you solve only 1 problem. My experience: 3 div.2 / 4 div.3 (year ago) 4-5 div.2 / 6-7 div.3 (now)
•  » » » » » 2 years ago, # ^ |   +7 OK, I got it. If I go to advance level I will get the difference. Thank you guys
•  » » 2 years ago, # ^ |   -18 because you're so bad at coding. if you aren't advancing, why do you keep trying and wasting your time with this cp bullcrap? move on kid....
•  » » » 2 years ago, # ^ |   -20 I know what I'm doing. Didn't ask for your advice. Piece of shits everywhere
•  » » 2 years ago, # ^ |   +12 The creators of the contests have sufficient intelligence to differentiate problems of Div 2 from Div 3. Trust them.
•  » » 2 years ago, # ^ |   0 That's because you solve only one problem during the contest regardless of whether it is Div2 or Div3. So you find both of them same.
•  » » » 2 years ago, # ^ |   0 OK. got it
 » 2 years ago, # |   +18 Vovuh can stay on top of the contributors table just by organizing 1/2 Div. 3 rounds per month xD
 » 2 years ago, # |   0 Hope I will turn pupil after the round :)
•  » » 2 years ago, # ^ | ← Rev. 2 →   +8 I wish you good luck!EDIT: when you get downvotes for cheering someone on xD
•  » » » 2 years ago, # ^ |   0 Thanks :)
 » 2 years ago, # |   -13 Good luck everyone, i hope for a good contest for all of us.
•  » » 2 years ago, # ^ |   +8 1.it won't be
•  » » » 2 years ago, # ^ |   -11 why ?
 » 2 years ago, # | ← Rev. 2 →   -11 Div 3 after long time.
 » 2 years ago, # |   +17 Tired of helping Vasya and Petya !
•  » » 2 years ago, # ^ |   +12 And Nastya.
•  » » 2 years ago, # ^ |   +4 Also Tanya, Alice, and Bob.
•  » » » 2 years ago, # ^ |   +1 They always screw us with their so called games.
•  » » » » 2 years ago, # ^ |   +1 yup
 » 2 years ago, # |   0 when these persons are testing the round , the chance of hack comes down a lot !
•  » » 2 years ago, # ^ |   0 It becomes zero in some questions(B) as they have to remove then xd
»
2 years ago, # |
-13

# MyPrediction

•  » » 2 years ago, # ^ |   0 Really!?
•  » » 2 years ago, # ^ |   -6 Handle or Name ?
 » 2 years ago, # |   +3 DIV-3 contest is always missed by Vovuh. :D :D :D
 » 2 years ago, # |   -11 Does the countdown work correctly? It says 7:05 before start!
 » 2 years ago, # |   0 wow new contest from vovuhi love you man
 » 2 years ago, # |   +4 The temperature is higher than my meme contribution
 » 2 years ago, # | ← Rev. 2 →   0 good luck everyone,hope your rating will increase
 » 2 years ago, # |   +32 where are the problems
•  » » 2 years ago, # ^ |   0 There they are!
 » 2 years ago, # |   0 Unable to see the problems.
•  » » 2 years ago, # ^ |   +2 invisibleforces !!!
•  » » » 2 years ago, # ^ |   +1 also downforces!!!
•  » » 2 years ago, # ^ | ← Rev. 16 →   0 Same hereEDIT : fixed
 » 2 years ago, # |   0 Not able to see problems. Is it only me ?
 » 2 years ago, # |   0 question is not opening
 » 2 years ago, # |   -6 what is going on with interface?
 » 2 years ago, # |   0 why i can't ask an question????????????
•  » » 2 years ago, # ^ |   0 you just did
 » 2 years ago, # |   +2 Anyone else not seeing problem statements??
 » 2 years ago, # |   0 WTF
•  » » 2 years ago, # ^ |   0 it is not showing !!!
 » 2 years ago, # |   0 But where are the problems. Contest is running without any problem set
•  » » 2 years ago, # ^ |   +2 I like your handle.
 » 2 years ago, # |   0 Oh time is running although there aren't any questions!
•  » » 2 years ago, # ^ |   +1 seems like, it's gonna be an unrated contest
•  » » » 2 years ago, # ^ |   0 no way ...no one has seen the problems ..they will extend the contest
 » 2 years ago, # |   0 what's happening codeforces..
 » 2 years ago, # |   0 i can't see any problem
 » 2 years ago, # | ← Rev. 2 →   0 I cannot see the problems.
 » 2 years ago, # |   0 no questions?
 » 2 years ago, # |   0 Problems??
 » 2 years ago, # |   +1 problems aren't visible.. lol
 » 2 years ago, # |   +1 Where are all problems? Are we a joke to you?
•  » » 2 years ago, # ^ |   0 wait first 15 minutes
 » 2 years ago, # |   +1 Hello, there is some issue. The problem set is not loading.
 » 2 years ago, # |   +4 Why everyone is writing same comment of not able to see the problems ?
 » 2 years ago, # |   +1 are there any hidden questions :(
 » 2 years ago, # |   0 I can't see any problems in contest main page.
 » 2 years ago, # |   +43
 » 2 years ago, # |   0 can't view any problems??
 » 2 years ago, # |   +13 Where are the problems, I can not see them
 » 2 years ago, # |   +1 I cant enter in this round.Help plz
 » 2 years ago, # |   0 Why problemset is invisible?
 » 2 years ago, # |   0 Problems?!!!
 » 2 years ago, # | ← Rev. 2 →   +1 So many submissions already and i am just receiving the problems... Will it be rated?
•  » » 2 years ago, # ^ |   +2 Sir, I share this concern.
 » 2 years ago, # |   +1 The problems were not visible and suddenly I saw 3000 people have already solved the first question
 » 2 years ago, # |   +1 will there be extra time for the delay?
 » 2 years ago, # |   0 unexpectedly ez round...wish u guys good luck.
 » 2 years ago, # |   +5 Yet another internet speed round XD
 » 2 years ago, # |   +29 Queryforces
 » 2 years ago, # |   0 problem C is easy but hard to implement...
•  » » 2 years ago, # ^ |   0 < 10 lines in python for me
•  » » » 2 years ago, # ^ |   0 Could you please explain the solution. I mean pseudo code
•  » » » » 2 years ago, # ^ |   0 You can consider the formula for how much additional charge you will need, where "out" is the number of days you don't charge: neededCharge = (out*a) + ((n — out)*b) — k + 1 Specifically, we need neededCharge to be less than or equal to 0, so we can set out based on that. Simplify to get out <= (k-n*b-1)/(a-b). So, set out = floor((k-n*b-1)/(a-b)) Then, if out is less than 0, your answer is -1. Otherwise, your answer is min(n, out).
•  » » 2 years ago, # ^ |   0 I am having understanding the problem, could you please explain the problem. I will really appreciate it. Thanks.
 » 2 years ago, # |   0 can any one explain problem D ?
•  » » 2 years ago, # ^ |   0 store array containing frequency of i in arr[i]. sort all values in reverse order, now for all elements after 1st element in array, its value is min(arr[i],arr[i-1]-1). Answer is sum of positive values in array.
 » 2 years ago, # |   0 Problem E is more easy for Java people
•  » » 2 years ago, # ^ |   0 How,Can you please explain?
 » 2 years ago, # |   +48 Thanks for the contest! For anyone who had a hard time with any of the problems, I wrote up descriptions of my solutions, which you can find at this link. If you have any questions, feel free to post below.
•  » » 2 years ago, # ^ |   0 Thanks, I think it'd be a bit easier to read if you posted this as a blog and if you have the implemented code, to share it.
•  » » » 2 years ago, # ^ |   0 Good idea—I’ll post this soon. Thanks!
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Geothermal {May be I am wrong}...I tried D using max-heap but at the 19th case the response was TLE .. but as you guys have used sort() method [complexity will be nlogn]. So, as Mine...https://codeforces.com/contest/1183/submission/56128383any suggestion where am I wrong???
•  » » » » » 2 years ago, # ^ |   0 I'm not sufficiently familiar with Python to debug it effectively, sorry.
•  » » » » » » 2 years ago, # ^ |   0 Geothermal thanks for the response ...sorry, I don't want you to debug my code ... I am just asking whether max heap is a good way to solve it ..pseudocode: heap=maxheap(contains the frequency of distinct nos) start=maxheap[0] //max value while(heap not empty): val=heap(remove max value from heap) if((val-start)>=0): if(start>=0): count=count+start start=start-1 else: break else: if(start>=0): start=min(val,start) count=count+start start=start-1 else: break `So, for me its O(nlogn) ... n for removing the elements and log(n) for maintaining the heap...??? am I correct?? ...
•  » » » » 2 years ago, # ^ |   0 The blog is up at https://codeforces.com/blog/entry/67973.
•  » » 2 years ago, # ^ |   +8 Thanks for your effort. I looked into it. I found that explanation of Q.F was difficult for me to understand ( or maybe because i have used another method .) Can you tell me in short what you did ?My method : I found out during the contest that if there is a solution which doesn't have max element (let's say m) . Then the only better option can be m/2 + m/3 + m/5.
•  » » » 2 years ago, # ^ |   +3 Yes, I think we used different methods (although I know other people who used your approach too). That's a clever solution--my method was essentially a pruned complete search. I noticed that any number under 200,000 can't have too many factors (more precisely, they have at most 160 factors). This lets us considerably reduce the number of possibilities we have to search through, and from there the rest is essentially a bash.
•  » » » » 2 years ago, # ^ |   0 If I'm not wrong, you take 340 problems as a candidate for first problem , and for each of them you take next 170 as second and 340 as third candidate ?
•  » » » » » 2 years ago, # ^ |   +3 I took 340 problems as candidates for the first problem, then for each potential first problem, I chose 170 candidates for the remaining two problems. I then did some optimization so that I could pick the best pair of problems in ~170 operations rather than by considering all possible pairs of candidates.
•  » » 2 years ago, # ^ |   0 getting tle in test case 6 problem g https://codeforces.com/contest/1183/submission/56137010
 » 2 years ago, # |   0 How to solve G?
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Edit : This is for Problem H. Consider dp[i][j] -> number of distinct subsequences ending at i, of length j. Then, $dp[i][j] = \sum_{c = a}^{c = z} dp[prev[i][c]][j - 1]$Where prev[i][c] is the maximal index before i, that has value c.
•  » » » 2 years ago, # ^ |   0 Is there only dp solution? I've tried whole round to think greedy one
•  » » » » 2 years ago, # ^ |   -10 i'd say, that this is Dp + greedy
•  » » » 2 years ago, # ^ |   0 How does it make sure that only unique subsequences are counted
•  » » » 2 years ago, # ^ |   0 How can we take care of Overflow??
•  » » » 19 months ago, # ^ |   0 what is wrong in this solution. Would you please explain? https://codeforces.com/contest/1183/submission/74626611
 » 2 years ago, # |   0 Totally, I could not understand the problem C :(
•  » » 2 years ago, # ^ |   0 it takes me more than 40 min to understand :(
•  » » 2 years ago, # ^ |   +4 You can consider the formula for how much additional charge you will need, where "out" is the number of days you don't charge: neededCharge = (out*a) + ((n — out)*b) — k + 1 Specifically, we need neededCharge to be less than or equal to 0, so we can set out based on that. Simplify to get out <= (k-n*b-1)/(a-b). So, set out = floor((k-n*b-1)/(a-b)) Then, if out is less than 0, your answer is -1. Otherwise, your answer is min(n, out).
•  » » 2 years ago, # ^ |   0 "For each query print one integer: -1 if Vova cannot complete the game or the maximum number of turns Vova CAN JUST PLAY otherwise"The maximum number of turns Vova can just play that is without charge and play.
 » 2 years ago, # |   +1 How to solve E?
•  » » 2 years ago, # ^ |   0 dynamic programming dp [i] [j], the number of different strings of length i ending in j letter
•  » » » 2 years ago, # ^ |   0 Could you explain how do you ensure that we don't count the same string twice while building the dp. Thanks in advance.
•  » » » » 2 years ago, # ^ |   0 Try to understand it yourself. Let's get another matrix used [i] [j], indicating whether there was such a state before. If it was, we simply reset dp [i] [j] and recalculate the answer for it since this time we will have more different lines of length i ending in j.
•  » » » » » 2 years ago, # ^ |   +3 Thanks for making me figure it out myself..
•  » » » 2 years ago, # ^ |   0 Actually BFS is ok...
 » 2 years ago, # | ← Rev. 2 →   +1 In test case 4 of E why cost int not 232 — 1*0 + 10*(10-9) + (C(10,2) = 45)*(10-8) + 44*(10-7). UPD : Got it. I made a mistake.
 » 2 years ago, # |   0 why there was no hacking ? and when the ratings will come up ?
•  » » 2 years ago, # ^ |   0 Read the Announcement of the round
•  » » 2 years ago, # ^ |   +1 In Division 3 rounds, hacking occurs for twelve hours after the contest. Ratings will update after the hacking phase and system tests finish.
•  » » » 2 years ago, # ^ |   0 Thank you for your explanation would you tell me how to hack somebody now ?
•  » » 2 years ago, # ^ |   0 The Hacking phase in Div.3 comes after the contest like educational roundThe rating will come up after finish the Hacking phase
•  » » » 2 years ago, # ^ |   0 What if I try to hack but fail?
•  » » » » 2 years ago, # ^ |   0 Nothing happens in your penatly
 » 2 years ago, # |   +6 great round I would say but the complexity of the tasks > D is quite high for a Div. 3 contestants
 » 2 years ago, # |   +4 Damn I could solve E I think.. isn't it trying all the possibilities and if it took too long we would output -1
•  » » 2 years ago, # ^ |   +6 No its not you wold definitely get TLE or WA for that the solution . just consider a 100 letter string with same characters and k=99. you can use dynamic programming to solve it.
•  » » » 2 years ago, # ^ |   0 Yup it's no good to solve it like that I will try it later
•  » » » 2 years ago, # ^ |   0 Why DP. I thought it is a implementation type problem. I got pretest passed without DP.
•  » » » » 2 years ago, # ^ |   0 Yes I thought of an implementation solution like yours but unfortunately I wasn't able to solve the hard version with it so I used DP to solve both of them.
•  » » » 2 years ago, # ^ |   0 It is possible. My (updated after contest) solution: http://codeforces.com/contest/1183/submission/56154439
•  » » » » 2 years ago, # ^ |   +1 what do you mean by possible . I'm sure you didn't simply tried all the possibilities inefficiently.
•  » » » » » 2 years ago, # ^ |   0 I tried all, but stop when I achieve k number of possibilities. Sure, it's not fair "all". But it's kind of brute force.
•  » » 2 years ago, # ^ |   0 Hahaha, trying all possibilities? Did you read "substring" instead of "subsequence"? Just as a side note, total possible ( without removing repetitions ) number of subsequences is $2^N$ where $N$ is the length of the given string.
•  » » » 2 years ago, # ^ |   +4 Did you read reza comment .. yeah I get it and I know the possibilties could be large but I thought if we didn't find 100 substring after 1e8 possibility then there's no answer but as reza said 100 same letter wouldnt work with this way
•  » » » » 2 years ago, # ^ |   +2 Oh my bad then. But you didn't clearly mention what you were going to do? I accept I misunderstood here, but you should have said something like "Since $K$ is small, we can just find those many subsequences and then stop". This gives better idea of what you were trying to convey.Anyhow, I must apologize for my misunderstanding. Sorry for that! I shall read more carefully from now on.
•  » » » » » 2 years ago, # ^ |   0 yup i got Accepted with your approach :)
 » 2 years ago, # |   0 can I hack my own solution???????
•  » » 2 years ago, # ^ |   0 Yes
•  » » 2 years ago, # ^ |   +13 I remember once BinaryBoy did this with him self :|
•  » » » 2 years ago, # ^ |   0 How will be the scoring then?
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 deleted
 » 2 years ago, # |   0 Thanks for the contest!
 » 2 years ago, # |   0 Why am I not a trusted participant since I have participated in more than two rated rounds and never had +1900 rating?
 » 2 years ago, # |   -7 The user NO_PAIN-NO_GAIN cheated again.He somehow find the solution of problem H of sraman915Submission by sraman915: 56104958 Submission by NO_PAIN-NO_GAIN: 56124086I think he should be banned from Codeforces as he did cheating multiple time. The another cheating caught by me is hereI am drawing attention of MikeMirzayanov
•  » » 2 years ago, # ^ |   -27 Who are you LE_ROI? :D :D :D If you can prove this I will give you everything in this world. Please don't wast your time to see other code. Nijher chorkai tel dao. Copy past codeforce onek valo dhorte pare. I don't know who is sraman915. Hey Sraman are you know me? LE_ROI are you man or woman? :D :D :D
•  » » 2 years ago, # ^ |   +9 The question is all about finding the distinct subsequences of length K. after that one can easily figure out the solution. I googled it and found something relevant which I have also mentioned in my code.I don't know NO_PAIN-NO_GAIN but after seeing his solution I think he has also used the same thing but he forgets to mention in his code.
•  » » » 2 years ago, # ^ |   +1 Yes, you are correct. But I don't copy and past. I just use google to find out finding the distinct subsequences of length K . Thanks you sraman915.
•  » » » 2 years ago, # ^ |   0 Hey. I have also taken code from that site, although I was not sure whether I should use that code. Are we allowed to take code from other sites during contests?
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Yes, googling is a must skill. It does not violate any rule of CF.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +3 You can take any code that is not copyrighted except the code from current participants of the contest.
•  » » » » » 2 years ago, # ^ |   0 Okay. Thanks for clarification.
•  » » 2 years ago, # ^ |   +5 It seems he has copy and paste code from Internet source. It is clear from inconsistent indenting. Many people have done this. I don't believe he has cheated.
 » 2 years ago, # | ← Rev. 3 →   +1 TIL that declaring a massive vector makes a big difference in time complexity. (vector (MAX)) https://codeforces.com/contest/1183/submission/56113733https://codeforces.com/contest/1183/submission/56126400https://codeforces.com/contest/1183/submission/56126075https://codeforces.com/contest/1183/submission/56126321I thought that declaring a vector only takes up space and not time.
 » 2 years ago, # |   0 TLE https://codeforces.com/contest/1183/submission/56117801 AC https://codeforces.com/contest/1183/submission/56126830 The only difference between 2 submissions is I declare the array inside mainWhy I got TLE ?
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Have a look at my submissions I got plenty of TLE's for the same reason on D. When you declare your array globally of size 2e5 and when there are 2e5 queries it will become O(10^10) because you are initially array of size 2e5 everytime. That's why array should be dynamic to take advantage of the fact that the sum of n over all queries is <2e5.
 » 2 years ago, # |   0 How to solve G?
 » 2 years ago, # | ← Rev. 2 →   0 When I tried to hack others solution with my testcase.I am getting generator crash error Since it is valid. My test case is : : test case(for Problem D )
•  » » 2 years ago, # ^ |   0 It is because you are generating a testcase with 200000 queries where n=200000. However, in the problem statement, it is mentioned that "It is guaranteed that the sum of n over all queries does not exceed 2*10^5 ".
 » 2 years ago, # | ← Rev. 2 →   0 Hello i am very new to codeforces will anyone tell me that after participating in div 3 and solving 2 questions why there is no effect on my rating??please tell me Thanks :)
•  » » 2 years ago, # ^ |   0 Right now, hacking phase is going on which will continue for 12 hours. So, ratings will be changed later after the hacking phase ends.
•  » » » 2 years ago, # ^ |   0 Thanks
•  » » 2 years ago, # ^ |   0 the rating changes will ocurr after finish hacking phase in 12 hours
 » 2 years ago, # |   +4 can anyone explain..how to use DP in problem E?
•  » » 2 years ago, # ^ | ← Rev. 3 →   +5 Sure. Sub-problem : Count number of distinct subsequence in a string ? Sol — I'll use 1 based indexing. Let DP[i] be the number of distinct subsequnces ending with character s[i]. Then if character s[i] did not occured before then we can chain it to all distinct subsequence occured before this position i.e. we can freely choose second last position in our subsequence DP[i] = sum of all DP[j] for j < i. If s[i] occured before then we don't need to count second last position before last occurence of s[i] because they are already calculated DP[i] = sum of DP[j] for prev[i] <= j < i. where prev[i] = last occurence of s[i]. Base case is empty subsequence. DP[0] = 1. Original-Problem — Just add length state in DP. DP[i][j] = Number of distinct subsequence having last character s[i] and is of length j . Base case DP[0][0] = 1.This solution is O(n^3) but can be optimised to O(n^2) by calculating prefix sum DP for each length layer. While finding best cost in problem : Start taking subsequence with maximum length.
 » 2 years ago, # |   0 very nice round . congrats
 » 2 years ago, # |   0 Can somebody please explain the graphical approach to problem E?
 » 2 years ago, # |   0 queries round.
 » 2 years ago, # |   0 can somebody explain how you think problem B solution thanks in advance
•  » » 2 years ago, # ^ |   0 Take the item with the least price, if you increase this price by k, you will get the maximum price this item can be given, Now the range of prices for this item will be, assume price as 'a', [a,a+k], Now look at the item with the maximum price, you can change it's value to anything in the range, (let price be 'b')[b-k,b+k], if you take intersection of these ranges, you will get the range in which all prices of other items can be brought to,i.e, each item in the array can be brought to some price in this intersection, the maximum of this intersection will be the answer.
•  » » 2 years ago, # ^ |   0 In B we have a sure move to maximize the common price, if that is not possible there can't be a common price.After sorting the prices, if we increase the smallest price by k(maximum possible increase), and if the product with largest price is less than a[0] + 2*k, then there exist an increment or decrement of a value less than k to reach that maximum possible price. But if the product with largest price is greater than a[0] + 2*k then there is no such price that the smallest and largest initial price product can have in common.
•  » » 2 years ago, # ^ |   0 thank you
 » 2 years ago, # |   0 Can someone please review my solution for B: https://codeforces.com/contest/1183/submission/56089281I think I got lucky, since I don't even know what I was intending to do. My logic made sense in the start, and I kept changing the conditional to pass the example input.Perhaps it will not pass sytem tests.
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 I think your solution is correct. After sorting the array, to print (a[0]+k) as answer, we need to just check if (a[n-1]-k)<=(a[0]+k) or (a[n-1]-a[0])<=2*k. Instead of checking only for a[n-1] (or max element), you are checking for all elements which is not necessary. So it should pass system tests.
•  » » » 2 years ago, # ^ |   0 Thank you for your reply. Yes I noticed this too. I wasted time being confused with myself. I fully understand it now.
 » 2 years ago, # |   +2 Problem statement of C was not good, it took me around 30-40 minutes to understand the problem statement.
 » 2 years ago, # | ← Rev. 3 →   0 In the third problem, when I submit the solution with pypy I am getting TLE(time limit exceeded) in test 27 but when I use python 3 my solution is getting accepted. What is the difference between them and why did coordinators asked to use pypy??edited: Solution with python 56132978 Same solution with pypy 56130341
•  » » 2 years ago, # ^ |   0 I did some research and found out that the problem is += when I tried solving with replaced += in pypy my solution was accepted.
 » 2 years ago, # |   0 Good round and good tasks. Thanks, vovuh!
 » 2 years ago, # |   0 Will hack score?
•  » » 2 years ago, # ^ |   0 not in this one
 » 2 years ago, # | ← Rev. 2 →   0 .
 » 2 years ago, # |   0 How can I figure out what's wrong with my code when I get a WA on a mile long test case?
•  » » 2 years ago, # ^ |   0 Create a program that generates a (small) testcase, generate one as long as your output equals to the output of a bruteforce/copied model solution.
•  » » » 2 years ago, # ^ |   0 The solution itself is more or less bruteforce plus I tested the code for a lot of small cases by hand so I'm really surprised that I get WA
 » 2 years ago, # |   +2 The best div 3 I ever seen. But different in complexity between D and E was too hight.
 » 2 years ago, # |   +9 Hey codeforces ,Please check my blog where I have revealed a big fraud that happened in today's contest !What these two users did is just unbelievable, I hope MikeMirzayanov will do something about the subject.
 » 2 years ago, # | ← Rev. 2 →   0 problem G getting tle on test case 6 https://codeforces.com/contest/1183/submission/56137010
•  » » 2 years ago, # ^ |   0
 » 2 years ago, # | ← Rev. 2 →   0 My solution I'm getting trouble with problem B. Could anyone tell me what's wrong with my approach?? please...
 » 2 years ago, # |   0 When will the problem analysis be published?
 » 2 years ago, # |   +1 any help pls!,why this code fail in test 3 problem B? https://codeforces.com/contest/1183/submission/56142029
 » 2 years ago, # |   -8 how to solve E?? plz someone explain it in simple words
•  » » 2 years ago, # ^ |   0 Use breadth first search. Nodes are strings. Edges is removing one character from it. Use map or set to remove duplicates.
•  » » 2 years ago, # ^ |   0 For E u can simply bruteforce...Generate unique strings by deleting 0,1,2,3... characters from given string until size of 'S' becomes K... To generate all string u can use a queue of string and push the given string into it now take the front of queue, generate and push all unique string by deleting a character from it. Repeat this until queue becomes empty... You can refer to my submission
 » 2 years ago, # |   -8 Are all the solutions rejudged? I had solved 3 problems but now it is showing none. What is the issue?
 » 2 years ago, # |   -29 One of the worst contests ever. Terrible test cases, and for some reason, all questions had the same weight which doesn't make any sense.
 » 2 years ago, # |   0 Does our rank go up if we do successful hacks?
•  » » 2 years ago, # ^ |   +1 No, just in div.2 or div.1 you can hack and come up your rating
•  » » » 2 years ago, # ^ |   +3 Thanks..and btw when will the ratings be updated?
•  » » » » 2 years ago, # ^ |   +4 as soon as in these moments
 » 2 years ago, # | ← Rev. 2 →   0
 » 2 years ago, # |   +9 Editorials?
 » 2 years ago, # | ← Rev. 2 →   +1 Interesting problems.
 » 2 years ago, # |   0 systems message:"Внимание! Ваше решение 56108275 по задаче 1183E значительным образом совпадает с решениями других участников и находится в группе одинаковых решений lukamosiashvili/56108275, Whatever.../56123536. Такое совпадение является явным нарушением правил. Отметим, что непреднамеренное утечка тоже является нарушением. Например, не следует пользоваться ideone.com с настройками по умолчанию (публичным доступом к вашему коду). Если вы имеете неоспоримые доказательства, что совпадение произошло по причине использования общего источника, опубликованного до соревнования, то напишите комментарий к посту о раунде со всеми деталями. Подробнее можно прочитать по ссылке http://codeforces.com/blog/entry/8790. Такое нарушение правил может являться основанием для блокировки вашего аккаунта или других штрафных санкций. В случае повторения нарушений, ваш аккаунт может быть заблокирован." I can not wonder how he copyed my code, because I not gived him my code.
 » 2 years ago, # |   +6 Where Is The Editorial?
 » 2 years ago, # |   +3 any editorial/tutorial please? :)
•  » » 2 years ago, # ^ |   +3 https://codeforces.com/blog/entry/67973unofficial and please stop making these comments before reading other comments in here, you're creating useless messages which waste people's time when you could have just scrolled up a bit and found what you were looking for.
 » 2 years ago, # |   +3 The test case in problem c on which my code was hacked is showing same solution on one of the correct submissions .Are there any other reasons of a code getting hacked ?
•  » » 2 years ago, # ^ |   0 It might be giving TLE.
•  » » » 2 years ago, # ^ |   0 Yes it was that only thank you.
 » 2 years ago, # |   0 Where can I get editorial of this contest?? Plz help
•  » » 2 years ago, # ^ |   0 It is not uploaded yet!
 » 2 years ago, # |   0 Can someone please explain how to solve the last problem(H)?
 » 2 years ago, # |   0 Wow, this is my first time on the list!! Happy:)
 » 2 years ago, # |   0 This may sound dumb but I still dont understand Problem C- Computer Game. What is different between output 0 and -1?
•  » » 2 years ago, # ^ |   0 NOTE: In the first example query Vova can just play 4 turns and spend 12 units of charge and then one turn play and charge and spend 2 more units. So the remaining charge of the battery will be 1.doubt: TEST CASE: 15 5 3 2 If Vova can play 4 without charge and then 1 turn with charging then why is output 4?Help would be really appreciated
•  » » » 2 years ago, # ^ | ← Rev. 5 →   0 It’s all based on the completion of this game. In worst case you may output 0, otherwise output -1 when Vova cannot complete anyway. Vova can complete only if after each of n turns the charge of the laptop battery is strictly greater than 0. If it is equal to zero, it can only output -1, but it is not good.
•  » » » 2 years ago, # ^ |   0 The answer that the setter is looking for is the maximum number of turns Vova can play without charging, so the last turn (the play and charge turn) does not count towards the final answer. That makes the answer 4 instead of 5.
 » 2 years ago, # |   0 I am a begginer and most of my codes face TLE.Please suggest?
•  » » 2 years ago, # ^ |   0 keep in mind the constraints and optimize accordingly
•  » » » 2 years ago, # ^ |   0 Thanks
 » 2 years ago, # |   0 If you are Python programmer, consider using C++ instead of Python when you submit your code
»
2 years ago, # |
0

what is wrong in my code;

# include

using namespace std;

int main() { int a,n,b,d,c; cin>>a; d=a; while (d != 0) { b = d % 10; c = c + b; d = d / 10; } if((c%4) == 0) {cout<<a; } else {n=c%4; a= a+n; cout<<a;}}

•  » » 2 years ago, # ^ |   0 You should write a loop to find a bigger answer than "a" in the else statement.
•  » » » 2 years ago, # ^ |   0 ohh i found my mistake. thanks
 » 19 months ago, # |   0 can someone tell me what is wrong in this submission. I can't figure it out. Thanks in advance. 74626611 (Problem G(Candy Box) Hard Version)