<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!

GL to all :D vovuh orz

Good luck mate

So many contest during quarantine thank you vovuh.

GLHF to all, xD

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?

He is coordinator for div3 rounds .While Pikmike is coordinator for educational rounds series!

oh... ok i see thanks

what is the difference in educational rounds vs DIV rounds?

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.

thank you Mr. AM_I_Learning

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.

By the way the original question doesn't talk of normal rounds. Thus I didn't talk of it!

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.

1

Happy Easter to everyone who celebrates!

SpoilerGood luck to all participants. Hoping for a great contest. Have Fun!

..

lol

When anyone else tries to make Div3 contests:

Vovuh:

lol

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

It means you will have an access to all solutions in a text form. You won't be limited to your room only.

Thanks for the clarification

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.

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.

I think only few contestants take participate in hacking.

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.

I have started making video solutions on mostly D based problems of every codeforces round. The videos can be found here.

will try to overcome CodeJam Round1B failure. LOL

We want more contest in this quarantine :(

..

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?

Why are there "6 or 7 (or 8)" problems? Am I allowed to know how many problems there are?

It is an almost-copy-pasted-part, so you cannot know the number of problems now.

Thanks!

Good Luck!! Happy Programming *_*

Good Luck to everyone!!

looking forward to increasing my rating ..as always.. :)

![ ]()

I think the problems will be more like implementation type! So, Be ready with your implementation skill @ 20.05!!

get ready to be hacked!!

I wish the penalty was less(like the contests in Atcoder).

I hope it will be as fun as the last round

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

Thanks vovuh!We hope more Div.3 contests for our beginner )

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???

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.

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.It would be great if you add contests more frequently like alternate days or one in 3 days. Happy Coding :)

This is vovuh's 37th Div-3 contest.

In my opinion it is 36th contest. It is named "Div3 round 36" in polygon.

You are right. Mike held one Div.3 contest without me (I don't remember its number)

Best wishes to everyone for the contest

this contest has become now as contest with most number of participants ...wow

good luck all

26K+ participants. Simply WoW.

27k+ Registrants for this contest!!!I hope this contest would be good unlike the previous one.

Wasn't the previous one(Codeforces Round #635 (Div. 1) and Codeforces Round #635 (Div. 2)) good?

I meant previous div3, not the last contest. The last contest was fun.

What was your Comment ??

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. :D

However... It wasn't such an important thing. The fun part is about downvoters who have never seen what I'd said. :))

Problem F

there is no Special Judge? why? Can anyone reply my questions? thanks very much.

Read the problem

why don't you use this ?

Such a difficult D.

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

what's your idea?

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.

i agree with you. my solution was same

Congrats!

I have used the same solution as yours. Look like there's a silly mistake.

Did (tried actually) same thing but got WA (Test 2) :D

This happended with me too

can u plz show via dry run it will be much helpful

"I'm 1300 elo and I did it"- very poor reference. Remember Gennady was once a 1500 too.

Maybe we all can become Gennady ;)

Training always works out. Sometimes you just need a bit more of it with some consistency.

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.

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.

Since you only have one query, isn't it much easier to only do offline prefix sums instead of the segment tree?

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?

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)

prefwherepref[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 toO(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.

https://codeforces.com/blog/entry/15729

You can read the partial sum section from this blog for more understanding!

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 helpfulWhat is test 2 of D? Please.

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

Link to code: https://codeforces.com/contest/1343/submission/77543873

Same solution here. WA on 29.

Try this:

6 6 1 4 6

1 1 1 1 5000 5000

1 2

2 3

3 4

4 5

5 6

2 6

answer is 5004?

6

What is the answer to this?

6

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.

Your name :D, I'm dreaming to learn dp too :(

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.

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.

the first thing, ans must be long long, not int

the 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 min

because 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

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!

Video Tutorials for D and E

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).

I did the same, and am getting WA on 320th case(Test case 4) stefdasca

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?

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 changes

2) 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.

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

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.

Thank you Shisuko and ameya! Understood both your solutions.

what is the greedy solution of D?

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) + k

Then 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

Did the same but got WA on test 2

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 — — <number of pairs such that you can't reach the sum by changing one number>. The former is already in the map, the later can be computed if you notice that for pair <x, y> (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.

Great round, guys!

We are going live now:

https://youtu.be/ppk9pXL9rR4

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.

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

You have to find any a $$$P=2^K-1$$$, starting from $$$K = 2$$$, that divides N. Then print $$$\frac{N}{P}$$$.

Can you explain why 2^k -1? I only know a(r^n -1)/r-1 to be the summation of geometric progression.

We have:

Now, take

xcommon and you end up withApply the summation of geometric series formula and you end up with $2^K-1$.

Oh wow I'm dumb. Really appreciate the explanation!

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)

Oh wow that's such a cool way, thanks so much!

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 n

You can find out more information about that in here

x+2x+4x+.....+2

^{k-1}= nusing sum of G.P, we get x = n/2

^{k}-1. So i looped starting from k=2,for any 'k' if 2^{k}-1 divides 'n' ,then break and print n/2

^{k}-1.My solution : 77509910

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.

Could not get what is wrong here and found only after competition ended:

Correcting one line makes solution pass all tests :)

[Deleted]

lol me too XD

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.

Can you please look into my BIT solution??Getting WA!! Link to Soln

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

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)

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 :(

in D sample test case 1 :_ part 3 :

8 76 1 1 7 6 3 4 6why is the answer 4 ??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.

you can always change some a[i] to have x is k+1 so the answer <= n/2

Yay. I solved the first 5 with a penalty of 141.

If only I was in competition, and not OOC...

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.

Do these numbers also include those participants who have rating above 1600?

yes they do, since no one solved F in competition

can anyone give a strong test case for problem D?

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.

It passed for me

i sent the answer of d in time and it not counted . can u help me in this .

What is the solution for F?

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.

77550191 $$$O(n^4/32)$$$ using bitset

77584382 $$$O(n^2)$$$ using the fact that only the last and maybe the first element appears once in the input

Can you explain your

`O(n^2)`

solution.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)$$$

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....

Sometimes when you refresh Div3 rounds during the hacking phase it removes unrated contestants, but after the hacking phase it will not be ambiguous

excuse me, problem E, is graph connected ?

obviously, when it's stated clearly that there is a path between any two pair of nodes.

oh, you're right lol :v

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.`

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.

How do I give input for hacking in problem A.

I tried giving like

4

1000

10

134

234

but says invalid input. Can someone explain why?

There needs to be a valid answer. There is no valid answer for 134

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.i calculate three value as you, but i don't sort them, i use prefix for two last value ! 77542245

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.

yes, right ! you can replace false and NULL with 0, it is shorter :v

Same idea. Just make it easier to understand. Code

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?

Any DP approach for problem D?

very good contest ,I love it but i think it is a bit difficult as a Div.3

IT was approximately Div 2.5

but I like it better, so we push the limits a bit more

77574862 This is giving wrong answer for fourth test case if someone could help. Thanks :).

Problem E.

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 C

Any 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

Nice Solution.

For problem A, what would the output be for n=29? Can we obtain a positive integer value for x?

"It is guaranteed that at least one solution exists."

For n = 29, I do not think there are any solutions.

Misread "district" as "distinct" in qE :/

Thought I was the only one. I was getting WA due to the distinct part lol

https://codeforces.com/contest/1343/submission/77576736

`wrong answer 39th numbers differ - expected: '1', found: '2'`

Is it any chance to see 39th test case?

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 !Thank you! It works: https://codeforces.com/contest/1343/submission/77630846

can anyone explain the approach for problem E??

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.

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?

CodeThanks :)

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?

There is no problem if they intersect, it still works. Vertex k can be same as B or C.

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.

nicely explained thanks :)

hmmm.....theeek....ab muh me lele

Any Suggestion , what can be wrong in my logic for question D .

Mycode D

This will TLE since you're doing T*200000. Note that T*N is passing the TL and not T*20000.

In editorial complexity is O(T*n*logn) ,it still passes

Yes.

Understand that T*N is different from T*200000.

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!

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...

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 link

77560252

Yessss Div3 I love it :D

How to solve problem F ????

http://codeforces.com/blog/entry/76306?#comment-608218

Can anyone explain the solution of D?

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 other

Call E[i] is the number pair have sum exacly i

Call 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] j<i also use 2

And if x in range [2,i] use 2 so x in [2,j] j>i also use 2

We 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/2

Which 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

Hey I used exactly the same approach but using upper bound and lower bound 77581160 can you see what Ive done wrong

I think upper and lower on X is wrong

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 R

For 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

with a[i]+a[n-i+1] you can't know with 1 replace it can be x or not

example 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

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)

Ok Done I got the error and got Accepted though after the contest

Can anyone explain the solution of D without the use of fenwick tree?

/*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]; }

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 here

Iterate 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

your solution is very helpful and understandable.thank you.

R should be max(a[i], a[n-i+1]) right?

Yes,edited it.

Me after doing C.

where is editorial

Wait 1-2 days.

One more case of cheating by using forged hacks. See: hack details

MikeMirzayanov 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.

Nothing new, it happens all the time.

Yes, but I haven't found any solutions like that. (or it's already hacked)

77581160 Can someone tell me what Ive done wrong in Problem D getting WA on tc 461 of test 2

The server was amazingly smooth today!

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.

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)

Thanks buddy.

n is sum of a geometrical series. Use formula for geometrical series apply the conditions. Hope you will get an idea what to do

Thanks buddy.

Yeah. It is a G.P.

You need to find (X,K) such that X * (power(2,K-1) — 1) = N

Start 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.

Thanks man..

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 Coding

import java.util.Scanner;

public class Prob1 {

}

Thanks man...

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 bex.Minimum possible sum for a

pairis2and maximum possible sum for a pair is2*k. Thenxmust be between2and2*kI calculate no of replacement for each

xbetween2 and 2*Kand finally take minimum of allx[i]Now the challenge is to calculate each x[i] in O(1) complexity

For each x[i] there will be 3 types of pair according to sum of pair

For some pair

sum of pairwill be exactlyx[i], for such pair no replacement is needed.If

x[i]is range(min of pair + 1 , max of pair + k)then thisx[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

arandar[i]indicate how many pair can reachichangingoneelement.Finally for each

x[i]I check how many pair reachx[i] making 0 change(t), 1 change(y) and 2 change(z)minimum of all

y+2*zis answer.MY Submission

[Deleted]

you have pairs:

let x=11 then:

result is 3 because there are only 3 replaces

5 3 8 5 6 3 8 6

3 changes and sum of all pairs is 11

Yes 5 3 8 5 6 3 8 6 One of the example with 3 changes.

Cheat and duplicate account alert- bit.ly_cfdiv23boostlive sachinganguly69

Solution for DReference

Problem 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)

ObservationsImplementation`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)Great explanation, Thank you :D

Thanks, appreciate it!

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?

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].

Thanx,mate!Now,i get it..BTW,great explanation.

Great solution, thanks for sharing!!

seriously thanks broo...greatest explaination so far

Can someone please see and tell why my code(attached below) was shown the wrong answer for the second question when submitted, Highly appreciated

import java.util.Scanner;

public class Prob2 {

}

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.

Thank you, it was silly of me

Is there someway to extract complete test case as I'm getting this in Problem Ewrong answer 320th numbers differ — expected: '4', found: '6'

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

Even the input file is not fully visible.

IMO D was difficult for a normal Div #3 contest, wasted a lot of time on D :(

Can someone tell whats the issue with my approach to Problem

E?Wrong answer on Test Case 41. 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 appreciatedI think shortest path is not optimal always.

Let a to b has 3 edges

Shortest path from b to c has 3 edges which is different from a to b

Total edge 6

Now consider there is another path from b to c which has 4 edges(not shortest) but two two of them common with a to b

Then total edge 3+1=4

So second one will be optimal although shortest path not taken.

Thanks it made everything crystal clear

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_coder

Not 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 solutions

77562772

77564410

77556321

77565949

77562595

77563089

77564679

77549578

77565649

He thought adding comments will save him77564027

77558019

77557813

how ?

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.

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.

good work!!

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.

MikeMirzayanov vovuh These people must get ban.

One more: ashwani45 and restfulCoder both have same submission.

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.

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!

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?

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 = 4

N -> B = 1

B -> N = 1

N -> C = 5

So total different numbers used = 4(A->N) + 1(N->B) + 5(N->C) = 10

But 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 C

3-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.

Finally got this, thank you a lot!

Amazing explanation!

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!

I have made a video which explains the approach used in D along with the code explanation. The link is here.

nice explanation. Thanks

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.

I'll leave the analysis to you but pretty sure it is O(N^3) (I could be wrong) 77584222

I have a solution $$$O(n^2)$$$ https://codeforces.com/blog/entry/76306#comment-608280

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

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

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.

When do the ratings get published?

Whenever you are waiting for them to get updated, they never do.

are the servers down or what?? My submission is in queue for like 15 minutes

During the system test, all the participants' programmes were being tested so it's slow. Now the final standings have come out.

When will the rating changes be calculated?

when the rankings will be updated??About 6 hours after system testing.

It was a great contest. I really enjoyed the problems. Though, I have some suggestions for future Div. 3 rounds:

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 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!

In the past few contests, after system testing, I often saw some programmes got

`Time limit exceeded`

or`Runtime error`

on the last test cases(for example,`Time limit exceeded on test 84`

). Here are some examples:In Codeforces Round #635 (Div. 1):

Hazyknight(who got 15th place) got

`Runtime error on test 84`

.Miracle03(who got 17th place) got

`Time limit exceeded on test 33`

.Why do I have lots of downvotes? What did I do wrong?

Global variables are bad habit in programming, so it's totally fine when people fail because of them.

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 ?

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.

What is the point of submitting from two accounts anyways? The score you get is time based. Faster the submission, greater the score.

But he can check if his solution will receive WA or Accepted if he uses two accounts

Oh! damn didn't think of that. My bad.

You are not allowed to use multiple accounts in a contest.

Read the rules and pay more attention next time.

I haven’t found the rules. Could you please provide me the link.

Click on "register" for the next contest, you'll see this rule