Hello Codeforces!

On Jan/14/2021 17:35 (Moscow time) Educational Codeforces Round 102 (Rated for Div. 2) will start.

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

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

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

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

Good luck to all the participants!

**Our friends at Harbour.Space also have a message for you:**

*Hey Codeforces and Happy New Year!*

*To kick off 2021, we want to introduce you to new opportunities!*

*Undoubtedly, Harbour.Space is always happy to see Codeforces participants among our students! Young talents who are eager to learn, challenge themselves, seek continuous development are our top priority.*

*That’s why we want to announce our amazing apprenticeship program.*

*Our mission is to spark positive impact cycles between promising young talent, the tech industry, and innovative educators. We continuously work on finding the perfect match between talent and companies.*

*Check out a success story from one of our first apprenticeship program students.*

*David is a UX/UI specialist from Georgia who received a full scholarship from venture capital fund, OneRagtime.*

*But there are plenty more apprenticeship opportunities coming in the fields of technology, entrepreneurship, and design. Interested? Keep in touch and follow us on LinkedIn for more fantastic opportunities.*

*Good luck on your round, and see you next time!*

*Harbour.Space University*

Congratulations to the winners:

Rank | Competitor | Problems Solved | Penalty |
---|---|---|---|

1 | jiangly | 7 | 201 |

2 | hank55663 | 7 | 210 |

3 | BigBag | 7 | 282 |

4 | Lawali | 7 | 283 |

5 | FluffyT | 7 | 306 |

Congratulations to the best hackers:

Rank | Competitor | Hack Count |
---|---|---|

1 | ariloc | 35:-1 |

2 | smax | 34:-9 |

3 | mrkarlo | 27:-5 |

4 | VTifand | 19 |

5 | BlueGagosipda | 21:-22 |

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

Problem | Competitor | Penalty |
---|---|---|

A | Geothermal | 0:01 |

B | Geothermal | 0:02 |

C | SSRS_ | 0:09 |

D | Alfalfa_w | 0:09 |

E | _FlyingColor_ | 0:16 |

F | Apsara | 0:40 |

G | tfg | 0:48 |

**UPD:** Editorial is out

Hope this time it will be real educational and not just "educational". Anyway good luck to everyone!

Don't forget to notice the usual start time!RIP SupaHotFire meme skils

it's ok that happens sometimes I'll try to make a better one soon

Congratulations to David! It is cool to see internship and job opportunities on CodeForces, even though they are not directly related to competitive programming. Many people start CP to improve programming skills in general, and Educational Contests work well to tie these fields together.

Congrats dude you managed to survive the downvote apocalypse going on in here :P

My first contest in CF ;)

good luck, bro! This is my first experience too :)

pikmike -> awoo

I liked Pikmike more, but awoo is also cute :)

Hoping for a round which is educational

Educational rounds have never failed to be educational bro, you don't need to worry about that :)

If we hack any solution, will we get any points in this contest?

No,you will not get any points but the hacked solution will count as wrong solution.

ohh, okay..

but there is an advantage, if u hacked some1 above u and if he is hacked he will be down u, u can go 1 step up and that's good

When people find out this guy IS pikmike, they are like: awoo

senzawa classicMy first contest drunk ! Less gooo !!!

How's life?

Well well I have gone from partying drunk to giving a contest drunk. So I guess depressing.

6.9/10 recommend.

nice C. Also i have no idea why my B, D got AC. Someone please hack them.

How the problems were educational ?

excuse me, i didn't get you?

They where not, at least not C and not D.

IITKWPCJ — Harder version of B by PraveenDhinwa

can you please provide the solution to it..i am getting WA. THANKS.

SpoilerUse euclidean gcd.

Solution.

D is segment tree isn't it?

Yes just keep track of the minimum and maximum prefix sum

can it be solved using MO's algorithm?

Maybe yes!!

I solved it using prefix and suffix arrays.

might be, but will be an overkill.

yes but my code is very large and weird. Waiting for another solution (if there exist one)

No segment tree, required, for both prefix and suffix store the maximum and minimum sums.

I didnt manage to finsih the code but it is :

Something along these linesI used a sparse table, though it could have been done by maintaining a minimum of prefix/suffix and a maximum of those two.

The trick is to avoid all possible off-by-one errors. I did by try'n'error for about an hour.

How to solve E? I tried using Dijkstra but it didn't pass

SpoilerUse Dijkstra + dp, a state in priority queue is represented by {cur_min_weight, $$$max edge taken$$$(true/false), $$$min edge taken(true/false)$$$, cur_node}.

Code for reference with comments.

imo it's a correct solution, can't say if it got hacked later.

I did something similar here But I kept getting WA on test 5 and now I check there's only 1 number that differs I don't know why

it's just showing that 1 number differs but actually there are more if you look carefully

Problem E solutionrepresent the cost as follows: let cost initially be sum of the all the edge weights

1.you can choose any one edge and subtract its weight from the cost

2.you can choose any one edge and add its weight to the

cost(independently from previous choice)

choosing the maximum edge in 1st choice and minimum edge in 2nd choice minimizes cost

now to find the answer let dist[i][j][k] be be the shortest path

from 1 to i such that you have performed step 1 iff j==1

and you have performed step 2 iff k==1

answer for vertex i is dist[i][1][1]

Why you can choose an arbitrary edge to add or subtract? Did I misunderstand the problem?

Its kind of greedy. Notice that you are looking for the

shortestpath between node 1 and all others. If you must take the cost of some edge twice, It is always best to take the smallest edge weight on the path. Similarly, If you are allowed to remove the cost of one edge on the path, it is always best to use the largest edge weight on the path. Dijkstra naturally takes this into account.Ah, I see, thanks for the explanation!

We can convert edge {u, v, w} to three edges {u, v, w, 0}, {u, v, 0, 1}, {u, v, 2 * w, 1}. The fourth element in the edge is use as minimal or as maximal edge. Introduce Dynamic Programming d[v][flag1][flag2] — minimal answer in vertex v, where flag1 = 1, when we used maximal edge, and where flag2 = 1, when we used minimal edge. Calcing the Dijkstra. Answer for vertex v is d[v][1][1]

How to solve C ??

It was too complicated for me to find and proof the solution and thus i brute forced and observed the pattern .

from i=1 to 2*k-n-1 you need to print i itself . After that you need to start from k . For example for n=5,k=5 : 1 2 3 4 5. for n=6 , k=5 : 1 2 3 5 4 . n=7,k=5 : 1 2 5 4 3 . n=8,k=5 : 1 5 4 3 2 . n=9,k=5 : 5 4 3 2 1.

It can be proved that the number of inverse of array B must be more than or equal to A regardless of any permutation. I separated array into two parts p[1],p[2],...p[k-(n-k)-1] and p[k-(n-k)],p[k-(n-k)+1],...,p[k],p[k-1],p[k-2],...,p[k-(n-k)]. If you take a look at the latter part, you can see that, for any pairs of i<j between k-(n-k) and k, there is always one p[i] appeared before p[j] and another p[i] appeared after p[j]. So the number of inverse in the latter part is always constant because any pairs of i and j have exactly 1 inverse. In the first part, the number of inverse in array A is 0 because it is arranged in ascending order and every elements of first part in array A in less than second part. So basically, we have to create any array that the first part is the same as A(or else inverse will be more than A) which is 1,2,3,...,k-(n-k)-1 and second part can be any permutation of k-(n-k),k-(n-k)+1,...,k. and lexicographically largest permutation is k,k-1,k-2,...,k-(n-k).

I'll try to explain with examples

Let's use $$$k = 5, n = 9$$$

Initially

$$$P$$$ = $$$1, 2, 3, 4, 5$$$

And $$$B$$$ = $$$1, 2, 3, 4, 5, 4, 3, 2, 1$$$

Notice when you swap $$$5$$$ with $$$4$$$ in $$$P$$$ It doesn't change the number of inversions (

because of the mapping b[i] = p[a[i]])$$$P$$$ becomes $$$1, 2, 3, 5, 4$$$

And $$$B$$$ becomes $$$1, 2, 3, 5, 4, 5, 3, 2, 1$$$

So you can continue swapping the largest number to the left as far as the number you want to swap with has a duplicate value on the right-hand side of $$$B$$$

Let me use a smaller example

You have $$$k = 3, n = 4$$$

$$$P$$$ = $$$1, 2, 3$$$

$$$B$$$ = $$$1, 2, 3, 2$$$

You can swap $$$3$$$ to the left once in $$$P$$$

$$$P$$$ becomes $$$1, 3, 2$$$

$$$B$$$ becomes $$$1, 3, 2, 3$$$

And you can't swap $$$3$$$ again

Because if you swap it left you will increase the number of inversions

In general

If you have a sequence $$$P$$$ = $$$1, 2, 3, 4, 6 ... k$$$ and $$$n$$$

Reversing the last $$$n - k + 1$$$ in values in $$$P$$$ is your solution and the number of inversions remains the same.

why don't we just stop after swapping the last two elements? Can you please explain that because I can't find a test case where just doing that will fail.

ya exactly. i did this as well. a: 1,2,3,4,5,...k-1,k,k-1,k-2,k-3..k-(n-k) b: 1,2,3,4,5,...k,k-1,k,k-2,k-3,...k-(n-k) the only difference is the 3 numbers in middle. in A they gave 1 inversion. in B also they are giving 1 inversion. and for the rest of k-3,k-4,k-5....2k-n,the number of digits greater before them remain same. so in all cases inversions remain same and b is lexicographically greater. and when n==k just print 1,2,3,....k-1,k. pls explain if anyone sees a fault in this

maybe the question wants us to create the greatest possible lexigraphic configuration and not just greater. haha! we were so close to the solution dude.

oh hmmmm. b is lexicographically maximum. i thought amongst a and b, b must be greater. cool my fault then. thanks mate

Maybe this will help

Full visualization for $$$n = 7$$$, $$$k = 4$$$

$$$P$$$ = $$$1, 2, 3, 4$$$

$$$B$$$ = $$$1, 2, 3, 4, 3, 2, 1$$$

Swap $$$4$$$ and $$$3$$$ in $$$P$$$

$$$P$$$ = $$$1, 2, 4, 3$$$

$$$B$$$ = $$$1, 2, 4, 3, 4, 2, 1$$$

Swap $$$4$$$ and $$$2$$$ in $$$P$$$

$$$P$$$ = $$$1, 4, 2, 3$$$

$$$B$$$ = $$$1, 4, 2, 3, 2, 4, 1$$$

Swap $$$4$$$ and $$$1$$$ in $$$P$$$

$$$P$$$ = $$$4, 1, 2, 3$$$

$$$B$$$ = $$$4, 1, 2, 3, 2, 1, 4$$$

Swap $$$3$$$ and $$$2$$$ in $$$P$$$

$$$P$$$ = $$$4, 1, 3, 2$$$

$$$B$$$ = $$$4, 1, 3, 2, 3, 1, 4$$$

Swap $$$3$$$ and $$$1$$$ in $$$P$$$

$$$P$$$ = $$$4, 3, 1, 2$$$

$$$B$$$ = $$$4, 3, 1, 2, 1, 3, 4$$$

Swap $$$2$$$ and $$$1$$$ in $$$P$$$

$$$P$$$ = $$$4, 3, 2, 1$$$

$$$B$$$ = $$$4, 3, 2, 1, 2, 3, 4$$$

So the final value for $$$P$$$ is $$$4, 3, 2, 1$$$

Notice the inversion never increases or decreasesI wish I could upvote you twice. No youtube videos really helped but your comment did. Thanks Sir. Now I can sleep well ;-)

Is it possible to solve D in linear time? Only issue I had was how to find minimum and maximum for suffix. For prefix it's easy.

Lol! reverse the original array.

if you found the solution for prefix ,why you didnt reverse the array and did the same thing?

You don't need to find maximum/minimum prefix of suffix. Instead, you can calculate sum in two segments and substract minimum/maximum suffix, which can be calculated similar to minimum/maximum prefix.

first traverse from front then from back, keeping track of current position and max. and min. it has reached.

Could someone please explain why the answer for vertex 7 in test case 3, problem E is 3?

You can use an edge more than once

Thanks man, i wasn't able to figure it out

For those who still have this confusion, the optimal path for 7 is-

1->7->4->7

How to solve D, anyone can explain?, i got run time exceed

I tried square root decomposition and was expecting it to work But got TLE because I use Python RIP. Maybe it should work in CPP O(M root(N))

This contest made me realize that I should maintain a segment tree library.

so true :))

how to solve D and F ? Anyone explain.

D can be solved by range minimum & maximum queries in Segment tree.

Or just by calculating prefix/suffix maximums/minimums, no need for segtree.

can you explain a bit more ?

UPD: got it.InANutshell What are u trying to store there in seg tree?

I did storing the a pair of values, which is minimum and maximum of the prefix sums of all operations of that segment.

I did D by maintaining prefix and suffix minimums/maximums without segment trees. Just eliminate the effect of l to r by adding the cumulative sum to the min and max of the remaining suffix array. The answer is total_max — total_min + 1 Total_min and total_max are overall min and max(from prefix array and suffix array before l and after r respectively) after eliminating the effect of the segment l to r

Thanks, I understood it now.

I was thinking of Adding the cumulative sum to all elements in suffix array and then to eliminate duplicate elements (which was not even needed...)

Can you explain the logic behind adding the cumulative sum to the min and max of suffix array ? I cant understand it very well.

Hey, so you would add the cumulative sum to nullify the effect of the segment (l to r), instead if adding it to the whole suffix array, you can only add it to min and max because the change is uniform. You only need min and max from the prefix and suffix because all the points between them will be travelled automatically (because the step size is only 1)

PS — you can imagine it like a continuous graph, in which you remove a segment in between and join the ends if the other 2 segments, you have to bring the right end up or down to meet the left end ( so you add the cumulative sum * -1 which can be positive or negative to negate the effect)

Idk if this is helpful, not so good at explaining stuff

We need to observe one thing that if we want to know the distinct numbers possible in some ++--+-+++... string then the no of distinct possibilities are mx — mn + 1. (mx is max no possible and mn is min no possible).

consider 4 vectors pre_ma, pre_mi, suff_ma, suff_mi

while calculating these vectors we consider that value of x starts from 0pre_mi[i] — what is the min value that we came across until index i if we started from index 1.

pre_ma[i] — what is the max value that we came across until index i if we started from index 1.

suff_mi[i] — what is the min value that we came across until index N if we started from index i

suff_ma[i] — what is the max value that we came across until index N if we started from index i.

Now for each query, we have to consider 1 to l-1 and r+1 to N as combined string and do these operations. Instead we find the max and min possible values differently for both of these prefix and suffix strings.

So, for prefix string since the value of x starts from 0 we can directly consider pre_mi[l-1] and pre_ma[l-1], but for this suffix string the value of x doesn't start from 0, (But we have stored the vectors if the value of x starts from 0), but this suffix string starts at some value X (Here X denotes the sum of prefix string). so we have to consider (X + suff_mi[r+1] as the min value occured in this suffix string) , same goes for maximum in suffix string.

Final answer would be max(suffix max val , prefix max val) — min(prefix min val, suffix min val) + 1.

Link to my code

thanks learned a new way to calculate suffix maximum...) it was helpful

Hi, I encountered some strange errors while submitting a solution in Java for Problem D in the Codeforces Educational Round 102,

The code works perfectly in my local system, it even works correctly in an online Java Compiler(OnlineGDB). However, it was unable to read strings correctly in the Problem D.

My Submission: 104337369

Could someone please guide why this is happening..

can i know the aproach for problem div2A

traverse the input array, if there is no number greater than d, print yes. Now sort the array. If the sum of first two numbers is less than or equal to d, then it means that any number which is bigger than d can be replaced by the sum of these two numbers. But if their sum is not less than or equal to d, then we can be sure that no other sum in this array will be smaller than this. therefore, after sorting

if(a[0]+a[1]<=d) print yes else print no

Thank you. I could only solve first case.never thought of sorting the input array.

Editorial, please

$$$D$$$ was easier than $$$C$$$ at least to me.

Same for me, I find it hard to beleave that so much people solved C. It looks kind of unsolvable to me, I still did not read any near-to-understandable explanation.

The only thing you need to notice is that in the segment $$$[k - (n - k), ..., k, ..., k - (n - k)]$$$ no matter what permutation you choose the number of inversions in this segment will not change (and will equal $$$(n - k)^2$$$ but that's extra info irrelevant here).

So you can't afford any other inversion hence the head of your list must be $$$[1, 2, 3, ..., k - (n - k) - 1]$$$. Now to get the maximum lexicographical sequence you should transform $$$[k - (n - k), ..., k, ..., k - (n - k)]$$$ to $$$[k, k - 1 ..., k - (n - k), ..., k - 1, k]$$$ and to do so we use the permutation $$$[1, 2, 3, ... k - (n - k ) - 1, k, k - 1, k - 2, ..., k - (n - k)]$$$

How do you prove that no matter what permutation you choose the number of inversions in this segment will not change and will equal $$$(n−k)^2$$$ ?

Thats the part I did understand. This is, because if you change two (or more) numbers to each other, you allways change two of such pairs.

As an example, that part of the list looks like:

`3 4 5 4 3`

So, no matter which digits are exchanged to each other, it allways happend twice in respect to the positions, and hence number of inversions.So if $$$b = [k - (n - k), ..., k, ..., k - (n - k)]$$$ and $$$p = n - k$$$, $$$size(b) = 2p+1$$$.

By symmetry,

Then,

Finally,

might be because of massive cheating again . From coding perspective it was only 2-3 line solution and thus it was easy to spread and fool the moss .

To be honest it was way difficult than D and very incomprehensible.

Well, now, like 12 hours later, I think I understood the problem. Maybe I just needed a bit longer than other people.

seeing your current and maximum rating it's hard to digest you couldn't solve it and lot of people did . Something fishy going on these days.

Not so sure, it's easy to guess the solution to the problem. In contest, you don't have to understand why it works.

Then i would get WA on pretest 2

I guessed the solution at the beginning, tested on some small test cases, gained some intuition to why it works, and YOLOed. In contest, many people don't do the second part, much less the third. When you have no other ideas, sometimes its fine.

I'm not saying there was no cheating or anything, just saying that I don't think the solve count is too suspicious — you kinda see the pattern when you look at enough test cases.

It was quite easy to analyze some cases with backtracking and then observe the pattern. Maybe this was the reason of so many AC's.

Can you explain how did you do D?

I have explained here.

How to solve problem F ?

Build a flow network as follows: let's create a source $$$s$$$, a sink $$$t$$$, and a vertex for each element. We will try to model the problem as the minimum cut in this network.

For every element $$$i$$$, there are several elements $$$j$$$ to the left of it that should be taken if we take it. Let's add a directed edge with infinite capacity from $$$i$$$ to all such elements. For elements will positive $$$b_i$$$, add a directed edge from $$$s$$$ to them with capacity equal to $$$b_i$$$. For elements will negative $$$b_i$$$, add a directed edge from $$$i$$$ to $$$t$$$ with capacity $$$|b_i|$$$.

What does an $$$s$$$-$$$t$$$ cut in this network represent? Let's say that all elements in the same part with $$$s$$$ are taken into the answer, and all other elements are ignored. Let's say that we have some $$$i$$$ that is taken into answer and depends on some element $$$j$$$ that is not taken. Then there is an infinite-capacity edge from $$$j$$$ to $$$i$$$, and it goes through the cut, so the value of the cut is infinite (and we are searching for a minimum cut, so this cannot happen). For each positive $$$b_i$$$, if $$$i$$$ is not taken, the value of the cut increases by $$$b_i$$$ (since the edge from $$$s$$$ belongs to the cut), and for each negative $$$b_i$$$, if $$$i$$$ is taken, the edge from $$$i$$$ to $$$t$$$ belongs to the cut, so $$$|b_i|$$$ is added to the value of the cut. So, the minimum cut actually minimizes the sum of positive $$$b_i$$$ that are not taken, minus the sum of negative $$$b_i$$$ that are taken, so it gives us the optimal answer.

There's one issue though. This network can easily reach $$$O(n^2)$$$ edges, and that's too much. To reduce the number of edges to something like $$$9n$$$, for each $$$i$$$, consider all divisors of $$$a_i$$$ (including $$$a_i$$$ itself) to the left of it. If there are several equal divisors, then taking the closest of them ensures that we take all other divisors into the answer, so actually, for each divisor of $$$a_i$$$, we need to consider only the closest occurrence of this divisor to the left of $$$i$$$, and add an infinite edge from it to $$$i$$$.

This might be a dumb question (I'm pretty new to flows), but what would be the complexity of this algorithm? Using Dinic's, wouldn't this be $$$\mathcal O(V^2E)$$$, and with $$$V = 3000$$$ and $$$E \approx 9 \cdot 3000$$$, shouldn't this TLE? Or there also just might be some property about this flow graph that makes Dinic faster that I'm not aware of.

The distinctive feature of many flow problems is that it is either very hard or even impossible to construct a testcase on which an algorithm performs anywhere near its worst-case complexity.

Ah, that makes sense. I guess if a flow solution exists, it's always worth to try it and see if it passes. Thanks for the reply!

Yes, I've also considered this problem. In fact, the model solution is written with the implementation of maxflow in $$$O(VE \log F)$$$ (Dinic with scaling), so asymptotically it should be fine. But my implementation of regular Dinic also passes all of my test cases, I haven't found a test case which it gets TL on.

So, actually, we have a 100% working solution, but we guess that some asymptotically bad solutions might pass.

In this problem a path saturates a source edge or a sink edge always because the other edges have infinite capacity so the actual complexity is O(V paths) * O(E for finding a path) for any max flow algorithm.

Suspicious submission for hacks I think the hacker made an alternate account for hacking this.

Why would anyone do this? Afaik you get nothing for hacking in this contest.

Also no one gets anything by pointing this hack...

and I will get nothing by this comment.

You got an upvote by me :)

:(

Whoever concocted this is genius. They've practically lined themselves up to be caught.

https://codeforces.com/contest/1473/status/A?order=BY_CONSUMED_TIME_DESC

VIDEOTUTORIAL FOR PROBLEM A AND B WITH DETAILED EXPLANATION . I ALSO TRIED TO EXPLAIN LINE BY LINE CODE . I HOPE YOU GUYS WILL ENJOY THE VIDEO LINK PROBLEM B :https://www.youtube.com/watch?v=H3qBEDYwwX4 LINK PROBLEM A :https://www.youtube.com/watch?v=YjC6CcxYxo8

Getting downvotes due to CAPS :v

In problem $$$C$$$, It's never said that $$$b$$$ has to be the sequence with the least number of inversions. It can be found that number of inversions of $$$a$$$ is $$$(n - k)^2$$$ and the sequence $$$b$$$ builds off the permutation $$$1,2,..,k,k-1$$$ also has the equal number of inversions as $$$a$$$ and it should suffice to be the solution when $$$n > k$$$.

True, but it is said that

Also note that

I think you missed the requirement where B must be lexicographically maximum.

It hurts!roz adhoc problems karke man nahi bharta kya patang udao gilli danda khelo! come out of this artificial life.

Problem C and D video solutions — solution

Unable to understand C even after looking the to the test cases that didn't passed. Anyone here could you please help me with proper understanding of C.

I did same mistake with you during contest.

Try to solve this testcase by your hand

`1 7 4`

Go to secondthrad's youtube channel , he has explained that problem quiet nicely.

Hey, I have a doubt regarding problem C.Is the number of inversions in 1 2 3 2 1 is same as that in 3 2 1 2 3?

Yes, 4 in both cases.

Thanks

Yes. It's 4 in both.

Thanks

No.1 2 3 2 1 have 3 inversions and 3 2 1 2 3 have 4 inversions

Calculate it again.

oh,sorry bro! (2,1) appears two times.I calculated it only once..sorry

hey someone please help me to debugging my code i got WA in test case 8 of problem E;

Spoiler## include<bits/stdc++.h>

using namespace std;

using ll = long long;

## define int ll

const int mxN = 3e5 + 20;

mt19937_64 gen(chrono::system_clock::now().time_since_epoch().count());

const int mod = 1e9 + 7;

const int N = 1e6 + 10;

int32_t main() {

}

Your bfs solution is incorrect because edges in this task are weighted and that's why bfs won't work in this case. Try to use Dijkstra algorithm.

https://codeforces.com/contest/1473/submission/104345925 can someone explain what's happening here?

I think this violates Rule #6 by destabilizing the checking system (trying to increase the queue size by increasing the running time)

I have a big question could anyone tell me in Problem E how in the third sample the minimum weight to vertex 5 is 7? I can't find a path with lower than 8

I got it no problem anymore:/

Hey all, if you missed the post-contest stream that I did on https://www.twitch.tv/stevenkplus, here is the youtube recording: https://youtu.be/3o1Na9Qnaio.

Will edit this comment with links to my submissions (containing solution notes) once I perform the submission process :)

Problem E is really cool! I don't know why I didn't consider traversing an edge twice.

For anyone stuck in D, https://youtu.be/mMFkvyeRFQY

People using Segment tree and MO's algo in problem D

Nah, seg tree is really close to the linear solution anyway.

Does anyone have any idea what's the mistake in all the solns of E that were hacked?

if(no.a>dist[no.b.a][no.b.b])continue;

it the pair in the priority_queue has more distance than the shortest

path found till now then don't iterate further.Codes which didn't

add this condition got hacked(TLE).weak pretests

I got lucky for problem C. I somehow looked at the testcases and figured out what to do. This has happened to me in previous contest too . xd

can someone instead of flexing that it can be solved by prefix/suffix sum explain how to solve D . I know prefix,suffix but i don't know how to use that in this problem.

create the following arrays :

MaxTillHere[] -> stores the max value upto a particular index MinTillHere[] -> stores the min value upto a particular index

then, using backward traversal create the following array :

MaxFromHere[] -> stores the max increase we'll get after a particular index MinFromHere[] -> stores the max decrease we'll get after a particular index

now the answer is simple, for each query (l, r) : int max = MaxTillHere[l — 1] + val[i] + MaxFromHere[r] int min = MinTillHere[l — 1] + val[i] + MinFromHere[r]

ans = max — min + 1

I hope my answer was clear. Some index value might be wrong here, but i hope you've got the gyst of the solution!

you haven't solved this problem and telling wrong/incomplete solution .From next time solve it first. It's sad i can't take my upvote back.

Here. I solved it just for you. Problem D solution

Well you can downvote this one, if it makes you feel any better. Next time, either solve it yourself or don't bitch about people who try to help you.

When will the rating be updated for this round.

Educational contest take too much time for ratings updation and editorial normally

Video Tutorial for problem A,B and D link of problem D : https://www.youtube.com/watch?v=botAQ-AZNOQ

link of problem B : https://www.youtube.com/watch?v=H3qBEDYwwX4

link of problem A : https://www.youtube.com/watch?v=YjC6CcxYxo8&t=263s

Hope you guys will enjoy and understand the intution behind the solutions !!!

GREAT EXPLANATION BROTHER !!!

why did they temporarily roll the rating changes back ??

I guess, because of the cheating issues.

That is done after every contest. Right?

why i am getting negative points? i thought in 10 min solved no penalty

Points are counted depending on other participants, most likely someone solved more or as many problems as you, but at the same time was the lowest rating

what if i register and 0 submission solved 0 problem i am get negative point?

if you are registered, but you have not sent anything for the entire competition, you will not receive or lose anything

is it rated for the participants with rating greater or equal to 2100? i fount some people who geater than 2100 is rated

I'm one of them :(

My rating was above 2100 before taking this contest, but it was changed because of it. Could anyone tell me why?

I think it was applied as a rating when "Codeforces Round #695 (Div. 2)" is temporarily rolled back. At that time, our rating was lower than 2100.

Hello Codeforces!

I basically got a message that I cheated in this round, and that my rating won't change.

The message I gotAttention!

Your solution 104288640 for the problem 1473A significantly coincides with solutions johnJ21450/104286721, babu_rao/104286748, NoT_BFS/104287024, 0inbinary/104287048, Voltsky/104287220, fan_of_beyblade/104287230, hacker_prime3/104287348, vk99/104287446, gfrty11/104287712, error_0100/104287747, dex2132/104287930, WHgom22/104288640, sandkiakh/104288967, highRank/104289469, mdvirus/104291072, ksushil57/104292022, akash_ramjyothi/104292173, accelerator_9/104292448, mcbcac/104293903, TusharSD15525/104295317, cyberpython/104295924, kgm.kg.m2722/104298166, __gulshangodbole/104300172, WaTeRhEaD/104303632, sandx_123/104325936, TThanoSS/104328674, Durgesh_7979/104331920. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

I am writing this comment to inform to the codeforces headquaters that the plagarism check system has made a misjudgement.

I was pretty shocked to see this message and other people's codes.

They

weresimilar, and some were even theexactsame.I found no code that was

exactlythe same to my code, but some were astonishingly similar.Problem A in this contest was a very simple problem, that had a very simple solution, so there could be some coincidences in people's code.

Also, I confirm that I don't even have a telegram account and have never used Ideone or other online judjes in this contest.

I understand codeforces' work to catch cheaters to make codeforces a better community.

However, for the reasons I stated above, I want to get my rating back.

Thank you! :)

+) I am curious about when, and how I will get my rating back. Will the headquaters contact me via email or codeforces talk?

I took part in this unrated contest (for Div. 1) and found my rating changed afterwards. Why? Mistake?

Same thing happened with me, please comment if you find a solution to this

I pm'd to Mike and I'm waiting for him to reply.

Where is Editorial? Also Can you make problem statement clear? Problem C was so much confusing. I understood it only after reading examples.

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).I dont usually comment because of my low rating which gathers me downvotes...but the broad range of topics tested in this round, be it the use of data structures or algorithms in this round is appreciated. It didn't seem too adhoc like other rounds involved some known concepts to a perfect extent and again the breadth of topics of the questions- just amazing! Kudos to the authors of the contest. Well done! Editorial was fast, question statement lengths and test strengths were optimal. In short, one of the best contests I have ever participated on Codeforces.

Love the DP, LOL :P