### vovuh's blog

By vovuh, history, 13 months ago, translation,

Hello! Codeforces Round #667 (Div. 3) will start at Sep/04/2020 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 Daria nooinenoojno Stepanova, Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round. Also thanks to Artem Rox Plotkin and Dmitrii _overrated_ Umnov for the discussion of ideas and testing the round!

Good luck!

UPD: Huge thanks to Ivan Gassa Kazmenko for testing the round and fixing some issues with statements and the round in general! Also thanks to nuipojaluista, kocko, Ilya-bar and infinitepro for testing the round!

UPD2: Editorial is published!

• +365

 » 13 months ago, # | ← Rev. 2 →   +13 are technocup rounds rated ?can someone tell rules of these rounds?
•  » » 13 months ago, # ^ | ← Rev. 2 →   +11 .
 » 13 months ago, # |   -13 I think it's going to be a very interesting contest
 » 13 months ago, # |   -14 Div. 3 Lover :)
 » 13 months ago, # |   +29 with "with ratings up to 1600" so me a 380 rating can participate right?, sorry this is my second contest still a noob, is div 3 problems easier than div 2 last time where I participated?
•  » » 13 months ago, # ^ |   +9 Yes div3 problems are easier than div2
•  » » » 13 months ago, # ^ |   +16 oh I see thank you for the answer :)
•  » » 13 months ago, # ^ |   -11 yes div3 is easier than div2 and don't worry about your low rating .Initially you start from 0 according to the new rules but over a span of 5 contests you are provided with 1500 extra rating (500 rating is added for the first round which you have already given xD).
•  » » » 13 months ago, # ^ |   -7 Sometimes,it is really difficult to understand why you got downvoted
•  » » » 13 months ago, # ^ |   +3 Well, I didn't downvote you, but I think that's because that guy didn't say he is worried.
•  » » » » 13 months ago, # ^ |   +2 yeah but he had written "still a noob" and it was pretty evident that he did not know about the new rules so.. But yeah, even then I think you have a point
•  » » 13 months ago, # ^ |   0 Yes, you can.
•  » » 13 months ago, # ^ |   -20 yes
 » 13 months ago, # | ← Rev. 2 →   +4 
•  » » 13 months ago, # ^ |   +20 Too old joke
•  » » » 13 months ago, # ^ |   +1 It might be, but div.3 rounds by vovuh will never get old
 » 13 months ago, # |   0 Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes. Can anyone explain how this penalty is calculated?
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 It is the time in minutes for each solved problem. Plus 10 minutes for each submission but the last of one of those submissions per problem.
•  » » » 13 months ago, # ^ |   0 So if one has a wrong submission for a particular problem and he is not able to make an AC until the round ends how will that penalty be calculated?
•  » » » » 13 months ago, # ^ |   0 penalty for each incorrect submission until the submission with a correct solution (ac) is 10 minutes...
•  » » » » 13 months ago, # ^ |   +7 if he does not make AC till round ends then no penalty ,else 10 minutes for every incorrect submission till AC.
•  » » » » » 13 months ago, # ^ |   0 Are you sure Sundaram_Sharma that if one makes many wrong submissions to a problem and is not able to get an AC for that problem will he be exempted from these penalties?
•  » » » » » » 13 months ago, # ^ |   +1 Yes
•  » » » » » » » 13 months ago, # ^ |   0 So penalties work for question wise and not total score wise?
•  » » » » » » » » 13 months ago, # ^ |   0 Primary tie break is # of questions solved. Secondary tie break is time penalty, calculated based on submission time plus any penalties for wrong submissions on only solved problems by adding 10 minutes per wrong submission
•  » » » » » » » » » 13 months ago, # ^ |   0 Is this true for Div 2 rounds as well?
•  » » » » » » » » » 13 months ago, # ^ |   0 This is only true for rounds specifically held with "educational rounds (extended ACM-ICPC)". This is how ACM-ICPC contests are held, and usually tend to be true mostly for educational rounds. Most Div 2 contests are held with point penalties subtracted from pre-defined scored distributions.
•  » » » » » » » » » 13 months ago, # ^ |   0 Primary tie break is # of questions solved. Secondary tie break is time penalty, calculated based on submission time plus any penalties for wrong submissions on only solved problems by adding 10 minutes per wrong submission Will this be valid there as well?
•  » » » » » » » » » 13 months ago, # ^ |   0 No. Score distribution can give harder problems higher point values such that a Div 2E might be worth 2500 points, while Problems A and B are only worth 500 and 1000 points. For example's sake say that Person A solves Problem A and B instantly, getting 1500 points. They would score less than a person who solved Problem E instantly, getting 2500 points. Notice that person A solved two problems, but would have placed worse in a regular Div 2 round. In a round held with ACM-ICPC rules, person A would have placed better than person B, having solved more problems, despite them being easier problems.
•  » » » » » » » » » 13 months ago, # ^ |   +2 Actually, I'm asking about penalty. If till the end of the contest there all WA to a problem will there be any penalty?
•  » » » » » » » » » 13 months ago, # ^ |   0 In both cases, only solved problem penalties are applied. If you had 10 wrong submissions on a problem, they are not applied if you do not solve it. If you solve it at the last second, the penalties are applied. However, note that there is no case where it is more beneficial to not solve a problem, even with lots of penalties on it. Solving a problem in an ACM-ICPC round with a hundred penalties would still move you ahead of everyone who had solved the number of problems you had solved minus 1. Likewise, in Div 2, you are comparing 0 points for not solving to a positive number of points, no matter how many penalties.
•  » » » » » » » » » 13 months ago, # ^ |   0 Got your point. THanks
 » 13 months ago, # |   0 What does it mean by -"I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over." Are the pretests too weak or are they strong enough so that there would hardly be changes in the accepted solutions before and after the contest in the main tests?
•  » » 13 months ago, # ^ | ← Rev. 2 →   +10 Pretets are quite strong so that less people get sad after main tests
•  » » » 13 months ago, # ^ |   +36 They aren't necessarily strong, they're just not intentionally weak.
•  » » » » 13 months ago, # ^ |   0 Curious the ratio of problem setters who intentionally make intentionally make pretests with hacking potential to those who try to make strong ones.
•  » » » » » 13 months ago, # ^ |   +20 Problem setters do not try to intentionally make weak pretests.
•  » » 13 months ago, # ^ |   0 It means he tried to make pretests strong enough so that there would hardly be changes after main tests.
 » 13 months ago, # |   -6 My rating is 1603, is this round rated for me? base on description I am a "trusted participant of the third division", but I don't understood It is rated for those who have rating lower than 1600 "and" the trusted participant of the third division or just for first group.
•  » » 13 months ago, # ^ |   +67 "trusted participant of the third division" != "the contest is rated for you"
•  » » » 13 months ago, # ^ |   +68 If you are trusted participant of the third division,your name will be on official standing.(Because there are so many fake accounts,u n r a t e d = L G M)
•  » » 13 months ago, # ^ |   +3 Being a trusted participant of the third division means your name will appear in the standings.This round will be rated for you if your rating is strictly less than 1600.Because your rating is higher than 1600, this will be not rated for you, but because you are a trusted participant if you join the contest your name will be displayed in the rankings.
 » 13 months ago, # |   -16 Hope no long queue :>
 » 13 months ago, # |   0 Hello! I have got a question: do pretests too light to catch wrong solution? Why another person has an opportunity to make tests, which will "kill" solution of the problem?
•  » » 13 months ago, # ^ |   +12 There can be a situation where the author did not think of the edge case before the contest so it was not included in the pretests.
•  » » » 13 months ago, # ^ |   0 So authour makes this "mistake" meaningly? To give us chanse to hake someones solution?
•  » » » » 13 months ago, # ^ |   +13 No, it is usually not intentional.
•  » » » » 13 months ago, # ^ |   0 No,it is because he missed some corner conditions
•  » » » 13 months ago, # ^ |   +3 Does this mean that system tests are made after the contest ends ?
 » 13 months ago, # |   +5 how to register for this? this will be my first one
•  » » 13 months ago, # ^ | ← Rev. 2 →   +6 Go to the Contest page . You will get your answer .
•  » » » 13 months ago, # ^ |   +5 Thanks!
 » 13 months ago, # |   -30
 » 13 months ago, # |   0 no side story ?
 » 13 months ago, # |   +6 rating has taken a major dip :(,hope to improve it in this round
 » 13 months ago, # |   0 During my school time :(No worries better luck with next div.3 contest
•  » » 13 months ago, # ^ |   0 If it is virtual, then you can participate.
•  » » » 13 months ago, # ^ |   0 I mean I could but...Maybe ill risk rating just to try problems
•  » » 13 months ago, # ^ |   0 usually every contest happens at the same time.
 » 13 months ago, # |   0 Really waiting for Div3..
 » 13 months ago, # |   -9 Since this is a Div. 3 round, and many of you are probably beginners. I suggest trying Kotlin for this contest. This article nicely explains how to setup your local environment: https://blog.kotlin-academy.com/setting-up-your-workflow-for-competitive-programming-in-kotlin-b1e84e6a6670I wasn't able to get started in competitive for a long time because C++ is scary and cumbersome. But I switched to Kotlin a while back and now I'm finally getting some momentum. Also since CodeForces has in the past supported Kotlin through the KotlinHeroes contests, I think it's worth checking out.Good luck!
 » 13 months ago, # | ← Rev. 3 →   0 Let's hope this time finally I am able to break the 1599 barrier after falling back from 1590+ rating many times SPOILER
•  » » 13 months ago, # ^ |   0 I think you are very close, it just a matter of time and you will hit expert very soon.
•  » » » 13 months ago, # ^ |   0 Thanks! you were correct indeed
•  » » » » 13 months ago, # ^ |   +3 Congratulations on your recent achievement :)
•  » » » » » 13 months ago, # ^ |   +1 Thanks, hope to see you getting blue soon enough!
 » 13 months ago, # |   -8 I don't afraid who has more than 1200 rating. I 'm afraid who solve over 1000 A.
 » 13 months ago, # |   0 Can someone please tell me why is there a trusted participant definition created when the contest is rated for non trusted participant too. Is there a difference beside the official standing table or anything i am missing?
•  » » 13 months ago, # ^ |   +13 Trusted participants will appear in the official standing but non-trusted participants will not. But it will still be rated for both of them.
•  » » » 13 months ago, # ^ |   0 is there any change in rating for non trusted participant compared to trusted ones for the same rank?
•  » » » » 13 months ago, # ^ |   0 No there isn't
 » 13 months ago, # |   0 Is anyone facing translation issues?
 » 13 months ago, # |   +3 what is the fastest set solve for div3? william lin did today in 23 minutes!! that's just amazing!!
 » 13 months ago, # | ← Rev. 2 →   0 .
•  » » 13 months ago, # ^ |   0 Nope, I think it was a little bit easy for Div 3.
 » 13 months ago, # |   +1 How to approach problem E ?
•  » » 13 months ago, # ^ | ← Rev. 5 →   +2 Spoiler 1Y co-ordinates are useless Spoiler 2Sort the X co-ordinates.From X[i] find till which index you can cover point with the first platform. let's call this index pos. You can do binary searchthen find the maximum points you can cover with the second platform after the pos index. but how to find this?Start from the last point. every time at ith index store what is the maximum points you can cover after the current indexCode Explains more than words
 » 13 months ago, # |   +3 Is Y coordinate of any use in E?
•  » » 13 months ago, # ^ |   +12 No use at all
•  » » 13 months ago, # ^ |   +4 I don't think so
•  » » » 13 months ago, # ^ | ← Rev. 2 →   0 Then it is solvable using segment or Fenwick trees I have an approach! PS: Solved using Binary search 91881046
•  » » » » 13 months ago, # ^ |   0 Can you kindly tell me why BIT and BITS are used for?
•  » » » » » 13 months ago, # ^ |   0 Actually Earlier my thoughts were to use Binary Indexed Tree but on further look I left that approach and tried something easier then binary search came to my mind. BIT is an array which is used to store the maximum point till which we can go from current point to next point if we were to place the board of exactly k length at this point lets say this maximum point till we reach is represented by BIT[i]. BITS[i] is just the suffix maximum array for array BIT[i].
•  » » » » » » 13 months ago, # ^ |   0 Thanks man
 » 13 months ago, # |   0 B solution please?
•  » » 13 months ago, # ^ |   0 There were two cases first try to decrease a to minimum possible then try for b. The minimum of both case is the answer
•  » » » 13 months ago, # ^ |   0 Any proof for this? That this will yield the minimum product?
•  » » » » 13 months ago, # ^ |   +3 To minimise the product we have to maximise the difference between two numbers. Hence the two cases
•  » » » » 13 months ago, # ^ |   +6 Hint — For a particular sum, maximum product happen when both numbers are as close as possible.
•  » » » » » 13 months ago, # ^ |   -6 kazuya and ctyx you two are mentioning completely opposite things
•  » » » » » » 13 months ago, # ^ |   0 If you have two numbers a,b and let's say n=2. Then to minimize the final product it is better to do ${a-2}$ or ${b-2}$ instead of ${a-1}$ and ${b-1}$.
•  » » » » » » 13 months ago, # ^ |   +3 They are saying the same thing, read carefully.Basic premise here is the fact that, given a fixed perimeter, the area of rectangle is maximised when the rectangle is a square. Since you want minimum area, try to keep the two edge lengths as far apart as possible.
•  » » » » » » » 13 months ago, # ^ | ← Rev. 2 →   0 I thought of doing a ternary search on the possible interval but realized that min can occur only in one of these three points including mid-point as the curve formed will be a regular parabola. Now realized that checking mid is not necessary as interval lies strictly either to the left or right of mid.
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 Always we need to try one element at least minimum value.then try to reduce other one at least minimum if n positive !! step 1 : try to reduce a value till x,,, until n operation finish..if n exist then try to reduce b till y,,, until n finish.. step 2 : try to reduce b value till y,,,, until n operation finish..if n exist then try to reduce b till y ,,, until n finish.. ans=min(step-1 a*b value,step-2 a*b value); // I copy a,b,x,y,n, value for step-2 My accepted (till now) solution
•  » » » 13 months ago, # ^ |   0 I thought of these two possibilities. But why can't be a third case, where we don't go to a minimum of either but meet in the middle of both ranges. How can we prove that there doesn't exist such a pair?
 » 13 months ago, # |   +1 Was E solvable with two pointers? I tried so but getting WA on test 2. codeint n, m, k; int a[N], b[N]; void solve(int test_case){ int i, j; cin >> n >> k; for(i=0;i> a[i]; }for(i=0;i> j; sort(a, a+n); int r = n-1; for(i=n-1;i>=0;i--){ int R = a[i]+k; while(r>0&&a[r-1] > R)r--; b[i] = r-i+1; } b[n] = 0; r = 0; int ans = 0; for(i=0;i
•  » » 13 months ago, # ^ |   0 I tried two pointer but it does not account for test cases like this: 1 5 10 1 3 8 13 20 where two pointer finds the 3 8 13 on the first rod, when 1 3 8 and 13 20 are optimal. I tried to come up with additional cases, but ran out of time. Trying to look at your code, I am not sure you even used two pointers? Seems as though you calculate the second pointer each for all i, which would likely fail in terms of time complexity.
•  » » 13 months ago, # ^ |   0 For each b[i] you need to replace it with the maximum b[i] among all b[i] from i to n-1 as it is not necessary that both segments have no points between them.
•  » » » 13 months ago, # ^ | ← Rev. 2 →   0 Yeah I missed that too but it's still wrong answer https://codeforces.com/contest/1409/submission/91877808Checker says somewhere I printed 8 instead of 7. I think it was some silly mistake.
 » 13 months ago, # |   +12 Great contest. Thanks vovuh
 » 13 months ago, # |   0 Help me with E and F
•  » » 13 months ago, # ^ | ← Rev. 2 →   +3 Though F is easier to think, E is easier to explain. So I will try to explain E first SpoilerAre y coordinates of any use ? — NoWhat can be the best way to store x coordinate to proceed ? Spoilervector > where pair is x coordinate and corresponding frequency.Let's sort the vector of pairs as per x coordinate. One more precalculation that will be useful is, prefix array on frequencies, basically on .second of pairs in vector.Now let's make a dp table size of vector * 2 Either we take the current index or we don't. So if we are at i, and we take the current index, we need to find the other index, so that .first at current + k <= .first at end index for current platform. How ? SpoilerBinary searchSo once we have the end index, dp(i,j) = max(dp(i+1,j), prefix (end) — prefix (i-1) + dp(end+1, j-1)Implementation of above idea is 91831346.
•  » » 13 months ago, # ^ |   +3 Idea for F : let's us assume that we have a 3-D dp table 200*200*200 where at i,j,k we store the number of subsequences of t, in first i characters of s, using j exchanges and having occurence of first charcter of t, k times.To proceed to next state we 3 options, Set the current character as first letter of t, as second letter of t, or let it be same. We need to handle few cases carefully SpoilerWhat if the current charcter is already either first letter of t or second letter of t.A little effort and the following code will make sense. 91846302
 » 13 months ago, # |   0 Idea behind F?
•  » » 13 months ago, # ^ |   0 How did you solve E?
•  » » » 13 months ago, # ^ | ← Rev. 2 →   0 Well it's obvious that our two segment mustn't overlap. Now lets sort our dots by their x coordinates and calc ans[i] for i dot. ans[i] — a number of dots, that belong to the segment that starts at position x[i]. We can calc it using binary serch in O(nlogn). Lets second segment have larger cords that first one. Lets calc max_suff[i] — max dots that can belong to segment, that have the same or larger coordinate than x[i]. We can do it in O(n) just max_suff[i] = max(ans[i], max_suff[i + 1]) Lets calc now_max — the position of first dot, that have larger coordinate than the end of our current first segment. tmp_ans_i — answer if first segment start at i position Now look over first segment start coordinate and calc dots belong to it with binary search then add their number to the tmp_ans_i. Now update now_max: if (x[now_max] < (end of first segment)) now_max += 1 then update tmp_ans_i: tmp_ans_i += max_suff[now_max] Now choose the greatest tmp_ans_i — it is the answer. Code: 91848373
 » 13 months ago, # | ← Rev. 2 →   +3 Very nice problems. Solved all but F (WA39). Any ideas about F? Maybe some dp? Greedy didn't work
•  » » 13 months ago, # ^ |   -8 no, it's not a dp problem
•  » » 13 months ago, # ^ |   +4 I solved it using dp, dp[i][f][r] is the number of sub sequences in s[0..i-1] if the frequency of t[0] is f and there are r replacements you can do
 » 13 months ago, # |   0 How to pick the two segments in E after coordinate compression? Will greedy work?
•  » » 13 months ago, # ^ | ← Rev. 3 →   0 You can ignore the y coordinates. First sort the points according to the x coordinate, we'll call this array pts (for points). Then create two arrays suffix[n] and prefix[n]. They will store the maximum number of points you can save if you use one platform for points with x <= pts[i] for prefix and x >= pts[i] for suffix. These can be calculated in O(nlogn) time using binary search. Your answer would be max(prefix[i] + suffix[i+1] , where i=0...n-1) , also suffix[n] = 0See my submission : 91851604
 » 13 months ago, # |   0 I think there is a tricky edge case in problem D
•  » » 13 months ago, # ^ |   0 Did you check if sum of digits of n is already less than or equal to s. I solved this one but still unable to figure out the corner case in test 3
•  » » » 13 months ago, # ^ |   0 just set the maximum possible value for the elements every high.
•  » » » 13 months ago, # ^ |   0 91874268 yea i did. anybody approached string n starting from lsb?
•  » » 13 months ago, # ^ |   0 wrong answer 16th numbers differ - expected: '32932471720801151', found: '32932471720801152'I got this on my first submission attempt, it was just off by 1. Might have something to do with overflow but I'm no expert. I ended up using a string instead of a long and it worked out fine.
 » 13 months ago, # |   0 can anyone help to solve 2nd question?
•  » » 13 months ago, # ^ |   +6 You can just check both possibilities first try decreasing a then b (till their limits and n obviously) then other poss would be decrease b and then a. Find min of both you got ur answer...
•  » » » 13 months ago, # ^ |   0 Couldn't it be done using DP?
•  » » » » 13 months ago, # ^ |   0 It can be. But the constraints won't allow you I guess (1≤a,b,x,y,n≤109) unless you have a very good dp state function(which I can't think of any)
•  » » » 13 months ago, # ^ | ← Rev. 2 →   0 Thank you
 » 13 months ago, # |   0 Can someone explain what is wrong with this submissions for D? 91874847 I thought the contest was great!
 » 13 months ago, # |   -15 Video Editorial for D. Decrease the Sum of Digits
 » 13 months ago, # |   0 Can someone pls tell what was wrong with my D? https://codeforces.com/contest/1409/submission/91874703
 » 13 months ago, # |   +42 Problem E: you(y coordinate) vs the guy(x coordinate) she tells you not to worry about.
•  » » 13 months ago, # ^ |   0 How did you solve E?
•  » » » 13 months ago, # ^ | ← Rev. 2 →   0 sort points wrt to x co-ordinate. Then do a brute force. i.e. assume 1st platform start from $i^{th}$ points then find what is the maximum no of points you can get among the points after it's right edge($x_i+k$) with second platform. Add both platform contribution(for 1st just do Binary Search) for this you can first precompute this result for every $i$ and then do the prefix max. my submission $Note$- we don't have to do twice calculation as i have did during the contest. One pass is enough i think.
•  » » » 13 months ago, # ^ | ← Rev. 2 →   0 using queue to find how many points are there from i to i-k and i to i+k for each x coordinatethen find how many max points you can cover from left and same for rightanswer will max of sum from both sides for every point
 » 13 months ago, # |   +2 E was nice!
»
13 months ago, # |
Rev. 5   +1
###### Useless cheating, but still
His code.

91803529

His alt code

91859832
Same situation at B and C

•  » » 13 months ago, # ^ |   0 How do you catch that?
•  » » 13 months ago, # ^ |   0 Is Hacking a solution Offense.. Does it gives you points?
 » 13 months ago, # | ← Rev. 3 →   0 Problem A:91867460 can anyone review my solution and tell my how it's not a good solution and what was the solution if it's not correct since it shows time limit exceeded on test case 2
•  » » 13 months ago, # ^ |   0 You are incrementing the value one by one. Due to the larger limits this would take a lot of time as it is looping through each of the values.It is better to use division and modulo to quickly get how many times this number would be divided by a certain number (here it is 10) and then check if any additional number is required to make it equal to the other number.This is a common thing that I also did when I started doing CP. A new thing to learn I guess. ;)
•  » » » 13 months ago, # ^ |   0 Yeah, I took the ceiling of the absolute value of the difference of a and b over 10. ceil(abs(a-b)/10.) It's constant time and fast. In this case just take the 10 away each time until they differ by less than 10. Then add one more if it's not zero
 » 13 months ago, # |   +9 Imagine coding the shit out of myself with digit dp just to realize that people get AC'd with simple greedy
•  » » 13 months ago, # ^ |   0 My greedy got WA39. Can you link some accepted greedy?
 » 13 months ago, # |   0 Video Tutorial C:https://www.youtube.com/watch?v=FMu64hfwo3A
 » 13 months ago, # |   0 Video Tutorial B:https://www.youtube.com/watch?v=QJ0bHUT7qOc
 » 13 months ago, # |   +18 Is there a greedy approach that works for F? I spent a bunch of time on a few ideas but couldn't get them to work.
•  » » 13 months ago, # ^ |   +10 I can share the solution of Gassa but I didn't get deep into details. It's also $O(n^4)$ but he said it can be optimized. Code// Author: Ivan Kazmenko (gassa@mail.ru) module solution; import std.algorithm; import std.conv; import std.range; import std.stdio; import std.string; void main () { int n, k; while (readf !(" %s %s") (n, k) > 0) { readln; auto s0 = readln.strip; auto t = readln.strip; auto s = s0.dup; int res = 0; foreach (b0; 0..k + 1) { auto e0 = k - b0; loop_x0: foreach (x0; 0..b0 + 1) { loop_y0: foreach (y0; 0..e0 + 1) { int b = b0; int e = e0; int x = x0; int y = y0; s[] = s0[]; for (int i = 0; i < n && b; i++) { if (s[i] == t[0]) { } else if (s[i] != t[1]) { s[i] = t[0]; b -= 1; } else if (x > 0) { s[i] = t[0]; x -= 1; b -= 1; } } for (int j = n - 1; j >= 0 && e; j--) { if (s[j] == t[1]) { } else if (s[j] != t[0]) { s[j] = t[1]; e -= 1; } else if (y > 0) { s[j] = t[1]; y -= 1; e -= 1; } } int cur = 0; int add = 0; for (int i = 0; i < n; i++) { if (s[i] == t[1]) { cur += add; } if (s[i] == t[0]) { add += 1; } } res = max (res, cur); if (x > 0) { break loop_x0; } if (y > 0) { break loop_y0; } } } } writeln (res); } } 
•  » » » 13 months ago, # ^ |   +1 Yep I also had an $O(n^4)$ greedy, but it gets TLE. It should be optimizable to $O(n^3 \log n)$ with a Fenwick tree, but at that point it gets much more complicated than the DP solution (and is still slower).
 » 13 months ago, # |   0 Will an unsuccessful hacking attempt increase my time penalty in this round? I tried 2 hacks both were unsuccessful.
•  » » 13 months ago, # ^ |   0 NO in div-3
 » 13 months ago, # |   +12 I like the contests by vovuh because the statements are clear and precise :)
 » 13 months ago, # |   +2 Anyone else solved E by binary search?
•  » » 13 months ago, # ^ |   0 Yes! So for finding out how many points you can catch from a point with x-coordinate value A with K length, you can binary search the point with x-coordinate with value A+K. This can provide you with points you can catch while standing at ith position in nlog(n) time. Assuming that you sort the array of x-coordinates
 » 13 months ago, # |   -13 My B is getting tle , pls help #include #include #include using namespace std; void solve () { int a,b,x,y,n; cin >> a >> b >> x >> y >> n; unsigned long long ans=ULLONG_MAX; int p=min(n, a-x); int q=min(n-p,b-y); while (p>=0 && q<=b-y) { unsigned long long cur=(unsigned long long)(a-p)*(b-q); ans=min(cur,ans); --p,++q; } cout << ans << '\n'; } int main () { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t;cin >> t; while (t--) solve(); return 0; } 
•  » » 13 months ago, # ^ |   0 The problem with this solution is that you are iterating over all of the possible values one by one. This will cause a TLE as the iterations could be very large. It is better to subtract the maximum possible number first from A and then B, and then do it the other way, that is subtract from B first and then from A.The minimum value would be one of these two values obtained. It is not possible to obtain a smaller number by any other variation.
 » 13 months ago, # |   0 I only solved problem A :( I realized that I'm lacking in comprehension, I spend so much time reading and trying to understand the problems, only to realized it within the last 10 mins (problem D) I'm so dumb... but I enjoyed it still.
 » 13 months ago, # |   0 are these cheaters phamquan-cbg and papaya.ahaha?: 91808904 91812659I found these two VERY similar submission (when I was looking for people from my country to hack): + same strange input and output file name + exactly same loopIf you cheaters read this, please stop this immediately !!!
•  » » 13 months ago, # ^ |   0 How do you look for people who are from your country? Are they in your friend list?
•  » » » 13 months ago, # ^ |   +1 By using this extension you can see your country based standing..I collected it from a post..Crome extension Firefox extension *I am using crome extension..thats cool.
•  » » » 13 months ago, # ^ |   0 actually, i was just search for people in my country that are similar in rank with me manually :v
•  » » 13 months ago, # ^ | ← Rev. 3 →   0 lmao
 » 13 months ago, # |   0 My screencast + live commentary, enjoy watching :)https://youtu.be/nloGFTpdTJo
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 can you Explain cnt + (i == t[0])) + cnt * (i == t[1]) part in your F solution?Edit: I understood
 » 13 months ago, # |   0 I made the most embarrassing mistake. I used a separate function to calculate the solution of Problem B and everything was correct EXCEPT I returned an integer from the function instead of a long integer. I cannot facepalm myself enough.I feel stupid, could have probably solved C too with the time I wasted there. Need to practice more :(
•  » » 13 months ago, # ^ |   0 Did something similar :(
 » 13 months ago, # |   0 Can someone please tell me what's wrong with My Code Problem D
 » 13 months ago, # |   0 Can someone please help in D?
 » 13 months ago, # |   +5 Can anyone tell the idea how to solve E efficiently if we have $k$ platforms?
•  » » 13 months ago, # ^ | ← Rev. 8 →   +4 it can be solved by dynamic programming dp[i][j] that mean is what is the maximum number of points you can get from the first i points using j platforms .. the transition is 1-either use a new platform and go to the i->nxt[i] {that is the index of the point that x[nxt[i]] > x[i]+k }, you should precalc this array to keep your solution complexity is O(n*P) where P is the number of platforms and j->j+1 2-or ignore this point and go to i->i+1 , j->j 
•  » » » 13 months ago, # ^ |   +5 Thanks
•  » » » » 13 months ago, # ^ |   +4 ur welcome but don't forget to add nxt[i]-i to the first transition because all the points between them will be taken by this new platform . sorry i forgot it
 » 13 months ago, # |   -7 Guys, could anybody help me understand whats wrong with my code for problem D? It gives the correct answer for all test cases in my machine, but it does not work at the Codeforces' server.I'm sure the logic is correct, but don't know what happened. And unfortunately it was a valid submission in contest time.https://codeforces.com/contest/1409/submission/91865709
 » 13 months ago, # |   +1 https://codeforces.com/profile/enigma_13 Looking at this user, all his submissions have been hacked, because each of his codes has statements like if(t==xx). Although I think this way of raising ratings is very witty, should it really be encouraged?
•  » » 13 months ago, # ^ |   0 How will it raise his/her rating?
•  » » » 13 months ago, # ^ |   0 I am not sure that this method can improve the rating in div3 and edu round. I am also a novice. But in ordinary div1 and div2 (especially div 2), you can use a small id and submit such a program. If the algorithm is correct, it can easily pass the pretest, and then you can hack it with your large id. After being hacked, you can change the value of the condition in the if and resubmit. Then you can use your large id to hack it again. This process can be repeated almost countless times. So you can get rating easily?
 » 13 months ago, # |   0 When will I get my rating?
 » 13 months ago, # |   +1 Nice contest, thanks. Got stuck on C until late in the game when I discovered the constraints were easy, then ran out of time. See you next contest.
 » 13 months ago, # |   +8 this type of hack should be banned right ? 91859832 91860660 91861276 91817628 91879637 91879985 91880404 91880766
 » 13 months ago, # |   0 im new here, somebody knows why i haven't got rated, I got accepted in problem A but didn't get any rating yet, thanks, sorry if I miss anything
•  » » 13 months ago, # ^ |   0 It will take time. Maybe after 4 or 5 hours
 » 13 months ago, # |   +3 Such a nice round it was! It deserve more upvotes...
 » 13 months ago, # | ← Rev. 2 →   0 nice contest
 » 13 months ago, # |   +3 How can we solve E using DP?
 » 13 months ago, # |   0 My ratings are not getting updated. can you tell me why? My rating is 1444.
•  » » 13 months ago, # ^ |   0 Its already been 24 hrs
•  » » » 13 months ago, # ^ |   0 14 hours not 24
•  » » » » 13 months ago, # ^ |   0 sorry 14. Did yours get updated ?
•  » » » » » 13 months ago, # ^ |   0 no.. this time it is taking so much time
 » 13 months ago, # |   +7 System testing is in quarantine.
•  » » 13 months ago, # ^ |   0 lol
 » 13 months ago, # |   0 Can anyone please help me to understand why this n^3 solution for problem C got TLE? https://codeforces.com/contest/1409/submission/91917207
 » 13 months ago, # |   0 Why the ratings has not been updated yet..?
•  » » 13 months ago, # ^ |   0 I think it s because of the new update of this great condition of being a "trusted participant".. While waiting for the rating too, I ve seen some friends of mine getting higher places in the final standings.. the reason is maybe non trusted participants got banned from the official participation.
•  » » » 13 months ago, # ^ |   0 who is a "Trusted Participant"?
•  » » » » 13 months ago, # ^ |   0 In a youtube screencast, I noticed that the streamer has a button where he can vote whether a particular participant is "trusted" or not... So maybe it is up to high ranking mates to decide ! Otherways, here you'll find official details about this new update.
•  » » » » 13 months ago, # ^ |   0 Who take part in at least two rated rounds (and solve at least one problem in each of them),
•  » » » 13 months ago, # ^ |   0 Dude im a trusted one and it still hasnt updated
 » 13 months ago, # |   0 Why is rating change taking time?
•  » » 13 months ago, # ^ |   0 The round will be hosted by rules of educational rounds (extended ACM-ICPC) Educational rounds usually takes roughly 20 hours. (12 hrs of hack period +a)
•  » » » 13 months ago, # ^ |   0 12 hours of hack peroid + ?
•  » » » » 13 months ago, # ^ | ← Rev. 2 →   0 They re-judge our solutions using custom-invoked test cases by participants. (correction: plus the custom-invoked ones)
»
13 months ago, # |
-9

why is this solution giving time limit exceeded?...i just ran it now...it got accepted

# include <bits/stdc++.h>

using namespace std;

# define endl "\n"

int main() { ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);

int t; cin>>t; while(t--) { long long int n,x,y,i,j,num1=0,num2=0,mn=INT_MAX; vector v; cin>>n>>x>>y;

if(n==2)
cout<<x<<" "<<y<<endl;

else
{
for(i=1;i<=x;++i)
{
for(j=1;j<=10000;++j)
{
if(i+(n-1)*j>=y)
{
if((x-i)%j==0 && (y-i)%j==0)
{
if(mn>(i+(n-1)*j))
{
mn=(i+(n-1)*j);
num1=i;
num2=j;
}

if(mn==y)
break;
}
}

}
if(mn==y)
break;
}

cout<<num1<<" ";
n--;
while(n--)
{
num1+=num2;
cout<<num1<<" ";
}

cout<<endl;
}

}

return 0;`

}

•  » » 13 months ago, # ^ |   +3 Obviously TLE......
 » 13 months ago, # |   0 waiting for rating change.. solved 5 of 6 problems
 » 13 months ago, # |   0 This was my first attempt at competitive coding can someone tell me when can I expect my ratings update as it is still not updated
 » 13 months ago, # |   0 is it rated?
•  » » 13 months ago, # ^ |   0 Is IT Rated?
»
13 months ago, # |
0

this code is giving wrong ans.can someone please help me to find the bug.? this code is for question 3rd.

# include<bits/stdc++.h>

using namespace std;

# define ll long long int

int main() { int t ; cin >> t; while(t--) { ll n,x,y,i,j,dif=0,ans=0,i1=n,j1=n,k; cin>>n>>x>>y; vector<ll,ll>v1; // ll long long int ans=y-x; dif=ans; if(n==2){ cout<<x<<" "<<y; } else{ for(i=n-1;i>1;i--){ if(ans%i==0){ dif=ans/i; break; } } // cout<<dif<<" "; v1.pb(x); for(i=1;i<n;i++){ if(x+i*dif<=y){ v1.pb(x+i*dif); } else{ i1=i-1; break; } } // cout<<i1<<" "; for(j=1;j<n-i1;j++){ if(x-j*dif>0){ v1.pb(x-j*dif); } else{ j1=j-1; break; } } // cout<<j1<<" "; for(k=1;k<n-i1-j1;k++){ v1.pb(x+(i-1+k)*dif); } ll r=v1.size(); for(i=0;i<r;i++) cout<<v1[i]<<" "; } cout<<endl; }
return 0; }

•  » » 13 months ago, # ^ |   +3 Your text to link here..._ this is the link to code.
 » 13 months ago, # | ← Rev. 4 →   +3 My Java solution for E is just like everyone else's and the provided tutorial O(N Log N) and yet it keeps getting a TLE on test 5. Can someone have a quick look?https://codeforces.com/contest/1409/submission/91970662I've used FastIO, tried Java 8 and 11, nothing worked so far.EDIT: I added some conditions to narrow down the problem, turns out Arrays.sort(A) is taking too long, which is very weird. Not sure if I'm doing something obviously wrong. SolutionEDIT 2: Turns out, randomly shuffling the array before sorting it worked!! Why would the unshuffled array take WAY longer?!
 » 13 months ago, # |   0 Please help me I am getting wring ans in D solution:https://codeforces.com/contest/1409/submission/91972053Instead of making 9 from the digit where we get sum greater than or equal to sum i am increasing the previos value by one and making all zero from that digit .
 » 12 months ago, # |   0 93053565 To solve problem F, I use an dp algorithm which has O(n^4) time complexity. It spend 1996ms, when this problem limits 2000ms. Lucky.