By awoo, history, 20 months ago, translation,

Hello Codeforces!

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 sometimesnaive 6 176
2 SSRS_ 6 184
3 flowerletter 6 251
4 hank55663 6 255
5 Strigon-12 6 276

Congratulations to the best hackers:

Rank Competitor Hack Count
1 stdmultiset 133:-79
2 Tsovak 98:-10
3 dapingguo8 68:-6
4 MohamedAboOkail 65:-3
5 peti1234 60:-1
3590 successful hacks and 2569 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A Warawreh 0:01
B MysteryGuy2 0:04
C WZYYN 0:10
D peti1234 0:09
E CoderAnshu 0:06
F - -
G iaNTU 0:57

UPD: Editorial is out

• +376

 » 20 months ago, # |   -90 Please please please don't make it as hard as today's contest :/
•  » » 20 months ago, # ^ |   +17 Please don't do that, don't give me hope :)
•  » » » 20 months ago, # ^ | ← Rev. 2 →   -26 :(
 » 20 months ago, # |   -54 As a ......
•  » » 20 months ago, # ^ | ← Rev. 2 →   0 Do you want to get more contribution?say "as a"?
•  » » » 20 months ago, # ^ |   +4 i think u mean negative
•  » » 20 months ago, # ^ |   +16 He couldn't complete his sentence. Perhaps some big stone fell on him while he was typing. Sad.
•  » » » 20 months ago, # ^ |   0 Your ideas are ...
•  » » » » 20 months ago, # ^ |   0 Did a stone fell on you too OR .....
•  » » » 20 months ago, # ^ | ← Rev. 2 →   +1 And a small pebble fell on the "." key?
 » 20 months ago, # |   -26 Let the comments with "as a" begin
 » 20 months ago, # | ← Rev. 2 →   +21 I am new to Competitive programming, codeforces made me fall in love with it! Thanks to you all amazing people!
•  » » 20 months ago, # ^ |   +6 yes same
•  » » 20 months ago, # ^ | ← Rev. 2 →   +14 i tried everything to find my interests and nothing felt like i enjoy doing themas i started CP on codeforces 2 months back i feel like this is all i want to do for the next large amount of my time :) really thankful to the best internet community
•  » » » 20 months ago, # ^ |   +3 Same brother, initially I thought to first finish all Data Structures and Algorithms and then start CP, but doing it simultaneously is much better and helps retain concepts easily. Every new coder should start doing CP. (PS: Only if you don't mind your ratings dropping and you trust yourself enough, that one day, you'll make it.)
•  » » 20 months ago, # ^ |   -10 so Madara Uchiha saved you, huh.
•  » » » 20 months ago, # ^ |   +2 I killed him!
•  » » » » 20 months ago, # ^ |   0 But I think you were there to bring him back to life!!
•  » » » » 20 months ago, # ^ |   0 I killed OrochiMaru, Itachi
•  » » » » 20 months ago, # ^ |   0 no you didn't foolish kid.
 » 20 months ago, # |   -10 As a participant of today's contest kindly make the problems easier...
 » 20 months ago, # |   +4 I hope it will be a good round
 » 20 months ago, # | ← Rev. 2 →   -11 Hope for the nice contest!
•  » » 20 months ago, # ^ | ← Rev. 2 →   0 Lunch time is 30th right So no clash
 » 20 months ago, # |   +36 I will die if there will be adhoc problems in this contest too.
•  » » 20 months ago, # ^ |   0 Hahahhah did you also get burned by today's contest?
•  » » 20 months ago, # ^ |   -6 educational=(4problems or more)*adhoc XD
•  » » » 20 months ago, # ^ |   +62 That's a pretty bad equation, not gonna lie.
•  » » 20 months ago, # ^ |   0 what is adhoc?
•  » » » 20 months ago, # ^ |   +6 adhoc problems usually ask you to construct or to build something. Usually those problems can be solved without knowledge of algorithms. For example, you can check problem F from codeforces Round 640 div4. This is an example of ad-hoc problem.
•  » » » » 20 months ago, # ^ |   0 would adhoc be considered to be general-thinking problems?
•  » » » 20 months ago, # ^ |   +7 The problems on which you die thinking which algorithm to use while contest and then after looking at the editorial think .. "wait ... thats it ?"
•  » » » » 20 months ago, # ^ | ← Rev. 2 →   0 You mean, the less you know, the better off you are?
 » 20 months ago, # |   0 Hope,I will enjoy this round as today!
 » 20 months ago, # | ← Rev. 2 →   +24 FORTUNE COMMENT!
 » 20 months ago, # |   -21 My current rating is 401 will I be rated in this contest?
•  » » 20 months ago, # ^ |   +3 cout << "YES\n";
•  » » » 20 months ago, # ^ |   +3 Bro I am new to codeforces, please tell me based on my rating which all contest can I participate and be rated ?( Like div 1,2,3)
•  » » » » 20 months ago, # ^ |   +4 Div 2,3,Educational,Div1+Div2(combined rounds).
•  » » » » » 20 months ago, # ^ |   +3 Thanks bro
•  » » » 20 months ago, # ^ |   0 cout << (401 < 2100 ? "YES" : "NO") << '\n';
•  » » 20 months ago, # ^ |   0 Yes
 » 20 months ago, # |   +11 I am a newbie, it really made me happy that I could solve few problems. Looking forward to upcoming contests!
•  » » 20 months ago, # ^ |   -11 those who dont want jobs out of it will loose hope soon
•  » » » 20 months ago, # ^ |   +8 Well not getting a job when you are working hard is depressing but you have to believe in yourself, it can do miracles
•  » » » » 20 months ago, # ^ | ← Rev. 2 →   +5 well, recently a newbie girl I know received an offer from FAANG.
•  » » » » » 20 months ago, # ^ |   0 I am neither a newbie nor a girl, darkness awaits me.
•  » » » » » » 20 months ago, # ^ | ← Rev. 2 →   0 alright master man help me with my code please.. SEQ SPOJ i am getting WA i have spent the whole day trying to do this. doesn't work. any help is much appreciated. here is my code http://pastie.org/p/5RMR3nVahDVmrvyAUTIonz. nvm i solved it.
•  » » » 20 months ago, # ^ |   0 I'm in high school and do CP. And there are many others who don't want a job out of it. Problem-solving using DSA is fun!
•  » » » » 20 months ago, # ^ |   -12 well i am 2 nd year electrical engineer i do it to keep my brain sharp but our job is decided by such factors we tend to target on this site it all connects.and if u cant get anything out of it u will decay soon thats what i meant
•  » » » » » 20 months ago, # ^ |   +17 Depends on how you define 'anything'. For many people, there are more things in life apart from getting a job.
•  » » » » » » 20 months ago, # ^ |   -8 well u can eat sometimes without being hundry good for you
•  » » » » » » » 20 months ago, # ^ |   0 don't tell u have never eaten something even tho u were full? CP is a sport. Many people play football or any other sport without wanting to play for a club or a country.
•  » » » » » » » » 20 months ago, # ^ |   0 what would u call the release of serotonin when u win and the thrill when u loose ,u can eat but when u loose its the hunger that make u move forward ,ofcourse i am speaking on avg not on individual level but thats a fact
•  » » 20 months ago, # ^ |   0 Why are you so cute :')
 » 20 months ago, # |   +5 I hope i will become expert today..
•  » » 20 months ago, # ^ |   +3 hope i remain specialist today:)
•  » » 20 months ago, # ^ |   +6 hope i will become master one day:)
•  » » 20 months ago, # ^ | ← Rev. 3 →   +1 hope
 » 20 months ago, # |   -6 Hope to become specialist today
•  » » 20 months ago, # ^ |   0 Are you planning to cheat?
•  » » » 20 months ago, # ^ |   +7 no i am not like you
 » 20 months ago, # |   0 Hope the tasks aren't too hard, hope everyone can get a rating which can satisfy you :)
 » 20 months ago, # |   +55 There should be a third button IMO XD
•  » » 20 months ago, # ^ |   +6 There was but it got deprecated: HackForces. Now it's only present on Topcoder with name TopHacker.
•  » » » 20 months ago, # ^ |   0 Doesn't look like it.
•  » » » » 20 months ago, # ^ |   0 I meant for usual div 2 rounds. Usually educational rounds have more hacks because of longer and separate hacking phase.
•  » » 20 months ago, # ^ |   +2 MathForces!
•  » » » 20 months ago, # ^ |   +3 Oh just saw you already said it thanks a lot! Can we be friends?
•  » » 20 months ago, # ^ |   +3 And a forth: MathForces...
 » 20 months ago, # |   0 I hope i can solve first 2 problems quickly :)
•  » » 20 months ago, # ^ |   0 come on!
 » 20 months ago, # | ← Rev. 2 →   +1 Writing educational contests is really good way to develop. Thank you for this contest and good luck to everyone!
 » 20 months ago, # |   0 Hey Legend tell me how can i improve my skill on number theory ? in previous contest after lot of observation still i am not able to solve 3 and 4th problem
 » 20 months ago, # |   +5 hoping it to be a hard contest (and not containing math only ;-;)
 » 20 months ago, # |   +37 ( )
 » 20 months ago, # |   +251
•  » » 20 months ago, # ^ |   +26 This feels deep. You have my upvote sir
•  » » » 20 months ago, # ^ |   +6 Hello LostCow!!!
•  » » 20 months ago, # ^ |   0 Happened yesterday :) ...
•  » » 20 months ago, # ^ |   0 Hope this does not happen to me today .
•  » » 20 months ago, # ^ | ← Rev. 2 →   0 This is the most relatable meme I've seen on codeforces. Especially after yesterday's contest and today's.
•  » » 20 months ago, # ^ |   0 Couldn't relate more!
•  » » 20 months ago, # ^ |   0 Lose, not loose.
 » 20 months ago, # |   +1 Waiting for the contest which would take me to specialist :)
 » 20 months ago, # |   0 time to become green (hopefully)
 » 20 months ago, # |   +10 It will be a wonderful contest. Best wishes!
 » 20 months ago, # |   0 My chance for specialist.
 » 20 months ago, # |   0 As a contestant I wish you ALL THE BEST
 » 20 months ago, # |   +5 Hoping for a good contest!!
 » 20 months ago, # | ← Rev. 2 →   +3 Giving a contest after long time today ! Fingers Crossed..
 » 20 months ago, # |   +2 Best of luck to all :)
 » 20 months ago, # |   -21 A and B kinda sucked ngl
•  » » 20 months ago, # ^ |   +2 before contest i was confident that i will be successfull in protecting my specialist badge. after contest i am confident i will be successfull in getting demotion to pupil
•  » » » 20 months ago, # ^ |   0 My condition is also the same Brother.
•  » » 20 months ago, # ^ |   +2 Yeah, but I thought C and D made up for it!
•  » » 20 months ago, # ^ | ← Rev. 2 →   -11 Fu**ing B costed me 7 WA because of floats.
•  » » » 20 months ago, # ^ |   -8 That is why you should always work in integers if possible, if you are comparing $\frac{a}{b}\ge{\frac{c}{d}}$, compare ${ad\ge{bc}}$ instead. Watch some people like Errichto and you will pick up these things, it helps a lot.
 » 20 months ago, # |   0 the idiot tottered happily towards grey coder againIt's me I'm the idiot :)
 » 20 months ago, # |   -8 is educational contest rated for all or only for div2?
•  » » 20 months ago, # ^ |   0 only for div2
 » 20 months ago, # |   +16 B — balanced
 » 20 months ago, # |   0 I wasted literary 1 hour on problem C because I forgot typing else... GG I will always be silver...
 » 20 months ago, # |   0 How to solve C?
•  » » 20 months ago, # ^ | ← Rev. 2 →   +20 I solved C considering three cases: If we are at index 0, we only have one option, i.e. to start a cycle from here. If we are at the last index, we only have one option, i.e. to end the current cycle. If we are at an index in the middle: We check if b[index+1] == a[index+1]. If this is true, then we need to terminate the current cycle and start a new one We again have 2 options here. We can either continue the current cycle with the existing length summed with the Number_of_vertices[index] - 1 - (b[index+1] - a[index+1]). The next option is to start a new cycle from here with length b[index+1] - a[index+1]. The reason why this is always true is that the rest of the cycle remains unaffected by the choice we make at this index. Another option is to terminate the current cycle here after adding Number_of_vertices[index] - 1. Remember to add 2 every time you expand the current cycle to count for the edges used to link the chains together.
•  » » » 20 months ago, # ^ | ← Rev. 3 →   0 Fixed. I didn't handle the 6th case well.
•  » » » 20 months ago, # ^ |   0 I did same still got WA on test case 3, Can you help? The code is easy enough to understand.
•  » » » » 20 months ago, # ^ |   +8 Here's my code see if that helps.
•  » » » » 20 months ago, # ^ |   +8 Firsty, I think that you have messed up the implementation in the if-else condition. It is safe to swap b[i] with a[i] if a[i] > b[i[. This will help to get rid of those abs(). Also you are adding 1 - a[i+1] + c[i] - b[i+1] which should actually be c[i] - 1 - b[i+1] + a[i+1]. Lastly, you are not considering the case when we can start a new cycle from this index with length b[i+1] — a[i+1]. I corrected these things in your code and submitted which gets accepted. Link to the submission: https://codeforces.com/contest/1476/submission/105949955Hope it helps!
•  » » 20 months ago, # ^ |   +8 You can use some dp to store maximum length cycle including all vertices of a[i] as ans[i]. See my solution:https://codeforces.com/contest/1476/submission/105907608
•  » » 20 months ago, # ^ |   +8 It can be solved by dp; firstly, let dp[i] denote the longest length at ith chain, "the longest length" means the longest length you can get before the cycle is formed, so we can get dp[i]=max(dp[i-1]+c[i]-1-abs(a[i+1]-b[i+1])+2,abs(a[i+1]-b[i+1])), then we update the answer by dp[i-1]+c[i]+1. one thing to be noticed is that when a[i+1]=b[i+1], dp[i] should set to 0. #include #define ll long long #define pb push_back #define FULL(x,y) memste(x,y,sizeof(x)) using namespace std; const int N=100005; int t,n; ll c[N],a[N],b[N],dp[N]; int main() { cin>>t; while(t--) { cin>>n; for(int i=1;i<=n;i++) cin>>c[i]; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) cin>>b[i]; for(int i=1;i<=n;i++) { dp[i]=0; } ll ans=0; dp[1]=abs(a[2]-b[2]); for(int i=2;i
•  » » » 20 months ago, # ^ |   0 I just realized my approach wasn't greedy at all. It's just DP without a DP array. Yeah, I solved it btw.
 » 20 months ago, # |   +1 Was I the only one who went into C and D thinking that they are graph problems, but both of them turned out to be dp ones? :P
•  » » 20 months ago, # ^ |   0 I thought so, but after seeing that the length of the chain can be 1e9, I knew it wasn't a graph problem.
•  » » 20 months ago, # ^ | ← Rev. 2 →   0 Yes, C isn't greedy.
•  » » » 20 months ago, # ^ |   0 There might be a greedy algorithm to it, but I solved it by trying all possibilities using dp
•  » » » 20 months ago, # ^ |   0 I think it's greedy I got AC using greedy.
•  » » » » 20 months ago, # ^ |   0 Nice, I also did greedy but it failed on testcase 3.
•  » » » » » 20 months ago, # ^ |   0 I failed on testcase 3 also in 1st attempt , you're probably missing the edge case.
•  » » » » » » 20 months ago, # ^ |   0 can you tell the edge case your code failed the first time? I can't understand the logic of why you put the cur=max(cur,y-x+1); in your passed attempt.
•  » » » » » » » 20 months ago, # ^ |   0
•  » » » » » » » » 20 months ago, # ^ |   0 Thank you. For some reason, I thought that this case is covered on ans=max(ans,cur+c[i-1]); this part of your code. Thank you
•  » » » » » » » » » 20 months ago, # ^ |   0 Yeah, I need to learn to write clean code ;), I put so many max conditions that were not necessary at all xd.
•  » » » » 20 months ago, # ^ |   0 there is not much difference between greedy and dp in this problem because you are accessing only the values from the previous index.
•  » » 20 months ago, # ^ |   0 I solved it using greedy.
•  » » » 20 months ago, # ^ |   0 Could you tell me your approach?
•  » » » » 20 months ago, # ^ |   0 You can refer to this comment: https://codeforces.com/blog/entry/87282?#comment-755104
 » 20 months ago, # |   +3 How to solve D?
•  » » 20 months ago, # ^ | ← Rev. 2 →   +3 Note that the structure of the graph only depends on the parity of time elapsed. Therefore, we can use $(node, parity)$ as stage and use DSU to maintain the reach-ability between stages and the sizes of connected components.
•  » » 20 months ago, # ^ | ← Rev. 2 →   +14 Make a left_c and a right_c array which represents the maximum number of cities city i can traverse that lie strictly on it's left and it's right respectively. Then, notice that if there lies a path b/w city i and city i-2, then city i can traverse all those different cities that city i-2 can because at time t and time t+2, all paths are exactly the same. If there just exists a path b/w city city i, and city i-1, then increment one to the left_c array for the city i. And, do similar things for right_c.Answer for the i_th city is left_c[i]+right_c[i]+1You can check my submission
•  » » » 20 months ago, # ^ |   0 Okay,understood! Thanks for the explanation!
•  » » » 20 months ago, # ^ |   0 What means "b/w city"?
•  » » » » 20 months ago, # ^ |   0 between city*
•  » » » 20 months ago, # ^ |   0 My idea was the same. You can check my implementation with regex (with eval-groups inside) — 105956225.
 » 20 months ago, # |   0 How to solve A? I'm new here...
•  » » 20 months ago, # ^ | ← Rev. 2 →   0 take range of get the smallest number x with x*n >= kor if n > k : x*n >= ceil(n/k)*k
•  » » » 20 months ago, # ^ |   0 How to think for such solutions?
•  » » » » 20 months ago, # ^ |   +8 "disclaim: It took long time for me :("-the first observation is that the smallest value for n positions is : 1n,2n,3n,4n, ...say you have n = 3 and k = 11 => 1,6,9,12 , 15,... you can get 11 by replacing 4 by three 4,4,4,3.-so you can get any lower values of x*n by replacing on or more x by lower valueyou should take into account n > k
•  » » » » » 20 months ago, # ^ |   0 Comment section is filled with amazing people! It's motivating :)
•  » » » » » » 20 months ago, # ^ |   +3 watch the stream, it's very helpful
•  » » » 20 months ago, # ^ |   0 nope.Lets consider two cases: n >= k. if n is divisible by k, you simply set everything to 1. otherwise, you set some of the numbers to 1, some others to 2, so that in effect you have added "enough 1s to make n divisible by k. n < k. There is no point in making the sum any bigger than k and by pigeon hole principal, at least one of the numbers will be ceil(k / n). As (ceil(k / n) * n) >= k, it suffices to subtract some amount from some of the numbers to make the sum equal to k.
•  » » » » 20 months ago, # ^ |   0 Does nope mean that I did it wrong? n >= k then k = ceil(n/k)*k and do the same thing.
•  » » 20 months ago, # ^ |   0 Basically the idea is take 2 coditions- 1-if n<=k Here of course ans is n/k if(n%k)==0 and n/k+1 if it is not equal to zero because imagine sum consisting of 1,1,1... and then remaining will be added acc from first. 2-if n>k Basic idea is as n>k, bring k multiple as close as possible to the smallest number greater than n so that is eventually again satisfies the first condition and then proceed as if it is now a case 1.Hope u get the idea Here's the sample for case 2- Spoilerlong y = (n / k) + 1; long r = y * k; long y1 = r / n; long u = r % n; if (u != 0) { printWriter.println(y1 + 1); } else { printWriter.println(y1); } 
•  » » 20 months ago, # ^ |   0 Here's some one liner code for ya (k - n % k + n - 1) / n + (n % k != 0)
 » 20 months ago, # |   0 Any hint for A?
•  » » 20 months ago, # ^ |   0 find nearest integer >=n which is divisible by k say x, ans=ceil(x/n)
 » 20 months ago, # |   +26 Omg -141 delta for meQuestion D is far more simpler to me compared to question B and C :/
•  » » 20 months ago, # ^ |   0 I had a terrible day too!At least some previous contests had interesting problems I could not solve and I got negative delta, but this one was Painfully pointless to me :(
 » 20 months ago, # |   +9 my contest in 1 photo :
•  » » 20 months ago, # ^ |   0 the division with 1 huh? Yes it took me some time as well. But no worries mate I lost 1 hour on C not because I could not find the solution but just because I forgot a simple 'else' statement. Look at my submissions on C if you don't believe. Like what separates the successful from the unsuccessful I believe is just the ability of removing the blindness effect that I don't even know what casts it upon us. It's like we are in a MOBA arena and we have a passive ability of getting blinded for 1 hour randomly. We can be blind friends together hit me up if you ever want us to do a Virtual Contest together and then laugh at our blindness.
•  » » » 20 months ago, # ^ |   0 Not really. First I tried binary search and now i am wondering what was wrong on that solution, after i found some interative solution but i used the wrong formula :) .
•  » » » » 20 months ago, # ^ |   0 Ah sorry I just realized you stuck on B and not A. My bad. Anw I solved B without binary search I would be very interested to see how it is solved with binary search.
•  » » » » » 20 months ago, # ^ | ← Rev. 2 →   0 first you have to observe that the solution is to add some number just to p0. Now ,let x be the solution and you can find it with binary search. For each x, check if can be a solution. If not, have to increase x, otherwise ,decrease it. The article in EDU about binary search is very nice, I ve learned a lot from that one.
•  » » » » » » 20 months ago, # ^ |   0 Oh this is smart but it requires more complexity than the linear solution. Still very smart nevertheless. 105884577
•  » » » » » » 20 months ago, # ^ |   0 I just read you solution. It is linear as well. Oh I can see where it got hard maybe when you where trying to calculate how much to add. I just did a max there since the maximum is what you need. Damn I could rank up so much in this round had I been a little more careful.
•  » » » » » » » 20 months ago, # ^ |   0 my binary search solution : CODE
•  » » » » » » » » 20 months ago, # ^ |   0 Yes so it is O(nlogn). It just instead of doing the division and checking for the modulo that I was doing you do the BS to find the correct value.
•  » » 20 months ago, # ^ |   0 Bro how did multiplying by 100LL instead of 100 get the answer in B ?
•  » » » 20 months ago, # ^ |   0 because your variables are int, and 100*1e9 = 1e11 and this value for int is overflow
•  » » » » 20 months ago, # ^ |   0 If all variables and array are taken as long long. Will it still overflow ?
•  » » » » » 20 months ago, # ^ |   0 nope, should work fine.
 » 20 months ago, # |   -13 Don't you think the copying during contests is increasing day by day?Also there are many smurfs account in the contest. Affects rating of a lot of people
•  » » 20 months ago, # ^ |   0 Who is copying?
•  » » » 20 months ago, # ^ | ← Rev. 6 →   +1 AkashRamjyothi1 see his solutions 105874881 : A105895241 : B105915359 : C105929955 : Dwhile(true){ int abc = 0; abc++; abc++; abc--; break; }He is using these lines to save his code.awoo, MikeMirzayanov please look into it
•  » » » » 20 months ago, # ^ |   +6 In order to check if a program is a copy of another one, can't the program be subjected to run on a set of deliberately faulty test cases during system testing? Programs whose behaviors, that is, the errors/exceptions they throw, the current values of all present variables, and the variable names in use, are the same for all test cases can then be weeded out...
 » 20 months ago, # | ← Rev. 2 →   +154 You are asked to rearrange the patterns in such a way that the first pattern the j-th string matches is p[mtj].This is ambiguous. I thought it meant the rearranged patterns index mtj, causing me to write completely wrong code.
•  » » 20 months ago, # ^ |   +21 Same here
 » 20 months ago, # |   +7 E was really nice. for each string s, for all the patterns that matches it, I put a directed edge from the first pattern it should match (mt for that string) to every other pattern that matches it and the answer is YES if the graph formed is a DAG?
•  » » 20 months ago, # ^ | ← Rev. 3 →   0 I thought the same but dismissed it quickly because how is that not TLE? Each string can match to potentially all $m$ patterns. So $O(m^2)$ sized graph (or DAG) right there? The only explanation I can think of is that maybe because of the contraint that each pattern is distinct this bound can be tightened? Do you have the proof?EDIT: Oh got it. smh. Each string can only match to atmost 16 patterns (because of distinctness constraint) so size of graph is bounded $O(m)$.
•  » » » 20 months ago, # ^ |   0 According to the question, all patterns are distinct. For a string s, given its maximum length is 4, we can have at most 2^4 + 1 patterns that match it (for all binary numbers from 0 to 2^4, if $ith$ bit is 1 then keep s[i] as it is, else replace it with '_').
•  » » » 20 months ago, # ^ | ← Rev. 2 →   0 A string can match with at most 2^k patterns. Let's take an example string "abc". Which patterns can it be matched with? "abc", "a_c", "ab_", "a__", "_bc", "__c", "_b_", "___" So, for each position of a string, we can either keep the original letter as it is, or replace it with '_'. so, for this reason a string can match with at most 2^k patterns.
•  » » 20 months ago, # ^ |   0 Yes, and the answer is the topological sort of the DAG.
 » 20 months ago, # | ← Rev. 2 →   -6 .
 » 20 months ago, # |   0 Can someone please tell me why is my code failing, I did a 2 way kadane-ish dp and printed their sum. WA_CODE
•  » » 20 months ago, # ^ |   0 The dp seems to be off by one, since the indices go up to $n$ (as there are $n + 1$ cities).
 » 20 months ago, # |   +7 I think problem B needed more tests, although figured out how to get 99 on test 1 it doesn't seem like it for the other tests.
 » 20 months ago, # |   0 The most educational things I learnt from A and B is that don't forget to use ceiling when comparing
•  » » 20 months ago, # ^ |   0 Yeah same, Costed me 7 WA for B ;)
 » 20 months ago, # |   +49 The hardest part of E was understanding it. Nice problem set though, thank you!
•  » » 20 months ago, # ^ |   +18 I still didn't understand the problem. Can you explain it?
•  » » » 20 months ago, # ^ | ← Rev. 2 →   +40 Let the initial arrangement of patterns be $P$. Your goal is to find an arrangement of patterns $P'$. $P'$ is such that, for each string $s_j$, the first pattern in $P'$ that matches with $s_j$ is $P[mt_j]$.
•  » » » » 20 months ago, # ^ |   +47 That how it should be written in the statement! As for me, it was absolutely unclear that s[j] matches P[mt[j]], and P remains the same. Maybe I misread something, but it seems there is no contradiction if you understand that part of statement differently
•  » » » » » 20 months ago, # ^ |   +23 Reading it again, I feel it was somewhat clear what they meant. In my hurry to read it, I misunderstood and wasted 45 minutes on solving a different problem. Perhaps the problem statement should have held your hand a bit to be completely clear (like I did in my statement). I can't complain too much though, it's my fault I didn't read it closely enough.
•  » » » » » » 20 months ago, # ^ | ← Rev. 2 →   +53 At least that other understanding doesn't pass samples. That was the point at which I figured out that something is wrong: coding is done, I fail first sample, OK let's actually look at the samples now...
•  » » 20 months ago, # ^ |   +3 Yeah I wouldn't understand if there were no sample testcases.
 » 20 months ago, # |   0 In Q2 multiplying by 100LL instead of 100 got me AC. Any reasons why ?
•  » » 20 months ago, # ^ |   +3 Integer overflow
•  » » » 20 months ago, # ^ |   +3 Any article or reference on the same ? Costed me 6 WA.
•  » » » » 20 months ago, # ^ |   0 $p_i$ can be up to $10^9$ so $p_i\times 100$ can be up to $10^{11}$. Max int is usually $2^{31}-1$, which is slightly above $2\times 10^9$.
•  » » » » » 20 months ago, # ^ |   0 Can you please tell me why I got an overflow even after taking the entire array as long long https://codeforces.com/contest/1476/submission/105897736On changing 100 to 100LL I got AC.... Can't understand why!! Thanks In advance
•  » » » » » » 20 months ago, # ^ | ← Rev. 3 →   0 you are getting overflow on your tmp variableUPD: got AC here
•  » » » » » » » 20 months ago, # ^ |   0 YES GOT IT!!
 » 20 months ago, # |   +18 imagining C graph cases gave me a headache but I liked this contest you have my upvote
 » 20 months ago, # |   -14 F, I wasted 1+ hour on B because I completely forgot that division by int rounds down :(
 » 20 months ago, # |   +33 How to solve G?
•  » » 20 months ago, # ^ |   0 Mo's algorithm
•  » » » 20 months ago, # ^ |   0 Take a look of this problem and its solution.https://codeforces.com/contest/700/problem/D
•  » » » » 20 months ago, # ^ |   0 How can we see its solution?? Its editorial isn't available.
•  » » » » » 20 months ago, # ^ |   0 Well, you can find some solution of the contestants in the comments.
•  » » 20 months ago, # ^ |   0 only $O(\sqrt n)$ different values in the cnt array, so then apply Mo's algorithm to it and use a list to maintain different values in cnt, and then for each query take out all values and brute forcetotal complexity is $O(m\sqrt n\log n+n^{5/3})$.
•  » » » 20 months ago, # ^ |   0 But i am unable to handle the updates. Please elaborate.
•  » » » » 20 months ago, # ^ |   0 I'm assuming you know how to handle the problem without updates (using Mo's).To handle updates, split the queries (type 1+2) into blocks. Now, within each block, run Mo's. When you start processing a block, make sure that all the updates in the preceding blocks have been applied. To account for the updates in this block for a query of type 1, you can naively iterate from the start of this block applying all applicable type 2 queries. Since you broke it down into sqrt(m) blocks initially, it is guaranteed that you'll only iterate block_size times at max even when doing updates naively for each type 1 query.You might need to fiddle a bit to find the appropriate block size though.
•  » » » » » 20 months ago, # ^ |   0 You mean for every block run Mo's naively?? Then for every block it should be $O(N*sqrt(N))$. Please correct me if I am wrong.
•  » » » » » » 20 months ago, # ^ |   0 Google "Mo's algorithm with update"
 » 20 months ago, # |   0 In C what does this mean that "First chain is skipped", does this mean we cannot take any node from first chain? I had initially set the ans to c[0]. That was the only reason I was not able to solve C and costed me wrong ans :)). First chain skipped means I thought I cannot connect any node to previous ones, otherwise I can taken some nodes from first chain.
•  » » 20 months ago, # ^ |   0 your last nodes can be in first chain.It means your cycle can't go above it.
 » 20 months ago, # |   0 God I could have solved B if I had 30 more sec... I submitted right after the contest ended and got AC :( Spent 60+ mins to figure out why my solution got WA... I really get mad at myself
•  » » 20 months ago, # ^ |   0 I believe we both made the same mistake :(, but I was able to submit it just before the contest finished.
 » 20 months ago, # | ← Rev. 2 →   0 Can Anybody Please give Me some counter test case i.e., Fail My CodeQuestion LinkSolution LinkI tried Everything but not able to find any counter case, Also did Stress testing, Still Not able to find it.
•  » » 20 months ago, # ^ |   0 try to use multiplication instead of division in check, that can be a problem.
•  » » » 20 months ago, # ^ |   +6 Yes got accepted after doing this, Thank-you so much brother
 » 20 months ago, # |   0 Why was my submission not uploading after 10 PM. Ugh I don't get it. Now my rating will decrease without any reason, man!
 » 20 months ago, # |   +3 How to solve E?
•  » » 20 months ago, # ^ |   0 Take a look at this comment
•  » » 20 months ago, # ^ |   +21 If there are multiple $p_i$s match the same $s_j$, then the specified constraint is basically implying the specified pattern exists before all other $p_i$s. Thus, we can keep track on the indices of patterns and build a dependency graph based on the constraints. For any specific $s_j$, there would be at most $2^k$ distinct patterns matching it. Thus, at most $2^k$ edges would be added to our dependency graph. Hence, the problem is reduced to check if a given directed graph with $n$ vertices and at most $m\times 2^k$ edges is acyclic, and if so, report any topological order. This can be solved by topological sort.There are a few trivial cases to notice, like the specified pattern not matching the given string or different occurrences of the same string being matched by different patterns, you may refer to my submission 105914103 for implementation details.
 » 20 months ago, # |   -21 I was unable to sove even Problem A, can some one say the intuition to problem A. I tried binary search for problem B, but it did not pass 3rd test case for i in range(int(input())): n,k=[int(i) for i in input().split()] arr=[int(i) for i in input().split()] prefixSum=0 ans=0 for i in range(len(arr)-1): prefixSum+=arr[i] if (arr[i+1])*100<=k*prefixSum: continue else: Min=1 Max=(10**9)+1 posible=Min while Min<=Max: mid=Min+(Max-Min)//2 if (arr[i+1])*100<=k*(prefixSum+mid): posible=mid Max=mid-1 else: Min=mid+1 ans+=posible prefixSum+=posible print(ans) 
•  » » 20 months ago, # ^ |   0 Try 1 2 1 1 1000000000
•  » » 20 months ago, # ^ | ← Rev. 2 →   0 For problem A: we are need minimum sum that can be divided by k. Let find that sum.sum = ceil(n / k) * k;After we know sum, we need to spread it to cells, that each element was minimum possibleansw = ceil(sum / n);
•  » » 20 months ago, # ^ |   0 Increase the Max value.
•  » » 20 months ago, # ^ |   0 Consider all array elements to be 1. We need to increase these numbers until the sum is divisable by k. So, first step is to find the next multiple of k bigger or equal to n. Second step is to find the max array element if the sum equals the number found in first step.
•  » » 20 months ago, # ^ |   0 I learned this the hard way — 99% of the time you don't need this big code for problem A. You probably need to take a deep breath and think at more fundamental level what the question is really asking.
•  » » » 20 months ago, # ^ |   -31 And my solution got hacked. To all the losers making hacking attempts, go fuck yourselves.
•  » » » » 20 months ago, # ^ |   +3 It would probably have failed system tests anyways so I don't think it matters.
•  » » » » 20 months ago, # ^ |   +3 Here's a tip for you $\lceil \frac x y \rceil = \lfloor \frac {x + y - 1} y \rfloor$
 » 20 months ago, # |   -10 simple dp for C . a is vector of heights , b and c are vector of endpoints connecting to previous. we have to recompute this dp between all the inclusive indices of where b[i+1]!=c[i+1]dp[i]=abs(b[i+1]-c[i+1])+1 +max(a[i+1],dp[i+1]-1-abs(b[i+2]-c[i+2])+a[i+1]+1-abs(b[i+2]-c[i+2]));simple code. code#include using namespace std; typedef long long int ll; #define endl "\n" ll a[500001],b[500001],c[500001],dp[5000001],pre[500001]; ll sol(vector a, vector b,vector c) { ll n=a.size()-1; ll i,j,k=0,l; vector dp(n+1); dp[n]=a[n]; dp[n-1]=abs(b[n]-c[n])+1+dp[n]; ll ans=dp[n-1]; // cout<=1;i--) { dp[i]=abs(b[i+1]-c[i+1])+1 +max(a[i+1],dp[i+1]-1-abs(b[i+2]-c[i+2])+a[i+1]+1-abs(b[i+2]-c[i+2])); //cout<>n; for(i=1;i<=n;i++) { cin>>a[i]; } for(i=1;i<=n;i++) { cin>>b[i]; } for(i=1;i<=n;i++ ){ cin>>c[i]; } vector v; ll prev=1,ans=0; b[n+1]=1; c[n+1]=1; for(i=2;i<=n;i++) { if(b[i+1]==c[i+1]) { vector bb={0},cc={0},aa={0}; for(ll j=prev;j<=i;j++) { bb.push_back(b[j]); cc.push_back(c[j]); aa.push_back(a[j]); } ans=max(ans,sol(aa,bb,cc)); prev=i; } } cout<>t; while(t--) { solve(); } return 0; } 
 » 20 months ago, # |   +17 Were F and G intended to be that much hard??
•  » » 20 months ago, # ^ |   +17 I'm really surprised nobody solved F. I've been rechecking and stressing my solution for hours, and I'm still sure it is correct, but it's strange that nobody got this problem.
•  » » » 20 months ago, # ^ |   0 How to solve it? Is it dp(i, j) — farthest covered positon to the right if we have processed i first positions and j is the farthest to the left uncovered position, with segment tree? Or it is wrong?
•  » » » » 20 months ago, # ^ | ← Rev. 2 →   +34 $dp_i$ — the maximum prefix we can fully cover with $i$ first lanterns.Let's look at how can we solve it in $O(n^2)$ with this kind of dynamic programming. First of all, let's write it forward. Which transitions from $dp_i$ do we have? iterate on the lantern facing left that will cover the lantern $dp_i + 1$. Let this lantern be $j$. It should cover all lanterns in $[dp_i + 1, j - 1]$, so all lanterns from $[i, j)$ can be turned to the right (and we need a max query to determine the new covered prefix); if $dp_i > i$ (lantern $i$ is already covered), we can just extend the prefix by turning the $i$-th lantern to the right. Note that turning it to the right when it is not covered yet will be modeled by the first transition. It is obviously $O(n^2)$, how can we optimize it? Let's write this dynamic programming backward. The second transition is changed to backward dp easily, what about the first one? Suppose we want to turn some lantern $i$ to the left. Let's iterate on the prefix $j$ that we will "connect" to it; for this prefix, $dp_j$ should be at least $i - p_i - 1$, and we update $dp_i$ with the maximum of $i - 1$ (since it is covered by lantern $i$) and the result of max query on $[j + 1, i - 1]$.In fact, we need only one such prefix — the one with the minimum $j$ among those which have $dp_j >= i - p_i - 1$. So, we build a minimum segment tree where each pair $(i, dp_i)$ is interpreted as the value of $i$ in position $dp_i$, and with min query on the suffix from $i - p_i - 1$ we find this optimal prefix, from which we should update (and to update, we can use any DS that allows max queries on segment — in my solution, it's another segment tree).Source code
•  » » » » » 20 months ago, # ^ | ← Rev. 3 →   +16 I was able to upsolve using what I think is a different DP, with $O(n \log n)$ distinct transitions, so both solutions are probably correct. Yours is definitely a much easier idea to implement.I reached my idea by supposing for some $i$ that every lantern in $[0, i]$ has had its direction chosen and lantern $i$ is the first unilluminated lantern. Then, there must be some lantern $j > i$ which is turned left to illuminate lantern $i$, after which the set of lit lanterns is a prefix, and every un-set illuminated lantern would thus be wasted unless turned right, which lets me greedily illuminate every lantern less than some value $k$. If $k = n$, that is a success; if $k = j$ then $k$ is facing left; otherwise $k$ may as well face right.It then turns out that there are at most $1 + 3 \log_2 (n-i)$ meaningfully distinct choices for $j$, and these are "easy enough" to iterate over: If $j$ is not the farthest-right-reaching lamp in the $[i+1, k)$ interval, no other value of $j \in [i+1, k)$ can possibly get a better value of $k$. But $k$ is at least 2 times farther from $i$ than the previous usable value of $j$ was! So the worst-case progression looks something like $j_0$, then $j_1$ (furthest reach in $[i+1, k_1)$), then $j_2 < k_1$, and then $j_3 \geq k_1 > i + 2 * (j_0 - i)$.Submission link: 105953208
•  » » » » » 20 months ago, # ^ |   +8 I had the same idea after the contest. You can simplify the code by doing some observations: $Dp[N]$ is going to be increasing, so you can do a binary search instead of a segment tree To do that max query on the lanterns that go to the right you can just use a sparse table that you can actually compute while reading the lamp powers. With those observations, I managed to get my code size at a little below 100 lines.Submission: 106013279
 » 20 months ago, # |   +10 Fs in the chat for question F
 » 20 months ago, # | ← Rev. 3 →   0 When "vovuh" is one of the writer then contests are awesome!!! Thanks for another good contest :-))
 » 20 months ago, # |   0 can someone say y my solution failed? i am confident logic is somewat rite. solution logic: cross multiplying the equality a*100<=k*sum and checking if condition false, add differnce to overall sum
•  » » 20 months ago, # ^ |   0 We have the same mistakeit should be (a[i]*100LL-k*s + k - 1) / kdon't ask me why :(
•  » » » 20 months ago, # ^ |   -187
•  » » » » 20 months ago, # ^ |   +25 dude don't do this
•  » » » » 20 months ago, # ^ |   +59 Hey, I understand that you want to make a point, but don't you think tagging is unnecessary? I believe noone likes to be tagged just to be asked to debug someone else's code.
•  » » » » 20 months ago, # ^ |   0 you assume that a[i]*100LL-k*s == a[i]*100LL/k - s
•  » » 20 months ago, # ^ |   0 You should add (difference/k) to the overall sum and ans.
•  » » 20 months ago, # ^ |   0 try this you will understand why.12 1001 2
•  » » » 20 months ago, # ^ |   +1 The authors should put a good sample cases, it's educational round not destroying roundbad people in math (like me) will not figure out the division when k = 1
 » 20 months ago, # | ← Rev. 2 →   0 How can the answer of this case of problem C be 4?33 3 3-1 2 3-1 2 3Can anyone please explain what I am missing?
•  » » 20 months ago, # ^ |   +3
 » 20 months ago, # |   +8 How many tests will problem A have? There're 1000+ hacks...
•  » » 20 months ago, # ^ |   +7 I think the authors should manually look at the hacks and form some set of new testcases which cover all the corner cases, otherwise system test will continue for eternity.
 » 20 months ago, # | ← Rev. 2 →   +4 Finally a time for me to be on the "+11" side of a widespread hacking event :DI am deeply sorry for the people who got hacked though, I've been hacked multiple times before and I know exactly how that feels.
•  » » 20 months ago, # ^ |   0 No you are not sorry, so stop pretending ffs.
 » 20 months ago, # |   0 brilliant contest! Thank you
»
20 months ago, # |
-46

this is my code for 2nd question inflation can anyone help where is the problem

include<bits/stdc++.h>

using namespace std; int main() { int t;cin>>t; while(t--) {int n,k; cin>>n>>k; long long sum1=0;long long sum=0; long arr[n]; for(int i=0;i<n;i++) {cin>>arr[i]; sum1+=arr[i];
} sum=arr[0]; for(int i=1;i<n;i++) { if((arr[i]*100-k*sum)<=0) { int c=1; } else { long long d=arr[i]*100/k; sum+=d-sum; while((arr[i]*100-k*sum)>0) {sum++;} } sum+=arr[i];

}
cout<<(sum-sum1)<<"\n";
}

}

 » 20 months ago, # |   +35 In problem E, "You are asked to rearrange the patterns in such a way that the first pattern the j-th string matches is p[mtj]." doesn't clearly state that index mtj is referred for initial arrangement.It should have been stated clearly.
 » 20 months ago, # |   0 How to generate hack test cases? I am trying to hack A with highest constraint, i.e. T=1000, K=1, N= $10^9$, but still solution passes
•  » » 20 months ago, # ^ |   0 bruh check for corner cases when k=1 in code.
 » 20 months ago, # |   +6 C was harder than D
 » 20 months ago, # |   +16 Problems were good, I liked how ABC needed more thinking than coding and more thinking speed than typing speed.It was an interesting contest even tho problem D was a standard one LOL.
 » 20 months ago, # | ← Rev. 4 →   -39 thank u guys for 'A's weak pretests... :'((((((((((((((
 » 20 months ago, # |   0 As a...... As a novice at code/algorithm， I like codeforces! It's amazing and I like the feel to try my best to solve the problem... also I can't solve D which made me sad
 » 20 months ago, # |   0 It was hard and my solution on GNU C++17 64 bits FAILED BUT SAME SOL. ON C++17 PASSED...LOL
 » 20 months ago, # |   +22 My standard screencast, with the standard tradition of misreading at least one problem
 » 20 months ago, # |   +9 Nice pretests for A, as an tradition of Educational Rounds.
•  » » 20 months ago, # ^ |   0 Felt you
 » 20 months ago, # |   0 As well as all of the other educational rounds
 » 20 months ago, # |   0 is there any extra points for hacking in educational rounds ?
•  » » 20 months ago, # ^ |   0 No, it's not
•  » » » 20 months ago, # ^ |   0 Are there any ... ? No, there are not.
 » 20 months ago, # |   0 thanks for great contest (i have 51 hacking successful =)) )
 » 20 months ago, # |   +13 Just one thing: was it really necessary to have a two-letter variable like $mt_{j}$? First I saw that there is an $m$ variable, so I immediately interpreted $mt_{j}$ as $m\cdot t_{j}$, and that didn't help at all. I mean, I would understand $match_{j}$, but $mt_{j}$?..
•  » » 20 months ago, # ^ |   +1 And they also didn't specify which p they are talking about, the changed one or original.
 » 20 months ago, # |   0 I thought p[mtj] is a pattern after permutation :(.
 » 20 months ago, # |   +20 I have to congratulate the setter of problem G. My solution looks like something well known, but I've never did something like that before. Really nice one, I definitely learned new stuff today. Thank you!
•  » » 20 months ago, # ^ |   0 What's your solution?
•  » » » 20 months ago, # ^ |   +38 I used Mo's algorithm. I didn't know about the trick to handle updates. A brief explanation of my solution:Keep track some stuff: $cnt[x]=$ how many times number x appears in the range. $tot[x]=$ how many numbers occurs x times in the range. $vals=$ vector of distinct numbers in array cnt. It's really easy to update $cnt$ and $tot$ when you add/remove an element. For $vals$, simply push all the values to the vector while moving Mo's pointers, and after that remove values the ones that are irrelevant (those for which tot[x]=0). Also, avoid pushing an element to $vals$ twice. It's easy to see that after doing that, $|vals|<=\sqrt{n}$, because all elements are distinct and their sum is $<=n$.Using the fact that $|vals|$ is small, you can answer the query with two pointers over the array $vals$.
•  » » » » 20 months ago, # ^ |   0 What is the complexity of this implementation? I can't understand the amortized analysis of the update part
•  » » » » » 20 months ago, # ^ | ← Rev. 2 →   +8 when you use Mo's algorithm with updates, you have you use size of blocks $S=n^{2/3}$. In fact, i read somewhere that it's optimal to use $S=(2*n^2)^{1/3}$.Time complexity for addittion/removal of elements and push/rollback of updates is $O(S*(n+q))$ amortized.Time complexity for iterating elements and removing values form $vals$ is $O(S*(n+q))$ amortized, because each operation pushes at most one element to the vector.Time complexity for answering queries after removing irrelevant elements from $vals$ is $O(q*sqrt(n)*log(sqrt(n)))$ because you need to sort the vector of unique values before using two pointers method.So, total time complexity is $O((n+q)*(S+sqrt(n)*log(sqrt(n))))$. Please notice that this analysis uses the fact that $S \approx n^{2/3}$ (not $sqrt(n)$). In practice, the solution works a lot faster (my code runs in 1500 ms).
•  » » » » » » 20 months ago, # ^ |   +8 For those interested in the details about complexity of Mo's algorithm with updates, there is a really nice blog, written by Fype, that explains everything :)
•  » » » » » » 20 months ago, # ^ |   0 Thank you for the explanation.
 » 20 months ago, # |   0 Great contest. Problems are interesting and educational. I enjoyed solving them.
 » 20 months ago, # | ← Rev. 2 →   0 I don't know why, but I feel like at least 1 of my 4 problems will fail system testing :(
 » 20 months ago, # |   0 For Problem C i've included all border cases , still I'm getting WA, can someone please tell me what's wrong or give a test case on which my code fails ??
 » 20 months ago, # |   0 The penalty for each incorrect submission until the submission with a full solution is 10 minutes can someone explain what this 10 minutes penalty mean? and if we submit the correct solution after certain incorrect submissions there will be no penalty right?
•  » » 20 months ago, # ^ |   0 No. Penalty means that if you submit a correct solution, you get the time for that solution plus the penalty. That is 10 minutes per submission, buf the first submission is for free.
•  » » » 20 months ago, # ^ |   0 got it thank you
 » 20 months ago, # |   0 Will it system test later,or just announce the final standings after the hacking time?
 » 20 months ago, # |   0 Can someone please tell me what error is there in my logic for this. I check for all elements in reverse order if the increase coeeff <= k and if its not I increase p0 by a sufficient amount. Link to soln: https://codeforces.com/contest/1476/submission/105888794
 » 20 months ago, # | ← Rev. 4 →   -12 Difference between right and wrong in Question A double n,k; cin>>n>>k; if(k
•  » » 20 months ago, # ^ |   0
 » 20 months ago, # | ← Rev. 4 →   -10 Your code here...  `ll n,k,val; cin>>n>>k; vector pre,a(n); ll sum=0; loop(i,0,n) { cin>>a[i]; sum+=a[i]; pre.pb(sum); } ll add=0,maxadd=0; loopeqr(i,n-1,1) { val=a[i]*100-k*pre[i-1]; if(val>0) add=ceil(val/(k*1.0)); maxadd=max(maxadd,add); } cout<
•  » » 20 months ago, # ^ |   0
 » 20 months ago, # | ← Rev. 2 →   0 hiI really need help therefore I really couldn't understand what is the problem with the code which outputs that kind of format in test 3 problem b(but in math the number is correct)submission:105899297and its not just only mineanother submission of another person:105852796help please
•  » » 20 months ago, # ^ |   0 In C++, when a really large double is divided by a small number, it changes into the scientific notation. To avoid this, explicitly convert the double to a long long int or int as required in the problem.
•  » » 20 months ago, # ^ |   0 when you use double then if your ans is large it tend to represent ans in power of e notation .So to avoid it you can name your variable as long long int or when you are printing ans just typecast the ans i.e cout<<(long long int)ans<<" "
 » 20 months ago, # | ← Rev. 2 →   0 .
 » 20 months ago, # |   0 for C problem, my code failed in 4th testcase.I am not able to figure out the testcase,if anyone has any idea about what the testcase could be. Link to the code — https://codeforces.com/contest/1476/submission/105951904 My approach was to calculate number of vertices of every chain that will be added if i take that chain as an intermediate chain, ending chain, starting chain. i stored these values and calculated the maximum answer.
•  » » 20 months ago, # ^ |   +5 1716 2 12 2 7 18 8-1 7 1 2 1 2 2-1 10 2 12 2 3 12Correct Answer — 38Your Output — 37
 » 20 months ago, # |   +3 CodeForce is a great programming site!I love it.It brings me a lot of fun.The change of rating again and again makes me feel very exciting!
 » 20 months ago, # | ← Rev. 2 →   +3 Why so long for the editorial? Or is it normal? Sorry I am new, but my past contests had editorials almost in an hour
•  » » 20 months ago, # ^ |   0 educational rounds usually have slow editorials and idk why
 » 20 months ago, # | ← Rev. 2 →   0 I really do not understand, why my code for A problem had hacked .. why ceill function returns a wrong value While N & K are long Please can someone expert help me to understand what is the problem here ! this is my submission
•  » » 20 months ago, # ^ |   0 simply just don't use ceil, use (n+k-1)/k for ceil(1.0*n/k)
•  » » » 20 months ago, # ^ |   0 But why that happened !
•  » » » » 20 months ago, # ^ |   0 floating numbers are just too dangerous when you need absolutely correct results like codeforces, this ceil problem is very well known
•  » » » » » 20 months ago, # ^ |   0 Thank you .. i did not know that before This mistake cost me a lot this round ☹️
•  » » » » » » 20 months ago, # ^ |   0 I too used Ceil function, it got passed. In Java ceil returns double so have to typecast it into integer before printing the answer 105866315
•  » » 20 months ago, # ^ | ← Rev. 2 →   +1 For the test case 11 1000000000Your code gives 1e+009 as output, because you are doing "cout<