### vovuh's blog

By vovuh, history, 2 years ago, translation,

<almost-copy-pasted-part>

Hello! Codeforces Round #636 (Div. 3) will start at Apr/21/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!

</almost-copy-pasted-part>

UPD: Also thanks to Sakhiya07, infinitepro and ma_da_fa_ka for testing the round!

UPD2: Editorial is published!

• +297

 » 2 years ago, # | ← Rev. 3 →   +11 GL to all :D vovuh orz
•  » » 2 years ago, # ^ |   0 Good luck mate
•  » » 2 years ago, # ^ |   0 So many contest during quarantine thank you vovuh.
 » 2 years ago, # |   +3 GLHF to all, xD
 » 2 years ago, # |   -23 is vovuh the only user who can make div3 contest ? i mean why every div3 contest in the past 5 or so are made by him?
•  » » 2 years ago, # ^ |   +21 He is coordinator for div3 rounds .While Pikmike is coordinator for educational rounds series!
•  » » » 2 years ago, # ^ |   0 oh... ok i see thanks
•  » » » 2 years ago, # ^ |   0 what is the difference in educational rounds vs DIV rounds?
•  » » » » 2 years ago, # ^ |   +9 THe differnce is that Educational rounds are rated for div2 (rating below 2100) and Div3 ones are rated for rating below 1600 thus their is differnce in problems and their difficulty. Educational Round is an Harbour Space University Initiative and they pick problems that are really meant for teaching new things to newbies like us and Div3 rounds are practice rounds for us for honing our skills of accuracy and implementing problems in a better way.Both of the rounds are similar in terms of hacking if we see as both allows hackers to hack others solution after the contests and also all problems have equal weight in both the type of rounds.
•  » » » » » 2 years ago, # ^ |   0 thank you Mr. AM_I_Learning
•  » » » » » 2 years ago, # ^ |   0 Are you kidding me. It was supposed to like that. Div3 and educational div2 are fine. No doubt. But, if you think about teaching of new things, then normal div2 rounds also do this and some setters do this better like errichto.
•  » » » » » » 2 years ago, # ^ |   0 By the way the original question doesn't talk of normal rounds. Thus I didn't talk of it!
•  » » 2 years ago, # ^ | ← Rev. 2 →   +1 No, Codeforces Round #605 (Div. 3) was made by MikeMirzayanov, Rox, and vovuh, Codeforces Round #587 (Div. 3) was made by BledDest, fcspartakm, and vovuh, and Codeforces Round #570 (Div. 3) was made by BledDest, MikeMirzayanov, and vovuh.
 » 2 years ago, # | ← Rev. 2 →   +80 1
 » 2 years ago, # |   0 Happy Easter to everyone who celebrates!
 » 2 years ago, # |   +1 Spoiler
 » 2 years ago, # |   0 Good luck to all participants. Hoping for a great contest. Have Fun!
 » 2 years ago, # |   +51 ..
•  » » 2 years ago, # ^ |   0 lol
 » 2 years ago, # |   +126 When anyone else tries to make Div3 contests: Vovuh:
•  » » 2 years ago, # ^ |   0 lol
 » 2 years ago, # |   0 I had a doubt: does 12 hour hacking phase mean that solutions can be hacked during this phase after the contest? Till now I used to think that we have to lock our problems and look at solutions in our room and hack them during the contest.So which one is correct? Thanks in advance
•  » » 2 years ago, # ^ |   0 It means you will have an access to all solutions in a text form. You won't be limited to your room only.
•  » » » 2 years ago, # ^ |   0 Thanks for the clarification
 » 2 years ago, # | ← Rev. 2 →   -20 I think 12 hours of open hacking phase is too much. It could be reduced to 4-5 hours while adding successful hacks to system testing. If it is for 12hrs for some reason, It is just a humble request to please help me know the reason.
•  » » 2 years ago, # ^ |   +24 Contest timings are usually not favourable for everyone around the world. Yet, those who manage to participate might be participating at like midnight or something. Most people would prefer to sleep after the late night contest. To provide a good window and opportunity for hacking to such people, hacking phase seems to be 12 hours.
•  » » » 2 years ago, # ^ |   -7 I think only few contestants take participate in hacking.
•  » » 2 years ago, # ^ |   0 What about people in other countries? For example, in China, the contests usually starts around 10 p.m. so we can only hack the next day.
 » 2 years ago, # |   0 I have started making video solutions on mostly D based problems of every codeforces round. The videos can be found here.
 » 2 years ago, # |   -16 will try to overcome CodeJam Round1B failure. LOL
 » 2 years ago, # |   +4 We want more contest in this quarantine :(
 » 2 years ago, # | ← Rev. 3 →   +34
 » 2 years ago, # |   +17 ..
 » 2 years ago, # |   +2 How can I make problems in a Div.3 round? I see that le.mur(he/she hadn't participated in any contests) was one of the authors of Codeforces Round #552 (Div. 3). My rating is 1591 now so can I make problems in Div.3 rounds?
 » 2 years ago, # |   0 Why are there "6 or 7 (or 8)" problems? Am I allowed to know how many problems there are?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +5 It is an almost-copy-pasted-part, so you cannot know the number of problems now.
•  » » » 2 years ago, # ^ |   0 Thanks!
 » 2 years ago, # |   0 Good Luck!! Happy Programming *_*
 » 2 years ago, # |   0 Good Luck to everyone!!
 » 2 years ago, # |   +3 looking forward to increasing my rating ..as always.. :)
 » 2 years ago, # |   +7 ![ ]()
 » 2 years ago, # |   +4 I think the problems will be more like implementation type! So, Be ready with your implementation skill @ 20.05!!
•  » » 2 years ago, # ^ |   +3 get ready to be hacked!!
 » 2 years ago, # |   +4 I wish the penalty was less(like the contests in Atcoder).
 » 2 years ago, # |   0 I hope it will be as fun as the last round
 » 2 years ago, # |   -24
 » 2 years ago, # | ← Rev. 2 →   +2 Good luck to you all and have lots of fun, coders!As you got used to it, we will upsolve the most interesting problems of the round live at 8PM:https://youtu.be/ppk9pXL9rR4
 » 2 years ago, # |   +9
 » 2 years ago, # |   +1 Thanks vovuh!We hope more Div.3 contests for our beginner )
 » 2 years ago, # | ← Rev. 8 →   -36 I know u guys are already at it... but we need more contests in lesser time interval...upvote this comment if that's what u want too...so much hatred in this community :(why downvote???
•  » » 2 years ago, # ^ | ← Rev. 2 →   +29 Nope. We want good quality contests.I don't mind if it takes more time because we always have the option of doing virtual contests.
•  » » 2 years ago, # ^ | ← Rev. 5 →   +25 Always remember, we want good quality contests. A single bad contest can make people complain for a long timeGood contests usually require more preparation.If you want to have more contests, you can do virtual ones(Since there are more than 600 rounds in the past, you will have a lot of work to do)See this contest for an example:AIM Tech Poorly Prepared Contest (unrated, funny, Div. 1 preferred)Although is a funny unrated round, do you want to have rated contest like this?View the past contest list, choose a contest and click "virtual participation" button to do virtual contests.By the way, if you want more upvotes, you can submit useful comments(for example, answer questions), but not asking for upvotes. People usually won't do things they are forcely asked to do if they don't want.
 » 2 years ago, # |   0 It would be great if you add contests more frequently like alternate days or one in 3 days. Happy Coding :)
 » 2 years ago, # |   0 This is vovuh's 37th Div-3 contest.
•  » » 2 years ago, # ^ |   0 In my opinion it is 36th contest. It is named "Div3 round 36" in polygon.
•  » » » 2 years ago, # ^ |   +51 You are right. Mike held one Div.3 contest without me (I don't remember its number)
 » 2 years ago, # |   0 Best wishes to everyone for the contest
 » 2 years ago, # |   +6 this contest has become now as contest with most number of participants ...wow
 » 2 years ago, # |   0 good luck all
 » 2 years ago, # |   +3 26K+ participants. Simply WoW.
 » 2 years ago, # |   +15 27k+ Registrants for this contest!!!
 » 2 years ago, # |   -10 I hope this contest would be good unlike the previous one.
•  » » 2 years ago, # ^ |   +17 Wasn't the previous one(Codeforces Round #635 (Div. 1) and Codeforces Round #635 (Div. 2)) good?
•  » » » 2 years ago, # ^ |   0 I meant previous div3, not the last contest. The last contest was fun.
 » 2 years ago, # |   -20 The comment removed because of Codeforces rules violation
•  » » 2 years ago, # ^ | ← Rev. 2 →   +7 What was your Comment ??
•  » » » 2 years ago, # ^ | ← Rev. 2 →   -8 I had told that I think the first condition in problem D is not necessary because with the given definition of "replacement" it's impossible that we violate the first condition.I'd told this in a nice way and I thought it doesn't spoil anything about the problem so it doesn't violate the rules. But maybe it did. :DHowever... It wasn't such an important thing. The fun part is about downvoters who have never seen what I'd said. :))
 » 2 years ago, # | ← Rev. 2 →   +52 D, E, F though 
 » 2 years ago, # | ← Rev. 2 →   +3 The comment removed because of Codeforces rules violation
•  » » 2 years ago, # ^ |   +5 Problem F
•  » » » 2 years ago, # ^ |   +5 there is no Special Judge? why? Can anyone reply my questions? thanks very much.
•  » » » » 2 years ago, # ^ |   +23 Read the problem why don't you use this ?
 » 2 years ago, # |   +3 Such a difficult D.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +7 I am suprised so few people solved it, thought there would be 2-3 times more lucky solvers. I am 1300 elo and I did it! And I was even disappointed it took me so long. Seems my training worked out :D
•  » » » 2 years ago, # ^ |   0 what's your idea?
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +16 I go over each (a_i, a_n-i) pair and find for which sum x I would have to make 0, 1 or 2 replacements. They form ranges so I mark their starts and ends in an array, that lets me solve in linear time.
•  » » » » » 2 years ago, # ^ |   0 i agree with you. my solution was same
•  » » » » » » 2 years ago, # ^ |   0 Congrats!
•  » » » » » » 2 years ago, # ^ |   0 I have used the same solution as yours. Look like there's a silly mistake.
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Did (tried actually) same thing but got WA (Test 2) :D
•  » » » » » » 2 years ago, # ^ |   0 This happended with me too
•  » » » » » 2 years ago, # ^ | ← Rev. 3 →   0 can u plz show via dry run it will be much helpful
•  » » » 2 years ago, # ^ |   -9 "I'm 1300 elo and I did it"- very poor reference. Remember Gennady was once a 1500 too.
•  » » » » 2 years ago, # ^ |   0 Maybe we all can become Gennady ;)
•  » » » 2 years ago, # ^ |   +5 Training always works out. Sometimes you just need a bit more of it with some consistency.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Yes, I think the key to improvement is consistency and challenging yourself. I have a habit of solving one 1600-1800 problem everyday and it helps much.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 IMO it wasn't that bad.My solution I think is the most natural one arising from simply understanding the contribution of every index depending on the value of forced sum.You do some case analysis for $u, v > k$, $u, v \leq k$ and $\mathrm{max}(u, v) > k, \mathrm{min}(u, v) \leq k$ and just make an interval tree, in which $s$-th position corresponds to penalty for choosing the forced sum to be $s$. Then a minimum query on the whole $[0, 2k]$ gets you the answer.You need lazy propagation to build such a segment tree, though, but if you know that, it's pretty straightforward. The only pitfall here is debugging for an hour, like I did.
•  » » » 2 years ago, # ^ |   +1 Since you only have one query, isn't it much easier to only do offline prefix sums instead of the segment tree?
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 It's not obvious to me how to do that actually. The core of my solution 77566384 is processing elements of the prefix one-by-one and adding on the interval and I don't know how to do that without segment trees or treaps.I think this can be unwrapped into some scanline approach to get rid of LP but again no idea how to do it in other ways. Could you elaborate?
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Yeah. You're somewhere close to the idea with a scanline. Though, I am a bit surprised as to how you know about segment trees but are unaware of the prefix sum approach to query.Let's say you have an array A of size N with elements a[i], i = 1 to N.You're given Q queries in each of which you need to count number of values less than(or equal) a given value Y and strictly greater than a given value X.So, build an array(or map), say freq. freq[X] denotes how many times X appears in array A.Now, create a new array(or map) pref where pref[i] is sum of freq[0] to freq[i].So, for each query (X,Y] your answer is pref[Y] — pref[X].Note: Time complexity becomes O(N + Q). This isn't recommended when there are update queries for array A too since that leads time complexity to O(N*Q) as you will have to rebuiled the pref array(or map). Note that space issues might also arise for large values if you use array.In the concerned question, the values don't go beyond 2*K at any point of time, and hence there won't be space issues.
•  » » » » » » 2 years ago, # ^ |   0 https://codeforces.com/blog/entry/15729You can read the partial sum section from this blog for more understanding!
•  » » » » » 2 years ago, # ^ |   +7 The scanline approach will efficiently find, for each point, the sum of values of all segments that overlap it. Consider any segment $[l, r]$ of value $v$. In the scanline, for this segment, you want all indices $< l$ to be worth $0$, all indices $l \leq i \leq r$ to be worth $v$, and all indices $> r$ to be worth $0$. The scanline will keep a running prefix sum of the values at each array element. To increase this prefix sum by $v$, simply increment the value at $l$ by $v$. This increments all values on $[l, n]$ by $v$. To make our range exactly $[l, r]$, add $-v$ to $r + 1$. Doing this for all segments before doing the scanline, the scanline's value at each point represents the sum over all segments overlapping that point, and you can take the minimum of the values at all points. An image that may be helpful
 » 2 years ago, # |   +2 What is test 2 of D? Please.
 » 2 years ago, # |   +53 What was WA29 in Problem E?My logic was: Do a BFS from B. Find the node with max depth (say V) such that V to A and to V to C shortest paths exist — I basically conjecture that the common path will be a prefix, and once the paths bifurcate, they will never meet. Then the answer can be calculated appropriately, by giving the smallest edge weights to the common path and the remaining smallest to others.What's the countercase? I saw many people failing on WA29
•  » » 2 years ago, # ^ |   0 Same solution here. WA on 29.
•  » » 2 years ago, # ^ |   +48 Try this:6 6 1 4 61 1 1 1 5000 50001 22 33 44 55 62 6
•  » » » 2 years ago, # ^ |   0 answer is 5004?
•  » » » » 2 years ago, # ^ |   +5 6
•  » » » 2 years ago, # ^ |   0 What is the answer to this?
•  » » » » 2 years ago, # ^ |   0 6
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 for me i was just considering nodes on shortest path from a to b. when i removed that condition i.e checked for every node, I got AC.
•  » » » 2 years ago, # ^ |   +14 Your name :D, I'm dreaming to learn dp too :(
•  » » 2 years ago, # ^ |   +15 While your conjecture is correct, it is not necessary that the sum of lengths of paths ab and bc in the optimal answer is equal to the sum of lengths of shortest paths ab and bc.
•  » » 2 years ago, # ^ |   +50 Issue with that approach is, the paths doesn't have to be shortest for both nodes individually, there can be a case that, individually path for A and C is not shortest from B, but because of common prefix being longer, total cost can be lesser.
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 the first thing, ans must be long long, not intthe second, i think you must try all v and the and is sum(1,BV) + sum(1,AV+BV+CV) (only if AV +BV +CV <= M )and get minbecause sum(1,BV) + sum(1,AV+BV+CV) not depend on p[i] or BV, it depend on both, so u want to try all
•  » » 2 years ago, # ^ |   +21 You solution was wrong in a special case. You need check it can be the answer. Just BFS in the Edge 3 times,From A,From C,and the last From B To check it can be the answer.The total of V must <= M,and then to update the answer You should update the answer in every possible point. Hope it will help you.Good luck!
 » 2 years ago, # |   +1
•  » » 2 years ago, # ^ | ← Rev. 2 →   +3 Can you help me with my solution for problem E. https://codeforces.com/contest/1343/submission/77567588 Here I have applied BFS from a->b and then from b->c and counted which edge is used how many times in our total journey. and then sorted weights and assigned them accordingly for minimum total sum. (least weight is assigned to the edge with most visits).
•  » » » 2 years ago, # ^ |   0 I did the same, and am getting WA on 320th case(Test case 4) stefdasca
 » 2 years ago, # |   +8 Great Round! Problems were very interesting. Just feel bad because I started around 20 mins late due to personal issues....Solved ABC. Couldn't solve D (failed Test-2). Any ideas?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +1 Fix some $s$, which will be intended common sum of all pairs.1) Show that you can always change the sum of any pair to $s$ in 2 changes2) When can you change the sum to $s$ in 0 changes?3) When can you change the sum to $s$ in 1 change?Then, use some kind of data structure so that you can answer for all $s$ in $1 \leq s \leq 2k$ and get the min over all of them as your answer.
•  » » 2 years ago, # ^ |   +6 Construct intervals for each pair as follows:Each interval corresponds to choices of $x$ where this pair can be shifted by changing atmost one element of the pair. For example: if $k = 4$, and the pair is $(2, 3)$, the interval is $[3, 7]$. Then, sweep through all intervals by moving one step at a time, from $2$ to $2k$. At each step, you can compute the current score by seeing how many intervals overlap at this point (the depth). You will also need to consider those intervals contributing $0$ at this point, which occurs exactly when $x$ matches the sum of the pair corresponding to that interval. All those intervals not covering the current $x$ must contribute $2$ to the score.https://codeforces.com/contest/1343/submission/77572280
•  » » » 2 years ago, # ^ |   0 Seems like a great approach. Mine was too complex that I spent too much time and ended up not being able to solve it within contest time. Haha. Nonetheless, solved it with my approach.
•  » » 2 years ago, # ^ |   +5 Thank you Shisuko and ameya! Understood both your solutions.
 » 2 years ago, # |   0 what is the greedy solution of D?
•  » » 2 years ago, # ^ |   +4 I think, D is DP question. For each pair, calculate the maximum and minimum value, you can get in 1 change. Also calculate the number of pairs adding up to some x.min=min(a,b) + 1 max=max(a,b) + kThen maintain segments, and iterate from 2 to 2k, counting how many need less than one change. you know the ones needing no changes, so you can calculate the numbers needing one change, and the rest need two changes. Find the minimum of that.https://codeforces.com/contest/1343/submission/77536701
•  » » » 2 years ago, # ^ |   +6 Did the same but got WA on test 2
•  » » 2 years ago, # ^ |   0 Not sure if this counts as greedy or not, but anyways:Calculate how many pairs exist with this or that sum using a map. Enumerate all possible target per-pair sums. From each of them, the number of steps needed is n / 2 — — . The former is already in the map, the later can be computed if you notice that for pair (WLOG assume that x <= y) the minimum that you can reach with one operation is x + 1, and the maximum is y + k (two binary searches can be used here). Then just select the best target sum and output the answer for it.
 » 2 years ago, # |   +14 Great round, guys!We are going live now:https://youtu.be/ppk9pXL9rR4
 » 2 years ago, # |   0 People with rank between 2300 and 11100 all solved 3 prob, so you have 9000 person solved 3 problem, bad choice of difficulty of the problems IMO.
 » 2 years ago, # |   0 Wow, hardest problem A I have seen, I was able to solve B and C easily. But I got stuck on A. :(. Could anyone shared how they approached it? Thank you
•  » » 2 years ago, # ^ |   0 You have to find any a $P=2^K-1$, starting from $K = 2$, that divides N. Then print $\frac{N}{P}$.
•  » » » 2 years ago, # ^ |   0 Can you explain why 2^k -1? I only know a(r^n -1)/r-1 to be the summation of geometric progression.
•  » » » » 2 years ago, # ^ |   0 We have: $x + 2x + 4x + ... + 2^{K-1}x = N$Now, take x common and you end up with $x(1+2+4+...+2^{K-1})$Apply the summation of geometric series formula and you end up with $2^K-1$.
•  » » » » » 2 years ago, # ^ |   0 Oh wow I'm dumb. Really appreciate the explanation!
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +5 Let us look at the numbers in binary form-$2^0 = 1$$2^1 = 10$$2^2 = 100$$2^3 = 1000$$2^4 = 10000$Now, $2^0 + 2^1 + 2^2 + 2^3 = 2^4-1$ (i.e. 1111 in binary from)
•  » » » » » 2 years ago, # ^ |   0 Oh wow that's such a cool way, thanks so much!
•  » » 2 years ago, # ^ |   0 The trick is to know that x+2x+4x+...+2^kx=x(1+2+4+...+2^k)=x(2^(k+1)-1) because it is a geometric progression. So you could precompute the first 32 numbers 2^n-1, and look if any of them divides nYou can find out more information about that in here
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 x+2x+4x+.....+2k-1 = n using sum of G.P, we get x = n/2k-1. So i looped starting from k=2,for any 'k' if 2k-1 divides 'n' , then break and print n/2k-1. My solution : 77509910
•  » » 2 years ago, # ^ |   0 Thank you Zeus_NoT_Zues, convex_Hulk, accha_baccha. I understand it perfectly now. They key was on removing the sum of powers of 2 from the equation and looping.  int T = 1; cin>>T; while(T--) { int n, sum, i = 2; cin>>n; sum = pow(2, i) - 1; while(n%sum != 0 ){ i++; sum = pow(2, i) - 1; } cout<
•  » » 2 years ago, # ^ |   0 Could not get what is wrong here and found only after competition ended: #include int main() { uint32_t t = 0; scanf("%u", &t); for (int i = 0; i < t; ++i) { uint32_t n = 0; scanf("%u", &n); uint32_t s = 1; uint32_t pw = 2; while (true) { s += pw; pw <= 1; if (n % s == 0) { printf("%u", n / s); break; } } if (i != t - 1) printf("\n"); } return 0; } Correcting one line makes solution pass all tests :)
 » 2 years ago, # | ← Rev. 2 →   -29 [Deleted]
 » 2 years ago, # |   +6
•  » » 2 years ago, # ^ |   0 lol me too XD
 » 2 years ago, # | ← Rev. 2 →   0 For D my solution is probably incorrect but approach seems fine We have to do something like find range of sum of both elements such that only 1 element is changed. like for the test case of: 6 6 5 2 6 1 3 4 the ranges be like [5:11] for arr[0] and arr[n-1-0] and [3:9] for arr[1] and arr[n-1-1] and so on Then do something like psum[left]+=1 and psum[right]+=-1 for each pair of elements as stated in the problem. Then do the prefix sum across it. Then add the actual sum of these pair of elements as in that case we won't need to change even one element as psum[arr[i]+arr[n-1-i]]+=1 Then find max value of x which satisfies most ranges. The answer being n-(the above found max val) But I think there is some repetition in it. Can someone explain the issue with this soln?? EDIT: The code is: https://ideone.com/sb6eFB
•  » » 2 years ago, # ^ |   0 This is very similar to the solution I used to solve D, except that I used a Binary Indexed Tree to quickly process the psum[left] += 1 and psum[right] -= 1 updates.
•  » » » 2 years ago, # ^ |   0 Can you please look into my BIT solution??Getting WA!! Link to Soln
•  » » 2 years ago, # ^ |   0 You can check my solution. I used a similar approach. Divided the range into four subsets. Added 0,1 or 2 on the basis of conditions. Then took the sum value which required minimum changes
•  » » 2 years ago, # ^ |   0 the range for arr[0] and arr[n-1-0] will be [5:12] , for arr[1] and arr[n-1-1] will be [4:12] and so on if value of k is 6 (seems like from the example)
 » 2 years ago, # |   0 Went for the W by skipping D and trying to solve F since I had an idea...ended up solving none of D, E, F :(
 » 2 years ago, # |   0 in D sample test case 1 :_ part 3 : 8 7 6 1 1 7 6 3 4 6 why is the answer 4 ??
•  » » 2 years ago, # ^ |   0 for the first half, you can change 6 and 7, and for the second half, you can change 3 and 4, you can always find a way to make these pairs equal by changing those values to certain values.
•  » » 2 years ago, # ^ |   +3 you can always change some a[i] to have x is k+1 so the answer <= n/2
 » 2 years ago, # |   0 Yay. I solved the first 5 with a penalty of 141.If only I was in competition, and not OOC...
 » 2 years ago, # |   -9 There was a mistake in Problem C in the 4th test case explanation during the contest. i.e [1,−1000000000,1,−1000000000](assume all numbers are underlined) due to this I was confused and consumed 5 minutes. but now it's fixed.
 » 2 years ago, # |   0 Do these numbers also include those participants who have rating above 1600?
•  » » 2 years ago, # ^ |   +12 yes they do, since no one solved F in competition
 » 2 years ago, # |   +1 can anyone give a strong test case for problem D?
•  » » 2 years ago, # ^ |   0 I've made a strong test case that my programme failed on. 1 8 7 4 7 7 7 6 6 6 5 The answer is 2, we should change the first number and the last number.
•  » » » 2 years ago, # ^ |   0 It passed for me
 » 2 years ago, # |   0 i sent the answer of d in time and it not counted . can u help me in this .
 » 2 years ago, # |   +27 What is the solution for F?
•  » » 2 years ago, # ^ | ← Rev. 6 →   +17 It is basically brute force.First, decide what can be put at $p_1$, and brute all of them. From problem constraints, the number must be contained in a segment with length 2, and it must not appear in more than one length 2 segment. (Why?) Then, you can also decide on $p_2$ since it is just another element in the segment.To decide what $p_3$ is, you can pick a not-yet-used segment. There is only one valid segment, and it satisfies the following: It contains exactly 1 unused element. For the already-used elements that also exist in this segment, they must be put in valid range in the answer array. (e.g. if you are deciding on what $p_6$ is, and the current segment has length 4, the 3 used elements must be in $p_3$, $p_4$, $p_5$, but in any order) Then, the one unused element is $p_3$. If you cannot find a valid element, you can cut this branch. Follow this approach until $p_n$.I coded it in a $O(n^4)$ way but I believe $O(n^3)$ way of this exists.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +12 77550191 $O(n^4/32)$ using bitset77584382 $O(n^2)$ using the fact that only the last and maybe the first element appears once in the input
•  » » » 2 years ago, # ^ |   0 Can you explain your O(n^2) solution.
•  » » » » 2 years ago, # ^ |   +3 Lemma: Only the last and maybe the first element appears once in the inputYou know that one of them is the last element, fix the last element and remove its segment (it's unique), again the lemma is true, keep doing it while the last element is unique, when it is not, one of the elements is the first, then fix the first element, now the last element must always be unique and you can restore the permutation.So summarizing, you have two possible last element this take $O(2*n^2)$ and each one can return two possible first element, so you need $O(4*n^2)$
 » 2 years ago, # |   0 Why are the ranks of official standings (not unofficial) ambiguous? some of them,3 questions answered,penalty 100,rank 4501. some others, 3 questions answered,penalty 99, rank 4904. why is it that people with more penalty are ranked better? there are more such ambiguity as well....
•  » » 2 years ago, # ^ |   +1 Sometimes when you refresh Div3 rounds during the hacking phase it removes unrated contestants, but after the hacking phase it will not be ambiguous
 » 2 years ago, # |   0 excuse me, problem E, is graph connected ?
•  » » 2 years ago, # ^ |   +11 obviously, when it's stated clearly that there is a path between any two pair of nodes.
•  » » » 2 years ago, # ^ |   0 oh, you're right lol :v
•  » » 2 years ago, # ^ |   +8 Yes, this fact is mentioned in the question at least twice. The second line of the question says — It is guaranteed that there is a path between each pair of vertices (districts). The second last line of the input section says — It is guaranteed that the given graph is connected.
 » 2 years ago, # |   +12 Hello! I have two submissions for problem E. The only difference between them is how I read the prices. 77571570 gives me wrong answer on test 22. 77571013 is accepted. Can you tell me please why the 1st submission encountered a problem despite that the prefix array if declared as long long.
 » 2 years ago, # |   0 How do I give input for hacking in problem A.I tried giving like4100010134234 but says invalid input. Can someone explain why?
•  » » 2 years ago, # ^ |   0 There needs to be a valid answer. There is no valid answer for 134
 » 2 years ago, # | ← Rev. 2 →   +4 Actually D is not as hard as it seems. I solved it greedy. For each pair a[i] and a[n — 1 — i] we need to count three numbrers: 1) sum of a[i] and a[n — 1 — i] without changing a[i] or a[n — 1 — i] 2) min sum of a[i] and a[n — 1 — i] if we changed a[i] or a[n — 1 — i] 3) max sum of a[i] and a[n — 1 — i] if we changed a[i] or a[n — 1 — i]. First is just a[i] + a[n — 1 — i], second is min(a[i], a[n — 1 — i]) + 1 (we take the min value and make other 1, thus we get the min sum), third is max(a[i], a[n — 1 — i]) + k. Now we need to differ each of them from others. We can do it by matching a number to each value: 0 for first, -1 for second and 1 for third. Then we put this three values in the array and sort it. Not we need to iterate over array and count the answer. Time complexy O(nlogn) because of sorting the array.Sorry for my poor English.Code.
•  » » 2 years ago, # ^ |   +2 i calculate three value as you, but i don't sort them, i use prefix for two last value ! 77542245
•  » » » 2 years ago, # ^ |   0 Oh, nice idea, thanks.So we can reduce time complexy to O(n + k) with your idea. But it works in 300+ seconds, can you please add this to your code to see how fast it will be. ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
•  » » » » 2 years ago, # ^ |   +1 yes, right ! you can replace false and NULL with 0, it is shorter :v
•  » » 2 years ago, # ^ | ← Rev. 2 →   +1 Same idea. Just make it easier to understand. Code
•  » » 2 years ago, # ^ |   0 I calculated the three values but hadn’t sorted it, so I failed on this test case(I made it): 1 8 7 4 7 7 7 6 6 6 5 The correct answer is 2 but my answer is 3. Do anyone know why? Do I have to sort it?
 » 2 years ago, # |   0 Any DP approach for problem D?
 » 2 years ago, # |   +21 very good contest ,I love it but i think it is a bit difficult as a Div.3
•  » » 2 years ago, # ^ |   +8 IT was approximately Div 2.5
•  » » 2 years ago, # ^ |   0 but I like it better, so we push the limits a bit more
 » 2 years ago, # |   0 77574862 This is giving wrong answer for fourth test case if someone could help. Thanks :).
•  » » 2 years ago, # ^ |   0 Problem E.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +6 My solution: BFS from A, B, C. cal d[0][u] is the shortest length from u to A, 1 for B and 2 for CAny move way must have some u which the path is A -> U -> B -> U -> C and then the length is AU+2BU+CU.So we use exactly AU+BU+CU p[] of m p[]. and because the weight from U to B is calculated twice, we'll use BU first p[] for them.So we can solve problem by for U from 1 to n, each U we call the weigth if we move A -> U -> B -> U -> C and get min. Only calculate if AU+BU+CU<=m
•  » » » 2 years ago, # ^ |   0 Nice Solution.
 » 2 years ago, # |   0 For problem A, what would the output be for n=29? Can we obtain a positive integer value for x?
•  » » 2 years ago, # ^ |   0 "It is guaranteed that at least one solution exists."For n = 29, I do not think there are any solutions.
 » 2 years ago, # |   +11 Misread "district" as "distinct" in qE :/
•  » » 2 years ago, # ^ |   +3 Thought I was the only one. I was getting WA due to the distinct part lol
 » 2 years ago, # |   +1 https://codeforces.com/contest/1343/submission/77576736wrong answer 39th numbers differ - expected: '1', found: '2'Is it any chance to see 39th test case?
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Sorry ; I couldn't do this in your code itself ; as I am bad at using Python.BUT LUCKILY YES ( Click on view to see test cases ) ; and you may also see ; the solve function ; to how I did it ( in case you get into this sort of trouble in future ! )I hope this helps !
•  » » » 2 years ago, # ^ |   0 Thank you! It works: https://codeforces.com/contest/1343/submission/77630846
 » 2 years ago, # |   0 can anyone explain the approach for problem E??
•  » » 2 years ago, # ^ |   +19 Note that a possible shortest path follows the form of A -> k -> B -> k -> C, where k is any vertex in the graph. Define A[k] as the shortest distance from node A to node k (similar definitions for B[k] and C[k]). Note that we can further break this down into two parts: there should be a total of A[k]+B[k]+C[k] distinct edges visited, with B[k] of those edges being visited twice. We want to take the smallest edges to be repeated, so we sort our prices array and generate prefix sums for fast queries. Now, you can do BFS to calculate the minimum distances for A,B,C and iterate over k. It'll look something like min(psums[B[k]]+psums[A[k]+B[k]+C[k]]) for all k such that A[k]+B[k]+C[k] <= M.
•  » » » 2 years ago, # ^ |   0 Hey I am trying to generate shortest path from a->b and b->c then assigning lowest cost to the path's edges. Im aware this is wrong for e.g. in first case I get 7 rather than 6 because I'm assigning 1->{1,2} and 2->{1,3}. Is there any hopes to this solution can this be implemented in right way? Codevector path(int a,int b,vector& adj) { VII par(adj.size()+1,0); queue q; q.push(a); par[a]=0; while(!q.empty()) { int u=q.front(); q.pop(); if(u==b) break; for(auto it:adj[u]) { if(!par[it] && it!=a){ q.push(it); par[it]=u; } } } VII path; path.pb(b); for(int x=par[b];x!=0;x=par[x]) path.pb(x); reverse(all(path)); return path; } main() { int n,m,a,b,c; cin>>n>>m>>a>>b>>c; VII w(m); vector adj(n+1); for(auto &x:w)cin>>x; sort(all(w)); for(int i=0;i>x>>y; adj[x].pb(y); adj[y].pb(x); } VII s1=path(a,b,adj); VII s2=path(b,c,adj); map assign; ll sum=0; int ptr=0; for(int i=1;i
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 How would you guarantee that paths A[k], B[k],C[k] do not intersect to claim that there are A[k]+B[k]+C[k] distinct edges?
•  » » » » 2 years ago, # ^ |   0 There is no problem if they intersect, it still works. Vertex k can be same as B or C.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +4 I need to go from vertex A to B and then B to C minimizing the cost of travel. I have the flexibility to assign a weight to an edge from given weights.Obs 1: If I have to travel Q edges, I will always want to make them the Q smallest edges.Obs2: Let's say path from A to B has P edges and path from B to C has Q edges. The max edges I need to traverse is P+Q, but if somehow, I can find overlap between P edges and Q edges, that would be best since, this means, I am reusing smaller edges leading to a lesser sum. This tells us we need to go from A -> V -> B -> V -> C. so that V to B and B to V is reused.Let's say A — V is P edges, V to B is Q edges and V to C is R edges. I will assign V to B smallest Q edges. Then assign next P edges to A to V path and then rest R edges to V to C path.So iterate for all X from 1 to N and your ans is min of all.
•  » » » 2 years ago, # ^ |   +3 nicely explained thanks :)
•  » » » » 2 years ago, # ^ |   0 hmmm.....theeek....ab muh me lele
 » 2 years ago, # |   0 Any Suggestion , what can be wrong in my logic for question D .Mycode D
•  » » 2 years ago, # ^ |   0 This will TLE since you're doing T*200000. Note that T*N is passing the TL and not T*20000.
•  » » » 2 years ago, # ^ |   0 In editorial complexity is O(T*n*logn) ,it still passes
•  » » » » 2 years ago, # ^ |   +5 Yes.Understand that T*N is different from T*200000.
•  » » 2 years ago, # ^ |   0 You spend too much time in the memset! In editorial complexity is O(T*n*logn) ,it still passes,Because the totN<=200000 But you memset 200000 in every Case, So it TLE So you can fill the array to zero in every N just like this for(int i=1;i<=N;i++) Ins[i]=In[i]=0 But not memset(Ins,0,sizeof(Ins))Hope it can help you.Good luck!
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 But , tle is not problem , i am getting wrong answer at 3rd sample case., what could be wrong?\Also , thanks i will try to avoid memset...
 » 2 years ago, # | ← Rev. 2 →   +1 Sir vovuh Can you please explain why I am getting WA on test 2 I think my submission does not have use of unitialised variable but I am getting Wrong Answer and the judge says it uses uninitialised variable Please explain where I am wrong in problem D . Sorry for my poor english and thanks in advance. I hope you will reply This is the submission link77560252
 » 2 years ago, # |   0 Yessss Div3 I love it :D
 » 2 years ago, # |   +22 How to solve problem F ????
•  » » 2 years ago, # ^ |   +5
 » 2 years ago, # |   0 Can anyone explain the solution of D?
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Call L=a[i] R=a[n-i+1] (because of my lazy xD)So if x=L+R, we use 0 replace, in range[min(L,R)+1,max(L,R)+k] we use 1 and 2 for otherCall E[i] is the number pair have sum exacly iCall Up[i] is the number pair have max(L,R)+k=i (it means if x is more than i, we must use two replace)Call Down[i] is the number pair have min(L,R)+1=i we can see, if x in range [i,2*k] must use 2 then x in range [j,2*k] ji also use 2We call prefix for up and down Up[i]=Up[i]+Up[i-1], Down[i]=Down[i]+Down[i+1];In fact, we always use most n/2 replace for x=k+1 so the answer<=n/2Which x we have n/2 pair, E[x] pair have exactly value, so there is n/2 — E[x] pair wrong which use at less 1, have Down[x-1] + Up[x+1] pair must use two replace, so we must add Down[x-1] and Up[x+1]-> ans=min(n/2, n/2-E[x]+Down[x-1]+Up[x+1]) 2<=x<=2*k
•  » » » 2 years ago, # ^ |   0 Hey I used exactly the same approach but using upper bound and lower bound 77581160 can you see what Ive done wrong
•  » » » » 2 years ago, # ^ |   0 I think upper and lower on X is wrong
•  » » » » » 2 years ago, # ^ |   0 Upper Bound will give me index of that element greater than R and if its index is X i can say there are (N-X) elements greater than RFor Lower Bound Will give me Index of element Greater than equal to L and So this Index-1 will be the index of Number Smaller than L and so this +1 will be Number of Elements Smaller than L
•  » » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 with a[i]+a[n-i+1] you can't know with 1 replace it can be x or notexample a[i]+a[n-i+1]=12 (k=9)with 6 6 you can change to [7,15]with 3 9 you can change to [4,18]so with only 12 you can't know how much replace to get 6 or 18
•  » » » » » » » 2 years ago, # ^ |   0 With [6,6] I will be stroing (1,15) and for [3,9] I will be storing [1,18] I am assuming initially Answer to be N Then substracting for Exactly similar elements and then Adding 1 for those who will bcome equal (After Changing both of their elements)
•  » » » » » » » 2 years ago, # ^ |   0 Ok Done I got the error and got Accepted though after the contest
 » 2 years ago, # |   0 Can anyone explain the solution of D without the use of fenwick tree?
•  » » 2 years ago, # ^ |   0 /*THIS IS ONLY IMPLEMENTATION PART AS LOGIC IS ALREADY DISCUSSED ABOVE*/we can obtain the 3 values for every index i 1) min possible min(a[I],a[n-i-1])+1; ==> left most (l) 2) max possible max(a[I],a[n-i-1])+k; ==> right most (r) 3) there sum a[I]+a[n-i-1] ==> its sum (s)now create 2 arrays 1) enter array => it will look after range l-s (including both) 2) exit array => it will look after range s-r (including both)now we can iterate over all cases by loop like int ans=n;int curr_savings=0; rep(i,1,2*k+1) { curr_savings+=enter[i]; ans=min(ans,n-curr_savings); curr_savings-=exite[i]; }
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 For each i from 1 to n/2 consider this: L=min(arr[i],arr[n-i+1]) and R=max(arr[i],arr[n-i+1]) .-If we make 0 changes we can get sum equal to arr[i]+arr[n-i+1]-If we make 1 change we can make the pair sum equal to all the values from L+1 to R+k (except L+R which needs 0 changes).-To get all other values as sum you need to change both arr[i] and arr[n-i+1](2 changes).Now using this create a partial sum array.Read from hereIterate from i=2 to i=2*k on the array and take the minimum value.Link to my code: https://codeforces.com/contest/1343/submission/77568588
•  » » » 2 years ago, # ^ |   0 your solution is very helpful and understandable.thank you.
•  » » » 2 years ago, # ^ |   0 R should be max(a[i], a[n-i+1]) right?
•  » » » » 2 years ago, # ^ |   0 Yes,edited it.
 » 2 years ago, # | ← Rev. 2 →   -15 Me after doing C.
 » 2 years ago, # |   0 where is editorial
•  » » 2 years ago, # ^ |   0 Wait 1-2 days.
 » 2 years ago, # |   0 One more case of cheating by using forged hacks. See: hack detailsMikeMirzayanov vovuh Please check. A particular value of n is hardcoded to print wrong answer intentionally. The hacker and hacked user have similar user name as well.
•  » » 2 years ago, # ^ |   +4 Nothing new, it happens all the time.
•  » » » 2 years ago, # ^ |   0 Yes, but I haven't found any solutions like that. (or it's already hacked)
 » 2 years ago, # |   0 77581160 Can someone tell me what Ive done wrong in Problem D getting WA on tc 461 of test 2
 » 2 years ago, # |   +18 The server was amazingly smooth today!
 » 2 years ago, # |   0 Hi Codeforcers,Can anybody give me a hint to solve div 3 candies A problem? I know that it forms a GP of sum of n series but couldn't get my way around to solve the problem?Help if anybody can. Thanks in advance.
•  » » 2 years ago, # ^ |   0 For some valid x and k, n = x*((2^k)-1).Hence, check for all k's such that 2<=k<=30, if for some k, n is divisible by (2^k — 1), you got the answer, x = n/(2^k — 1)
•  » » » 2 years ago, # ^ |   0 Thanks buddy.
•  » » 2 years ago, # ^ |   +3 n is sum of a geometrical series. Use formula for geometrical series apply the conditions. Hope you will get an idea what to do
•  » » » 2 years ago, # ^ |   0 Thanks buddy.
•  » » 2 years ago, # ^ |   0 Yeah. It is a G.P.You need to find (X,K) such that X * (power(2,K-1) — 1) = NStart from K = 2 to 50 (why 50 suffices? since N <= 10^9, hence 2^50 will exceed 10^9) and check for value of K, (power(2,K-1) — 1) divides N, whenever it divides, you can print that corresponding X.
•  » » » 2 years ago, # ^ |   0 Thanks man..
•  » » 2 years ago, # ^ |   0 The logic that I implemented was: As you need to print any of the answers as multiple answers are possible and also k>1 which means that at least you will have x+2x should be equal to n, following this if 3x (x+2x) is not equal to n then you will see for x+2x+4x and so on... till the time you get it equal to n and finally when you get it you just need to print n/x. Hope this helps. You can have a look at my solution for reference. Happy Codingimport java.util.Scanner;public class Prob1 { public static void main(String[] args) { Scanner s=new Scanner(System.in); int t=s.nextInt(); for(int i=0;i
•  » » » 2 years ago, # ^ |   0 Thanks man...
 » 2 years ago, # |   +10 My Approach for D:Since array has n elements so there is n/2 pair(a[i],a[n-i+1]) and sum of pair will be x.Minimum possible sum for a pair is 2 and maximum possible sum for a pair is 2*k. Then x must be between 2 and 2*kI calculate no of replacement for each x between 2 and 2*K and finally take minimum of all x[i]Now the challenge is to calculate each x[i] in O(1) complexityFor each x[i] there will be 3 types of pair according to sum of pair For some pair sum of pair will be exactly x[i], for such pair no replacement is needed. If x[i] is range (min of pair + 1 , max of pair + k) then this x[i] can be achieved changing one element of the pair. If value is out of that range then two value of pair will be changed to achieve x[i] as sum of pair. I calculate range for 1 change for each pair, then i take an array ar and ar[i] indicate how many pair can reach i changing one element. Finally for each x[i] I check how many pair reach x[i] making 0 change(t), 1 change(y) and 2 change(z)minimum of all y+2*z is answer.MY Submission
 » 2 years ago, # | ← Rev. 2 →   0 [Deleted]
•  » » 2 years ago, # ^ |   0 you have pairs: 1+6 = 7 3+1 = 4 8+7 = 15 5+6 = 11 let x=11 then: 5+6 = 11 (replace 1 with 5) 3+8 = 11 (replace 1 with 8) 8+3 = 11 (replace 7 with 3) 5+6 = 11 (stays same) result is 3 because there are only 3 replaces
•  » » 2 years ago, # ^ |   0 5 3 8 5 6 3 8 63 changes and sum of all pairs is 11
•  » » 2 years ago, # ^ |   0 Yes 5 3 8 5 6 3 8 6 One of the example with 3 changes.
 » 2 years ago, # | ← Rev. 2 →   0 Cheat and duplicate account alert- bit.ly_cfdiv23boostlive sachinganguly69
 » 2 years ago, # | ← Rev. 2 →   +19 Solution for DReferenceProblem recapGiven an array with n elements (where n is even), find the least number of operations such that the sum of each number with its mirror element is the same (i.e. a[i] + a[n-1-i] = x for all i)Observations The key observation here is to realize that there are 3 options for any pair a[i] and a[n-1-i]. These are: make no changes, make 1 change (only one of the element changes) and make 2 changes (both elements change). Consider two mirror elements, a[i] (lets call this x) and a[n-1-i) (lets call this y) If (x > y) then swap them such that x is always smaller or equal to y If you were to make zero changes to either element, their sum would be exactly one number (i.e. x + y) With one change, their sum could range from (x + 1) to (k + y). This is because you could make y=1 (set y to the smallest possible positive number per the problem constraints), or you could make x=k (set x to the largest possible number per the problem constraints) With two changes, you could cover the entire range of possible sums (i.e. 2 through 2*k — since you could make both x and y either equal to 1 or to k, or anything in between) Implementation We need a way to mark these possible sums and ranges for each mirror pair of numbers. Use prefix sums. Create an array for tracking frequency of zero changes. Create an array that tracks ranges for one change (this will be a prefix array). For each pair, zero changes are needed when sum = x + y. Increment zeros[x + y]. For each pair, mark the range that they can go to with exactly one change. This is the range (x + 1) to (y + k) described above. To do this, increment ones[x + 1] by 1, and decrement ones[y + k + 1] by 1. Compute the prefix sum of ones. Essentially, ones[sum] = number of pairs that can add up to sum with just one change. Then iterate through each possible sum (from 1 through 2*k) and see how many changes are needed to get to that sum. Cost = 1 * (ones[sum] - zeros[sum]) + 2 * (n/2 - ones[sum]). You need to subtract zeros[sum] from ones[sum] to avoid over-counting (as ones[sum] includes zero[sum]). Similarly, you need to subtract ones[sum] from twos[sum] (there's n/2 pairs in total and to find pairs where both elements need to be changed, remove ones[sum] which excludes the pairs that can get to this sum with either one or zero changes) Find the sum with the lowest cost and that's your answer
•  » » 2 years ago, # ^ |   +1 Great explanation, Thank you :D
•  » » » 2 years ago, # ^ |   0 Thanks, appreciate it!
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 in the cost formula why it is not 1*(ones[sum]-zeros[sum])+ 2*(n/2-(ones[sum]+zeros[sum]))as ones[sum] holds the value of sum we can get with one change but we also need to exlude the sum we got with zero changes,right? Can you please clarify it?
•  » » » 2 years ago, # ^ |   0 Say you have just two elements: {1, 5} with k=5. So zeros[6] = 1. And ones[2...10]=1. Notice that we have added one to both zeros[6] and ones[6]. So ones[x] is cumulative and includes zeros[x]. The actual definition of ones[x] = exactly_ones[x] + zeros[x]. Hence if you just want to get the twos[x], it's sufficient to just remove ones[x].
•  » » » » 2 years ago, # ^ |   0 Thanx,mate!Now,i get it..BTW,great explanation.
•  » » 2 years ago, # ^ |   +1 Great solution, thanks for sharing!!
•  » » 2 years ago, # ^ |   +3 seriously thanks broo...greatest explaination so far
 » 2 years ago, # |   0 Can someone please see and tell why my code(attached below) was shown the wrong answer for the second question when submitted, Highly appreciatedimport java.util.Scanner;public class Prob2 { public static void main(String[] args) { // TODO Auto-generated method stub Scanner s=new Scanner(System.in); int t=s.nextInt(); for(int i=0;i
•  » » 2 years ago, # ^ |   0 For n=12 it will generate 6 8 10 12 14 16 3 11 7 15 11 19 where 11 is repeated. all the value must be distinct.
•  » » » 2 years ago, # ^ |   0 Thank you, it was silly of me
 » 2 years ago, # |   0 Is there someway to extract complete test case as I'm getting this in Problem Ewrong answer 320th numbers differ — expected: '4', found: '6'
•  » » 2 years ago, # ^ |   0 Try printing out the input when current case = 320, add few ifs so that the solution does not fail on cases 1,2 and 3
•  » » » 2 years ago, # ^ |   0 Even the input file is not fully visible.
 » 2 years ago, # |   +1 IMO D was difficult for a normal Div #3 contest, wasted a lot of time on D :(
 » 2 years ago, # |   0 Can someone tell whats the issue with my approach to Problem E? Wrong answer on Test Case 4 1. Get the shortest path from a to b then b to c. And store all the edges of the route. 2.sort the edges based on the frequencies in descending order. And then allocate the prices from smallest to largest. The edge repeating the most will have the minimum price and so on.. I am getting wrong answer in test case 4 on 320 line which is not visible and hence don't know what edge case am I missing. Any help would be appreciated
•  » » 2 years ago, # ^ | ← Rev. 2 →   +1 I think shortest path is not optimal always.Let a to b has 3 edgesShortest path from b to c has 3 edges which is different from a to bTotal edge 6Now consider there is another path from b to c which has 4 edges(not shortest) but two two of them common with a to bThen total edge 3+1=4So second one will be optimal although shortest path not taken.
•  » » » 2 years ago, # ^ |   0 Thanks it made everything crystal clear
 » 2 years ago, # | ← Rev. 9 →   +101 Here as the virtual Moss for Codeforces, busting cheaters and getting them out of their bills. I hereby present to you the Inter-College Cheat Group(including NITs and HIET). restfulCoder pawangeek ankitkh6842 nit_ay03 saranshgupta1999 sreejit_007 sachinganguly69 bit.ly_cfdiv23boostlive inductor harry_india vknjwnjc rustic_coderNot to mention their ranks are (18-19-20-21-22) in today's DIV3 If this comment doesn't serve the purpose of un-rating or banning them. I don't what will. here goes the solutions775627727756441077556321775659497756259577563089775646797754957877565649 He thought adding comments will save him775640277755801977557813
•  » » 2 years ago, # ^ | ← Rev. 4 →   +8 how ?
•  » » » 2 years ago, # ^ |   +4 Oh my god this guy inductor ranked 5 in the contest. Still their submissions are not skipped. All these candidates mostly ranked in the list are below 100. I request vovuh and MikeMirzayanov look into this and skip their submissions because as many of their ratings below them are effected.
•  » » 2 years ago, # ^ |   +3 Oh my god Same submissions. I haven't seen these many people copying the solutions. This is something vovuh has to look at and disqualify these people.
•  » » 2 years ago, # ^ |   0 good work!!
•  » » 2 years ago, # ^ |   0 Really good work. Please ban this guys. We here are sitting and busting our asses and solving the problems and these guys are straight away copying the codes.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +2 MikeMirzayanov vovuh These people must get ban.
•  » » 2 years ago, # ^ |   0 One more: ashwani45 and restfulCoder both have same submission.
 » 2 years ago, # |   0 Can somebody prove the intuition of problem E? I had the same idea during the contest but i don't have an actual proof why the case when the sum of the distances is greater than m can be excluded.
•  » » 2 years ago, # ^ |   +5 The sum of the Distances, greater than "m" will always be excluded, because, you don't have a Prefix Sum, for prefix[i], where i>m.Since, we are getting only "m" values, we have "m+1" Prefix sums, so, there is no meaning to include the case, where the sum of distances > m.I hope, it helps. Thank you!
•  » » » 2 years ago, # ^ |   +8 Yes, i understand this, but why a case when we repeat some edge, and the total number of edges exceeds m is excluded? For example, in the path from node to c, there are some edges identical to the edges from b to node. Isn't this case possible?
•  » » » » 2 years ago, # ^ | ← Rev. 5 →   +19 We're breaking down the road from A -> N -> B -> N -> C. We're also assuming that the number of repeated edges are those from B -> N(Green Edges)So Here A -> N = 4N -> B = 1B -> N = 1N -> C = 5So total different numbers used = 4(A->N) + 1(N->B) + 5(N->C) = 10But the number of different edges are 6, so we should exclude this? Why? Because there's always a path that minimizes the answer and uses less than m edges, And that happens here if we chose A as our N.So In our case We're always looking for a node $X$. Such that There's no repeated edges from A -> N and from N -> C, So only repeated edges happen at B -> N.Consider the following 4 cases, 1-C lies before A, as in the photo, So the best node to choose would be A itself.2-C lies between A-B, then the best node to choose would be C3-C lies after B, then the best node to choose would be B 4-C lies on an path that is connected to a node between A-B, then the best node to choose would be that node that connects us to C.I guess that explains why it's fine to ignore if the edges > m, Because there's always a path with edges <= m and will produce better answers.Forgive the paint skills.EditYou can also consider if the AN+NB+BC > m, then just keep using the greatest price. It'll produce a correct answer.
•  » » » » » 2 years ago, # ^ |   0 Finally got this, thank you a lot!
•  » » » » » 2 years ago, # ^ |   0 Amazing explanation!
 » 2 years ago, # |   +13 Damn vovuh this may very well be the best round I ever took part in!!! The problems were extremly cool, especially problem E. Idk but the round just felt very good. Congratulations on doing such a good job!
 » 2 years ago, # |   +3 I have made a video which explains the approach used in D along with the code explanation. The link is here.
•  » » 2 years ago, # ^ |   0 nice explanation. Thanks
 » 2 years ago, # | ← Rev. 2 →   0 Can anyone give a another solution of F? Here have a O(N^4/32)，But it need bitset. I want to get a O(N^3) solution if anyone know. Thanks very much. I think a solution can be check for i from 1 to N and for each ans is a number is can be. At last it got the answer? but I can't prove it! Does anyone have a O(N^3) solution? thanks.
•  » » 2 years ago, # ^ |   0 I'll leave the analysis to you but pretty sure it is O(N^3) (I could be wrong) 77584222
•  » » 2 years ago, # ^ |   +5 I have a solution $O(n^2)$ https://codeforces.com/blog/entry/76306#comment-608280
 » 2 years ago, # |   0 My submission does not fail in any of the test cases I made.. Plz check if you could find one https://codeforces.com/contest/1343/submission/77567195
 » 2 years ago, # |   0 I don't understand when the ranking settlement will be completed. It seems that sometimes it will be settled immediately after the hack stage, sometimes it will take longer
 » 2 years ago, # |   +5 Oh my goodness, D was easy man. We just missed that during contest. Now, I tried to sketch and finally found it was just a basic prefix sum. Thanks, vovuh. This round was great and educative like the previous one.
 » 2 years ago, # |   +4 When do the ratings get published?
•  » » 2 years ago, # ^ |   +5 Whenever you are waiting for them to get updated, they never do.
 » 2 years ago, # |   0 are the servers down or what?? My submission is in queue for like 15 minutes
•  » » 2 years ago, # ^ |   +1 During the system test, all the participants' programmes were being tested so it's slow. Now the final standings have come out.
 » 2 years ago, # |   0 When will the rating changes be calculated?
 » 2 years ago, # |   +1 when the rankings will be updated??
•  » » 2 years ago, # ^ |   0 About 6 hours after system testing.
 » 2 years ago, # |   +47 It was a great contest. I really enjoyed the problems. Though, I have some suggestions for future Div. 3 rounds: Although I understand that multiple test case problems make tests stronger, they become quite bothering when it requires careful initialization of several arrays. Problem D and E are the examples, where we need to initialize multiple arrays until certain points (or dynamically allocate them), and things like memset(arr, 0, sizeof arr); have possibility to get TL. Of course, one can argue that being careful about these things is also a part of the problem, but this distracts participants from the core idea of the problem greatly and makes them waste a lot of time getting TL over and over again, not even realizing what went wrong with their code. Also, we can see that a lot of participants got AC with running time very close to the limit because of the initialization, and I'm sure that many others have failed to fit in time with very similar logic, possibly because of bad luck or just a little less optimization. My argue is that it will be better to either decrease the max number of TC, or decrease the max of $n$ when the time complexity isn't super important (like what I've done in one of my problems), especially when the contest is for beginners. I see problems like A in many 2A's and 3A's, where the implementation is super easy if you know how to simplify the mathematical expressions. But that 'simplification' is not very easy for beginners, as we can see that more people have solved B than A. I'd like to expect more straightforward problems for 3A instead of requiring mathematical knowledge or observation, because it's not the easiest subject for people who want to participate in a programming contest.
•  » » 2 years ago, # ^ |   0 I second this. Ideally, I think the easiest problem of Div2 or Div3 should not use concept higher (or harder to come up) than multiplication and division, let alone powers or GCD/LCM's. They are 8th/6th grade subject in Korean curriculum respectively. Not everyone who codes know that (believe me). As long as we are targeting them, it's encouraged to help them solve at least one problems in a contest, so they can figure out how things go on.I think this discussion is more relevant to be in here, but anyway.OTOH I'm not trying to blame the setter for anything: This is just my suggestion!
•  » » 2 years ago, # ^ |   -16 In the past few contests, after system testing, I often saw some programmes gotTime limit exceededorRuntime erroron the last test cases(for example,Time limit exceeded on test 84). Here are some examples:Hazyknight(who got 15th place) gotRuntime error on test 84.slime(who got 17th place) gotTime limit exceeded on test 33.
•  » » » 2 years ago, # ^ |   0 Why do I have lots of downvotes? What did I do wrong?
•  » » 2 years ago, # ^ |   +27 Global variables are bad habit in programming, so it's totally fine when people fail because of them.
•  » » » 2 years ago, # ^ |   0 I'm really curious to know as in why do they fail, if I have declared an array of size large enough that Im not going out of bounds , why would I be getting runtime error and how can I get TLE due to global variable. At times I have avoided TLE by using global variable instead of redeclaring array for each test case, but on rare occasions I get runtime error because of global variables, can you help me why does this exactly happens ?
 » 2 years ago, # | ← Rev. 2 →   0 My solutions matched with another account. Both are my account. I usually don't use using that account. Last contest I used both account, so the solutions matched exactly. I'm sorry. This won't happen again.
•  » » 2 years ago, # ^ |   0 What is the point of submitting from two accounts anyways? The score you get is time based. Faster the submission, greater the score.
•  » » » 2 years ago, # ^ |   0 But he can check if his solution will receive WA or Accepted if he uses two accounts
•  » » » » 2 years ago, # ^ |   0 Oh! damn didn't think of that. My bad.
•  » » 2 years ago, # ^ |   +1 You are not allowed to use multiple accounts in a contest.Read the rules and pay more attention next time.
•  » » » 2 years ago, # ^ |   0 I haven’t found the rules. Could you please provide me the link.
•  » » » » 2 years ago, # ^ |   0 Click on "register" for the next contest, you'll see this rule
•  » » 2 years ago, # ^ |   0 Logging in parallel of one person with two accounts should result in ban of both accounts. Then submitting the same solution twice, on both accounts within a contest does not happen without intention.