Good luck mate

So many contest during quarantine thank you vovuh.

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

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.

lol

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

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.

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.

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

get ready to be hacked!!

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 time

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

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

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

What was your Comment ??

Problem F

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

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.

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

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.

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!

Can you help me with my solution for problem E. https://mirror.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).

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://mirror.codeforces.com/contest/1343/submission/77572280

Thank you Shisuko and ameya! Understood both your solutions.

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://mirror.codeforces.com/contest/1343/submission/77536701

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.

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

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

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.

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)

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

yes they do, since no one solved F in competition

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

1. It contains exactly 1 unused element.

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

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

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

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.

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

i calculate three value as you, but i don't sort them, i use prefix for two last value ! 77542245

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?

IT was approximately Div 2.5

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

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

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

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 !

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.

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.

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