By awoo, history, 3 months ago, translation,

Hello Codeforces!

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
242 successful hacks and 872 unsuccessful hacks were made in total!

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

• +292

 » 3 months ago, # |   -73 Hope this time it will be real educational and not just "educational". Anyway good luck to everyone!
 » 3 months ago, # |   -73 It's 102. It's means we loved Educational round.
 » 3 months ago, # |   -80 Don't forget to notice the usual start time!
•  » » 3 months ago, # ^ |   -80 and you don't forget to take part. lol
 » 3 months ago, # |   0
•  » » 3 months ago, # ^ |   -31 RIP SupaHotFire meme skils
•  » » » 3 months ago, # ^ |   -31 Nah, he will just be like this
•  » » » 3 months ago, # ^ |   +13 it's ok that happens sometimes I'll try to make a better one soon
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   -11 yup no
 » 3 months ago, # |   +65 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.
•  » » 3 months ago, # ^ |   +45 Congrats dude you managed to survive the downvote apocalypse going on in here :P
 » 3 months ago, # |   -16 Hoping for strong pretests
 » 3 months ago, # |   -20 My first contest in CF ;)
•  » » 3 months ago, # ^ |   +10 good luck, bro! This is my first experience too :)
 » 3 months ago, # |   +24 pikmike -> awoo
•  » » 3 months ago, # ^ |   +99
•  » » » 3 months ago, # ^ | ← Rev. 3 →   0 So adorable.........looks like it will be good round.
•  » » » 3 months ago, # ^ |   0 I liked Pikmike more, but awoo is also cute :)
 » 3 months ago, # |   -8 Hoping for a round which is educational
•  » » 3 months ago, # ^ |   +5 Educational rounds have never failed to be educational bro, you don't need to worry about that :)
•  » » 3 months ago, # ^ |   0 good luck, Donald
 » 3 months ago, # |   -40 Educational round means uneducational round.
 » 3 months ago, # |   +1 If we hack any solution, will we get any points in this contest?
•  » » 3 months ago, # ^ |   +6 No,you will not get any points but the hacked solution will count as wrong solution.
•  » » » 3 months ago, # ^ |   0 ohh, okay..
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +1 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
•  » » » » 3 months ago, # ^ |   0 the system testing already do that
•  » » » » » 3 months ago, # ^ | ← Rev. 3 →   0 As I know, in such rounds the system tests are made by the own tests and hacks, and if you hack a person, the system test will just check your test on others solution, and your hack may make other solutions wa too. To sum up, it may increase your rating unless you hack yourself(:
 » 3 months ago, # |   -16 how to check time complexity of a parogram?
•  » » 3 months ago, # ^ |   0
•  » » » 3 months ago, # ^ |   -6 link is not working
 » 3 months ago, # |   -23 Educational Codeforces Round 102[Rated for Div.2]
 » 3 months ago, # |   +14 When people find out this guy IS pikmike, they are like: awoo
•  » » 3 months ago, # ^ |   +39 senzawa classic
 » 3 months ago, # |   +41 My first contest drunk ! Less gooo !!!
•  » » 3 months ago, # ^ |   +5 How's life?
•  » » » 3 months ago, # ^ |   +15 Well well I have gone from partying drunk to giving a contest drunk. So I guess depressing.
•  » » 3 months ago, # ^ |   +52 6.9/10 recommend.
 » 3 months ago, # |   -15 wtf getting wrong ans in tc 3 in b... :( ..i am gonna die
•  » » 3 months ago, # ^ |   0 same got it 2 times , i even stress-tested my code.... :(
 » 3 months ago, # | ← Rev. 2 →   0 nice C. Also i have no idea why my B, D got AC. Someone please hack them.
•  » » 3 months ago, # ^ |   +4 How the problems were educational ?
•  » » » 3 months ago, # ^ |   0 excuse me, i didn't get you?
•  » » » 3 months ago, # ^ |   -13 They where not, at least not C and not D.
 » 3 months ago, # |   +2 IITKWPCJ — Harder version of B by PraveenDhinwa
•  » » 3 months ago, # ^ |   0 can you please provide the solution to it..i am getting WA. THANKS.
•  » » » 3 months ago, # ^ |   0 SpoilerUse euclidean gcd.
 » 3 months ago, # |   0 D is segment tree isn't it?
•  » » 3 months ago, # ^ |   +3 Yes just keep track of the minimum and maximum prefix sum
•  » » » 3 months ago, # ^ |   +1 can it be solved using MO's algorithm?
•  » » » » 3 months ago, # ^ |   0 Maybe yes!!
•  » » 3 months ago, # ^ |   +13 I solved it using prefix and suffix arrays.
•  » » 3 months ago, # ^ |   0 might be, but will be an overkill.
•  » » 3 months ago, # ^ |   0 yes but my code is very large and weird. Waiting for another solution (if there exist one)
•  » » 3 months ago, # ^ |   0 No segment tree, required, for both prefix and suffix store the maximum and minimum sums.
•  » » 3 months ago, # ^ |   +2 I didnt manage to finsih the code but it is : Something along these lines//Think simple yet elegant. #include using namespace std; #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ll long long #define all(v) v.begin(),v.end() #define ff first #define ss second #define pb push_back #define mp make_pair #define pi pair #define REP(i,n) for(int i=0;i> t; while(t--){ cin >> n >> m; string s; cin >> s; set hsh; vector p(n),s(n); hsh.insert(0); int val=0; for(i=0;i> l >> r; --l,--r; cout<
•  » » 3 months ago, # ^ |   0 I used a sparse table, though it could have been done by maintaining a minimum of prefix/suffix and a maximum of those two.
•  » » 3 months ago, # ^ |   +1 The trick is to avoid all possible off-by-one errors. I did by try'n'error for about an hour.
•  » » » 3 months ago, # ^ |   0 Me too, didn't work out in the end.
 » 3 months ago, # |   +19 How to solve E? I tried using Dijkstra but it didn't pass
•  » » 3 months ago, # ^ |   +8 СпойлерUse 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.
•  » » » 3 months ago, # ^ |   0 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
•  » » » » 3 months ago, # ^ |   0 it's just showing that 1 number differs but actually there are more if you look carefully
•  » » 3 months ago, # ^ |   +86 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 pathfrom 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]
•  » » » 3 months ago, # ^ |   +3 Why you can choose an arbitrary edge to add or subtract? Did I misunderstand the problem?
•  » » » » 3 months ago, # ^ |   +21 Its kind of greedy. Notice that you are looking for the shortest path 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.
•  » » » » » 3 months ago, # ^ |   +5 Ah, I see, thanks for the explanation!
•  » » 3 months ago, # ^ |   0 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]
 » 3 months ago, # |   +4 How to solve C ??
•  » » 3 months ago, # ^ | ← Rev. 3 →   +6 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.
•  » » 3 months ago, # ^ |   +4 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
•  » » 3 months ago, # ^ | ← Rev. 9 →   +6 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.
•  » » » 3 months ago, # ^ |   0 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.
•  » » » » 3 months ago, # ^ |   0 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
•  » » » » » 3 months ago, # ^ |   0 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.
•  » » » » » » 3 months ago, # ^ |   0 oh hmmmm. b is lexicographically maximum. i thought amongst a and b, b must be greater. cool my fault then. thanks mate
•  » » » » » » » 3 months ago, # ^ |   0 how did everyone think the same ;)
•  » » » » 3 months ago, # ^ | ← Rev. 4 →   +3 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 decreases
•  » » » 3 months ago, # ^ |   +3 I wish I could upvote you twice. No youtube videos really helped but your comment did. Thanks Sir. Now I can sleep well ;-)
 » 3 months ago, # |   0 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.
•  » » 3 months ago, # ^ |   +4 Lol! reverse the original array.
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 if you found the solution for prefix ,why you didnt reverse the array and did the same thing?
•  » » 3 months ago, # ^ |   +5 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.
•  » » 3 months ago, # ^ |   +3 first traverse from front then from back, keeping track of current position and max. and min. it has reached.
 » 3 months ago, # |   0 Could someone please explain why the answer for vertex 7 in test case 3, problem E is 3?
•  » » 3 months ago, # ^ |   +14 You can use an edge more than once
•  » » » 3 months ago, # ^ |   +6 Thanks man, i wasn't able to figure it outFor those who still have this confusion, the optimal path for 7 is-1->7->4->7
 » 3 months ago, # |   0 How to solve D, anyone can explain?, i got run time exceed
•  » » 3 months ago, # ^ |   0 I think segment trees
•  » » 3 months ago, # ^ |   0 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))
•  » » » 3 months ago, # ^ |   0 How to do that? By the way
 » 3 months ago, # |   +3 This contest made me realize that I should maintain a segment tree library.
•  » » 3 months ago, # ^ |   0 so true :))
 » 3 months ago, # |   0 how to solve D and F ? Anyone explain.
•  » » 3 months ago, # ^ |   0 D can be solved by range minimum & maximum queries in Segment tree.
•  » » » 3 months ago, # ^ |   +35 Or just by calculating prefix/suffix maximums/minimums, no need for segtree.
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 can you explain a bit more ?UPD : got it.
•  » » » » » 3 months ago, # ^ |   0 Can you please explain using prefix /suffix sums in detail?
•  » » » 3 months ago, # ^ |   0 InANutshell What are u trying to store there in seg tree?
•  » » » » 3 months ago, # ^ |   0 I did storing the a pair of values, which is minimum and maximum of the prefix sums of all operations of that segment.
•  » » 3 months ago, # ^ |   +4 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
•  » » » 3 months ago, # ^ |   0 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...)
•  » » » 3 months ago, # ^ |   0 Can you explain the logic behind adding the cumulative sum to the min and max of suffix array ? I cant understand it very well.
•  » » » » 3 months ago, # ^ |   +2 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
•  » » » » » 3 months ago, # ^ |   0 Really liked your idea of visualizing it ..
•  » » » » 3 months ago, # ^ |   +3 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 isuff_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
•  » » » » » 3 months ago, # ^ |   +1 thanks learned a new way to calculate suffix maximum...) it was helpful
 » 3 months ago, # |   0 I noticed the typo in D but thought that it isn't a typo and wasted half an hour. Thought of segment trees upon seeing the problem statement and jumped to D from B. So in short I didn't solve D and got a huge penalty for C. FML
 » 3 months ago, # |   +6 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: 104337369Could someone please guide why this is happening..
 » 3 months ago, # |   0 can i know the aproach for problem div2A
•  » » 3 months ago, # ^ |   +4 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 sortingif(a[0]+a[1]<=d) print yes else print no
•  » » » 3 months ago, # ^ |   +1 Thank you. I could only solve first case.never thought of sorting the input array.
•  » » » 3 months ago, # ^ |   0 Yes, same logic
 » 3 months ago, # |   +9 Editorial, please
 » 3 months ago, # |   +14 $D$ was easier than $C$ at least to me.
•  » » 3 months ago, # ^ |   +6 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.
•  » » » 3 months ago, # ^ |   +15 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)]$
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 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$ ?
•  » » » » » 3 months ago, # ^ |   0 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.
•  » » » » 3 months ago, # ^ |   +3 So if $b = [k - (n - k), ..., k, ..., k - (n - k)]$ and $p = n - k$, $size(b) = 2p+1$.By symmetry, $inv(b) = \# \left\{ ib_j \right\} = \# \left\{ i •  » » » 3 months ago, # ^ | ← Rev. 2 → 0 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. •  » » » » 3 months ago, # ^ | 0 Well, now, like 12 hours later, I think I understood the problem. Maybe I just needed a bit longer than other people. •  » » » » » 3 months ago, # ^ | 0 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. •  » » » » » » 3 months ago, # ^ | +1 Not so sure, it's easy to guess the solution to the problem. In contest, you don't have to understand why it works. •  » » » » » » » 3 months ago, # ^ | 0 In contest, you don't have to understand why it work Then i would get WA on pretest 2 •  » » » » » » » » 3 months ago, # ^ | ← Rev. 2 → +4 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. •  » » » 3 months ago, # ^ | 0 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. •  » » 3 months ago, # ^ | 0 Can you explain how did you do D? •  » » » 3 months ago, # ^ | ← Rev. 2 → 0 I have explained here.  » 3 months ago, # | +15 How to solve problem F ? •  » » 3 months ago, # ^ | ← Rev. 2 → +87 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$. •  » » » 3 months ago, # ^ | +9 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. •  » » » » 3 months ago, # ^ | +25 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. •  » » » » » 3 months ago, # ^ | 0 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! •  » » » » 3 months ago, # ^ | +28 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. •  » » » » 3 months ago, # ^ | +32 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.  » 3 months ago, # | 0 Suspicious submission for hacks I think the hacker made an alternate account for hacking this. •  » » 3 months ago, # ^ | 0 Why would anyone do this? Afaik you get nothing for hacking in this contest. •  » » » 3 months ago, # ^ | ← Rev. 2 → +16 Also no one gets anything by pointing this hack...and I will get nothing by this comment. •  » » » » 3 months ago, # ^ | +5 You got an upvote by me :) •  » » » » » 3 months ago, # ^ | +6 :(  » 3 months ago, # | +36 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  » 3 months ago, # | -41 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 •  » » 3 months ago, # ^ | 0 Getting downvotes due to CAPS :v  » 3 months ago, # | ← Rev. 2 → 0 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$. •  » » 3 months ago, # ^ | 0 Yes exactly, I followed the same approach and just printed the permutation 1,2,3,..k-2,k,k-1 when n!=k and printing 1,2,..k when n==k and this will create b with the same inversions but it is giving wrong answer only because it's not matching the test exactly. •  » » » 3 months ago, # ^ | 0 But the sequence$b$has to be lexicographically maximum. Now, it makes sense. •  » » 3 months ago, # ^ | 0 It's never said that$b$has to be the sequence with the least number of inversions True, but it is said that [...] and$b$is lexicographically maximum. Also note that It can be proven that$p\$ exists and is unique.
•  » » » 3 months ago, # ^ |   0 Yeah, I just found that out.
•  » » 3 months ago, # ^ |   0 I think you missed the requirement where B must be lexicographically maximum.
 » 3 months ago, # |   +47 It hurts!
•  » » 3 months ago, # ^ |   -35 roz adhoc problems karke man nahi bharta kya patang udao gilli danda khelo! come out of this artificial life.
 » 3 months ago, # |   0 Problem C and D video solutions — solution
 » 3 months ago, # |   -54 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
 » 3 months ago, # |   0 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.
•  » » 3 months ago, # ^ |   0 I did same mistake with you during contest.Try to solve this testcase by your hand 1 7 4
•  » » » 3 months ago, # ^ |   0 Yes I made a logical mistake I counted the elements which has at least 1 inversion but we have to keep into account all inversions of a single element. In my wrong logic I counted this as 2 inversions: 1 2 3 4 5 6 5 4.
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Go to secondthrad's youtube channel , he has explained that problem quiet nicely.
 » 3 months ago, # |   0 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?
•  » » 3 months ago, # ^ |   0 Yes, 4 in both cases.
•  » » » 3 months ago, # ^ |   0 Thanks
•  » » 3 months ago, # ^ |   0 Yes. It's 4 in both.
•  » » » 3 months ago, # ^ |   0 Thanks
•  » » 3 months ago, # ^ |   0 No.1 2 3 2 1 have 3 inversions and 3 2 1 2 3 have 4 inversions
•  » » » 3 months ago, # ^ |   0 Calculate it again.
•  » » » » 3 months ago, # ^ |   0 oh,sorry bro! (2,1) appears two times.I calculated it only once..sorry
•  » » » » » 3 months ago, # ^ |   0 sorry also appears two times ;)
»
3 months ago, # |
-8

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

Spoiler
•  » » 3 months ago, # ^ |   0 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.
 » 3 months ago, # | ← Rev. 2 →   0 https://codeforces.com/contest/1473/submission/104345925 can someone explain what's happening here? while time.time() — cur < 1.7: pass 
•  » » 3 months ago, # ^ |   +9 I think this violates Rule #6 by destabilizing the checking system (trying to increase the queue size by increasing the running time)
•  » » » 3 months ago, # ^ |   -24 hellohttps://codeforces.com/group/MWSDmqGsZm/contest/219856/problem/Rpls give me the code...I tried it several times ...but getting WA on Test Case 11..
 » 3 months ago, # |   0 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
•  » » 3 months ago, # ^ |   0 I got it no problem anymore:/
 » 3 months ago, # |   +26 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 :)
 » 3 months ago, # |   -6 hellohttps://codeforces.com/group/MWSDmqGsZm/contest/219856/problem/Rpls give me the code...I tried it several times ...but getting WA on Test Case 11..
 » 3 months ago, # |   +11 Problem E is really cool! I don't know why I didn't consider traversing an edge twice.
 » 3 months ago, # |   0 For anyone stuck in D, https://youtu.be/mMFkvyeRFQY
 » 3 months ago, # |   0 good contest
 » 3 months ago, # | ← Rev. 2 →   +95 People using Segment tree and MO's algo in problem D
•  » » 3 months ago, # ^ |   0 Nah, seg tree is really close to the linear solution anyway.
 » 3 months ago, # |   0 Such a great contest
 » 3 months ago, # |   +8 Does anyone have any idea what's the mistake in all the solns of E that were hacked?
•  » » 3 months ago, # ^ |   +8 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
 » 3 months ago, # |   -7 can anyone please tell me ? why my solution https://codeforces.com/contest/1473/submission/104381227 giving me TLE and my https://codeforces.com/contest/1473/submission/104359549 got accepted .... i had just halfed the loop from 1000 to 500 ?? but i had used break statement ?? please tell my why my 1st solution giving me TLE??
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 When the answer doesn't exist, break won't work at all so it's not affecting your time. So, I think it's because of this
•  » » » 3 months ago, # ^ |   0 then why answer got accepted when loop get run upto 500 ?
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 As tou said you halfed the constraints so it won't take so much time as 1000
•  » » » » » 3 months ago, # ^ |   0 but sir ,,,if its giving answer on half contraint ,,then when i get answer on 500 then it will not upto 1000 ,,,so it should be correct ??
•  » » » » » » 3 months ago, # ^ |   0 I'm talking about the time that the answer doesn't exist The break statement won't work so it must iterate over 500 possible ways not 1000 . There is a large difference between these two
 » 3 months ago, # |   +2 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
 » 3 months ago, # |   0 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.
•  » » 3 months ago, # ^ |   0 create the following arrays : MaxTillHere[] -> stores the max value upto a particular index MinTillHere[] -> stores the min value upto a particular indexthen, 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 indexnow 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 + 1I hope my answer was clear. Some index value might be wrong here, but i hope you've got the gyst of the solution!
•  » » » 3 months ago, # ^ |   0 what you mean by val[i] ? You didn't defined it . Also is MaxFromHere is same as MaxTillHere except it's starting from reverse ?
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 3 months ago, # ^ |   +5 Here. I solved it just for you. Problem D solutionWell 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.
 » 3 months ago, # |   0 Here's my attempt at creating a video solution for the round. Video Solution for Problem APlease check it out, and do tell me how i can improve! Regards.I'll be posting solutions for B, C, and D today as well.
 » 3 months ago, # |   +17 When will the rating be updated for this round.
•  » » 3 months ago, # ^ |   +4 Educational contest take too much time for ratings updation and editorial normally
 » 3 months ago, # |   +1 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=H3qBEDYwwX4link of problem A : https://www.youtube.com/watch?v=YjC6CcxYxo8&t=263sHope you guys will enjoy and understand the intution behind the solutions !!!
•  » » 3 months ago, # ^ |   +1 GREAT EXPLANATION BROTHER !!!
 » 3 months ago, # |   0 why did they temporarily roll the rating changes back ??
•  » » 3 months ago, # ^ |   0 I guess, because of the cheating issues.
•  » » » 3 months ago, # ^ |   0 That is done after every contest. Right?
•  » » » » 3 months ago, # ^ |   0 It depends . Some times they check the cheating issue when they are trying to update the ratings, so they won't roll back the rating changes
•  » » » » 3 months ago, # ^ |   0 ye but this contest took to long
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 It's always like this for Div3 and educational rounds Because of a 12-hour hacking phrase
 » 3 months ago, # |   0 why i am getting negative points? i thought in 10 min solved no penalty
•  » » 3 months ago, # ^ |   0 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
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 what if i register and 0 submission solved 0 problem i am get negative point?
•  » » » » 3 months ago, # ^ |   0 if you are registered, but you have not sent anything for the entire competition, you will not receive or lose anything
 » 3 months ago, # |   +26 is it rated for the participants with rating greater or equal to 2100? i fount some people who geater than 2100 is rated
•  » » 3 months ago, # ^ |   +18 I'm one of them :(
 » 3 months ago, # |   +23 My rating was above 2100 before taking this contest, but it was changed because of it. Could anyone tell me why?
•  » » 3 months ago, # ^ |   +21 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.
 » 3 months ago, # |   +20 I took part in this unrated contest (for Div. 1) and found my rating changed afterwards. Why? Mistake?
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 MikeMirzayanov if he didn't reply ask him privately
•  » » 3 months ago, # ^ |   +18 Same thing happened with me, please comment if you find a solution to this
•  » » » 3 months ago, # ^ |   0 I pm'd to Mike and I'm waiting for him to reply.
 » 3 months ago, # |   +4 Where is Editorial? Also Can you make problem statement clear? Problem C was so much confusing. I understood it only after reading examples.
 » 3 months ago, # |   0 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
•  » » 3 months ago, # ^ |   0 Hello there... Regarding the issue of similarity in the solutions MAlpha/104306181 and HeiXT/104318838 ... this has occurred due to the use of same LCM function from https://www.programiz.com/python-programming/examples/lcm in the program ... kindly acknowledge this Thank you
 » 3 months ago, # | ← Rev. 4 →   0 Can someone explain why for C testcase "5 3" answer is "3 2 1"a = 1 2 3 2 1 (3 invers: 3-4, 3-5, 4-5)p = 3 2 1b = 3 2 1 2 3 (4 invers: 1-2,1-3,1-4,2-3, must be 3 or less)UPD: understand
 » 3 months ago, # | ← Rev. 2 →   0 Hello there... Regarding the issue of similarity in the solutions MAlpha/104306181 and HeiXT/104318838 ... this has occurred due to the use of same LCM function from https://www.programiz.com/python-programming/examples/lcm in the program ... kindly acknowledge this Thank you @awoo
 » 3 months ago, # |   0 In the drop-down list of languages it says "Python 3.9.1" when in fact it is Python 3.8.1.
 » 3 months ago, # |   +4 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.
•  » » 3 months ago, # ^ |   0 What makes you think that your rating gets you downvotes? All your comments commending a contest have been upvoted.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +5 Love the DP, LOL :P
•  » » 3 months ago, # ^ |   0 Guddu Bhaiya Follower :)
 » 3 months ago, # |   0 can't believe i missed this