Thank you for participating in our contest! We hope you enjoyed it.

**Hint 1**

**Hint 2**

**Solution**

**Implementation (C++)**

**Implementation (Java)**

**Implementation (Python)**

**Video Editorial**

**Hint**

**Hint Solution**

**Solution**

**Implementation (C++)**

**Implementation (Java)**

**Implementation (Python)**

**Video Editorial**

**Hint**

**Solution**

**Implementation (C++)**

**Implementation (Java)**

**Implementation (Python)**

**Video Editorial**

**Hint**

**Solution**

**Implementation (C++)**

**Implementation (Java)**

**Implementation (Python)**

**Video Editorial**

**Hint**

**Hint 2**

**Hint 3**

**Solution**

**Implementation (C++)**

**Implementation (Java)**

**Implementation (Python)**

**Hint 1**

**Hint 2**

**Hint 3**

**Solution**

**Implementation (C++)**

**Implementation (Java)**

**Implementation (Python)**

**Author Notes**

saarang orz

As a rated account on CF, I hope you enjoyed giving this round officially as much as I did testing it!

Yeah, everyone did. Now stop pulling the "as a tester" tag out of your ass everywhere. One time's enough, idiot.

ok

real id se aao

Please refrain from using any language other than English on this site. It makes it harder for others to understand.

This was an awesome contest with well balanced problem (Difficulty wise). Really enjoyed the problems. Looking forward to your future contests.

Editorials with Hints listed first are best :)

They have really done a very good job(Fast editorial,video editorial,good questions)Thank u very much such a good round.

exactly

Can someone share the C++ implementation for problem C?

It's been added :)

142873986

Thanks :)

When hacking solutions, how do I filter out submissions that have been made after the contest has finished?

just untick the show unofficial checkbox at the top right corner in standings.

Something about E:

Most solutions using SPFA fail on test 31. However, using mcfx optimization I can get AC. (142882998)

Can anyone hack this solution?

First of all, orz orz orz.

But I don't think the solution you linked uses mcfx optimization. AFAICT, mcfx optimization counts the number of times a node has been pushed into the queue, and if it's in $$$[2; \sqrt V ]$$$ then it push_front's otherwise it push_back's. It speeds up your solution from 1637 ms to 343 ms!

To put it in the language of problem setter, this contest was NOT BAD ( ;

As far as I remember, problem C is a Google online coding challenge problem. (I am not sure though) But I was not able to solve it at that time and i solved it today, soo...Auto comment: topic has been updated by saarang (previous revision, new revision, compare).nice problems. )) solution of problem C is third test case in example test. I think many, including me)) solved the problem thanks to this test case.

Problem B actually has a O(N+M) solution, though it is more complicated. I have spent one hour working out this O(N+M) solution because I misunderstood the hell limits of N and M!!!!!!!!!!!!!! Just didn't notice that sum of all N*M does not exceed 1e5 (it really sucks :( Then I have not enough time to submit problem C and I was almost there...

Hey, That is IMPOSSIBLE. Because you must print n*m numbers as answers.

Yep, but it is POSSIBLE to make it a harder problem by querying part of the answers. For example, make the sum of all N + M not larger than 100,0000 and query no more than 100,0000 of different k.

You are right. But I think that will be easy. Emmm, maybe?

Maybe not that easy, I solved problem C and D after contest and it takes me less than 1 hour. Not even longer than the time I spend on the harder problem B that I imagine. But maybe someone else thinks otherwise too.

Or we can print the full answers in a compressed format, it is easy to know that the list of answers can be represented by (Ai, Ci) where i <= N+M which means the next Ci answers are all Ai. In the sample case it is (3, 2), (4, 6), (5, 4).

Don't limit your creativity bro

same here T__T

Why in E does a dijkstra not work, for example maintain the state of dp[i]=max health after haveing used ladder i. Are there that much edges, or why does such aporach goes TLE?

Regular Dijkstra's algorithm doesn't work with negative weights, or rather, it TLEs.

I see, thanks.

Regular dijkstra? is there some version that does work for negative weights?

Monogon has a blog about it here. Advertising not paid for.

It works if you handle going up (or coming down) from the ladder separately, I used dijkstra here https://codeforces.com/contest/1627/submission/142848492 , now there are no negative edge

Isn't the time complexity of D $$$(n + Alog^2(A))$$$. One log due to iterating over multiples of first A numbers and another due to gcd.

In each iteration, the gcd can only decrease upto log times in total, so the actual complexity is still $$$\mathcal{O}(n + A \log{A})$$$.

Got it. Thanks!

Isn't the complexity of just finding gcd(a,b) O(logb) ?

Yes, but the value of GCD can only decrease log times, so doing GCD $$$n$$$ times with a max value of $$$A$$$ is $$$O(n + \log A)$$$. A way of thinking about this is that most GCD operations will keep the GCD constant, so most operations don't do any actual work.

I want to know whether i can use spfa to solve E, i get Time limit exceeded on test 31 o(╥﹏╥)o

use mcfx heuristic: 142882998

or terminate spfa after some time and run dijkstra: 142886644 (thanks to polarity- for this idea)

amazing! thanks~

Can you please explain about "mcfx" or share a link? Thanks!

Use a deque instead of a queue, and every so often you push to the front of the deque instead of the back like normal.

I don't actually know

whyit works, just that it's some Chinese antihack heuristic :vNot super exciting because it's silent, but I uploaded a screencast here (I solve all problems & get 15th place): https://www.youtube.com/watch?v=aWAafRRPS2M

grid-Forces

Nice contest

Here are my video solutions for people looking for video format.

Thank you

I did almost the same in D as in editorial, but it gives TLE.

142886157

My solution does $$$(10^6-n)*n*\log_2 10^6$$$, which is at worst $$$40*10^6$$$ operations.

Please help

UPD: got it, nevermind

This part here takes $$$O(mn)$$$.

Thank you! But i think its not the case here, because of the first if. I actually misscalculated the number of operations in the worst case, it should have been $$$25*10^{10}*40=10^{13}$$$

Let's say n = (10^6)/2. Then the number of operations n * (1e6 — n) becomes huge.

Thank you! Got it

Can someone help me by explaining the proof of the editorial of problem D.

solved c shortly after the contest :(

Can't F be solved using DP? I couldn't get any mistake after almost 1 hour.

dp[i][j] -> if we have processed first and last i rows of the grid and the last segment (among k+1 segments at every row) is j assuming that all pieces are considered that don't go out of first i, last i rows, and the vertical pieces in ith and (i+1)th row are to be considered. After that transitions are pretty simple.

The problem is that paths can be very squiggly:

Ohhh right!! Got it. Thanks a lot

Where were Anjali when Tina was being so harsh on Rahul.

Anjali was removed by Monogon just before the contest :(

hahahaha.... So Monogon was the real villain.

I had used the DP solution for Problem E but I am getting WA. Can someone tell the test case on which it fails or tell me why it is wrong?

Solution

I had used DP for storing (i,j) state result which is in map m2. map m1 I am using for getting ladders for that key row.

NOte: I used the same approach but without storing state (i,j) and got TLE at 4th Test case. Solution

In problem E I tried using recursion and travelled from one ladder to another and then tried to memoize it by making a HashMap of (string of row and col). I know this might give TLE but why is it giving wrong answer. If anyone knows please help. My submission 142888967

For B i just simulate backward and figure out we will have the max distance to the 4 corners

.

You don't need to start from a leaf, you can start from any vertex. The only important thing is to give 2 and 3 (or other prime $$$p$$$ such as $$$p+2$$$ is also prime) alternately to each edge.

Became Expert after 111 contests. Thanks for the contest. Happy coding everyone.

This is possibly the most amazing editorial I've seen gosh dam

Can anyone tell me why this code is accepted 142893345 after the contest (also passed the pretests during the contest) but the exact same code gave me a runtime error when the contest ended 142863080

Seeing as no one has commented about this, we can take advantage of the fact that E has no negative cycles to still run dijkstra on it. We can use the technique of potentials in a graph, see Monogon's blog. We dont need any fancy assignment of potentials based on the edges, the idea that all nodes on floor $$$i$$$ have potential $$$10^{12} - i * 10^6$$$ is enough to get ac.

Legend has it that Monogon only decided to coordinate our contest to promote his blog.

In-contest submission 142874701 using 'map' TLE's but AC's on using 'unordered_map' 142897768 rest of the code exactly same :(

In E, I didn't think of DP but instead applied dijkstra with the same idea that we need at most 2k + 2 nodes. but It got TLE but I don't know why exactly. Isn't the complexity for Dijkstra O(V+ELOG(V))? with V up to 2k+2 and E up to 2k. shouldn't it work?

This is my submission: 142877138 (I also tried with vectors instead of sets but it got TLE too)

I know weights of ladders are negative but there can't be any cycles since all ladders are in one direction? is there something I'm missing?

Yes, Dijkstra does not work with negative edges even if there are no negative cycles. See this comment for further information.

Thanks

However, Dijkstra can be applied in this problem if we process 'nodes' level by level: submission

So am I the only one who solved B with BFS from corners? Such a shame but at least I got it.

Another (a bit more complicated) solution for $$$D$$$:

Iterate from $$$i=10^6$$$ to $$$1$$$, if $$$i$$$ does not exist yet and it is a gcd of $$$2$$$ existing multiples greater than it, mark it as existing and increment the answer.

To check if $$$i$$$ is a gcd of $$$2$$$ greater exising multiples, get all existing multiples of $$$i$$$ after dividing them by $$$i$$$, lets call this group of values $$$grp$$$, if $$$grp$$$ has a co-prime pair then $$$i$$$ is a gcd of $$$2$$$ greater existing multiples.

To check if there is a co-prime pair within $$$grp$$$ we can get the count of all pairs within $$$grp$$$ with any common divisor > $$$1$$$ using inclusion-exclusion and mobius function, let's call this count $$$cnt$$$, a co-prime pair exists if $$$cnt$$$ is less than the count of all possible pairs in $$$grp$$$.

In fact there is no need for mobius (take a look at my submission). The number of pairs with gcd $$$k$$$ is the number of pairs with both elements divisible by $$$k$$$ minus the number of those with gcd $$$2*k$$$, $$$3*k$$$...

Other parts of your idea still stay the same.

Hey, I looked at your submission for Problem D. And, I have a doubt regarding the same.

Can you please tell that, why the following loop is being added inside the if condition?

Thanks in advance!

Another interesting way to check if there is a coprime pair within $$$grp$$$ is to randomly take about 300 pairs of integers in $$$grp$$$ and see if any one of the pairs are coprime. (I don't know how likely it will fail though, at least it passed system tests. Would appreciate a lot if someone can tell the probability of my approach failing)

Just uphacked your solution 142857475, though I intended it to be a WA hack but ended up getting a TLE one lol.

It's a good contest, but E may be too easy. hope to see a more interesting problem next time.

I've solved B using bfs, there's a pattern in the distance when you go over k=0,1,2...n*m-1 the minimum distance Rahul can achieve starts at the beginning and then it propagates to it's neighbors increasing by one

Me also,I have also tried to do so the same way but wasn't able to implement in contest but later got AC using bfs.

Hi, I solved it using the same way, you can see my implementation 142879486

Hey can you explain your code a bit, please.

shashankag I learned to do bfs on matrix with this practical tutorial, I think this could be very useful as you learn the basis and then you implement the code the way in which you feel most comfortable

My solution for Problem D: First I calculate gcd of every pairs in the array using exculsion dp. Then I calculate gcd of every pairs again with the initial array and new gcds (that calculated from the previous step). After doing it 3 times, I found the answer of all the new gcds that can be calculated at most.

Hey, Can you please share any resource about this concept of finding gcd or about what exclusion DP is?

Thank you!

I managed to solve B in O(n*m). I took all the center cells, initialized them with the distance (the corner cell) and ran a bfs, which would increment distance by 1 on each level. The code is quite messy, but it works :) 142914956

In problem C Can someone tell me why I am getting a runtime error in test case 2? My logic is completely right. I am not able to figure out why it's giving a run time error. Please Help !!!!!!!!!!!!!!

Code link:https://codeforces.com/contest/1627/submission/142916147

Whil taking input if your size of neighbors of x becomes more than 2 you print -1 and return and will not take input of further edges that's why you are getting runtime error. Did the same mistake.

Thank you so much !!!!!!!!!!!!!!!!!!

someone please tell me why I am getting TLE on third test case with almost the same solution as in tutorial for problem D my code

GOT IT .... MAP MUST NOT BE USED HERE

In problem C What is the meaning of this sentence

`A path should not visit any vertex twice`

Can someone please give me an example where a path visit a vertex twice.

For example consider the edge 1-2 move along it and again come back to 1 (2-1). so you are visiting 1 twice (starting at 1 and ending at 1).

can anyone explain me which seats do Tina paint if she plays optimally? I find the solution incomprehensible.

Tina paints in a cell whose maximum distance to all the four corners is minimum.

i got it! thanks

Why the problem D's solution takes $$$O(n+AlogA)$$$? We can see that find the multiples of all $$$1\le x\le A$$$ needs $$$O(AlogA)$$$. And gets the gcd of them needs $$$O(logA)$$$ ,too. So it should take $$$O(n+Alog^2A)$$$ in deed.

Hello, please read this comment.

Why is the complexity of problem D O(n + AlogA) and not O(nlogn + AlogA) as the two for loops for finding multiples will take upto nlogn and then AlogA extra factor for gcd computations?

The code for finding multiples is $$$O(A \log A)$$$, not $$$O(n \log n)$$$ since the number of multiples depends on the size of the numbers, not the length of the array.

In problem E, I use set to save best pairs of {room, cost} for each floor. We iterate over each floor starting from floor 1, and maintain the set by stack-like insertions. 142931555

Nice Contest!! Thankyou!!

fastest editorial!!

B:O(mn)using BFS 142943120the time complexity of problem B in edutorial is O((mn)*logmn) but i think it should be O(mn+log(mn)).. maybe a typo..

It is correct. You have to sort an array of $$$nm$$$ elements. That's $$$O(nm \cdot log(nm))$$$

I am still not getting it..can you please explain it a little bit more

If you have an array of $$$n$$$ elements, then sorting is $$$O(n \log n)$$$. In this case, we have an array of $$$nm$$$ elements, so the sorting complexity is $$$O(nm \log(nm))$$$.

oh now i got that,was congused in mn.. thanks a lot dear

In problem E ,I used CHT in every row twice one from left to right other from right to left and stored answer in 2d matrix but getting WA link

Problem D can be solved in $$$ O(n + A log log A) $$$ using multi-demension prefix/suffix sum technique

143170028

I use DP for E where each rooms are represented as a single DP state. But seems I got wrong in the implementation part. Any idea what I might be missed?

My implementation : 143189459

UPDATED : It got AC when I try to change them to bottom up. It seems I got the problem :

A room can have more than 1 ladder (which in this submission, I haven't handle the case)

Not sure to proof it, but I think it's a flaw from my DP idea :

Assume we can reach room $$$U$$$ and have got the minimum cost by moving from $$$U$$$ to the final room. Assume the distance from $$$U$$$ from final node is $$$D$$$

But then, there can be more optimal path that might goes through a path that has a lot of ladders (which in this case, we "gain" more health and "lose" $$$X$$$ points, which I will denote this as $$$-X$$$) and eventually we reached back to node $$$U$$$

it can be seen that $$$D-X$$$ might be smaller than $$$D$$$ therefore the DP answer can be updated — which I can't do that in top down because once I visited state $$$U$$$, then I will have $$$dp[U]$$$ fixed and never be updated, while in fact it needs to be updated

Changed to bottom up like the editorial just did and it seems to solve the problem

Hey Everyone!

Can anyone point out why I am getting a memory error in problem C? Here is my submission : 143317279

Thanks in advance!

Problem can also be solved using breadth first search technique in time complexity of O(NM). My solution: 143357988 Thanks

Can

problem Ebe solved usingdjakstra??No

https://codeforces.com/contest/1627/submission/142841460 Can someone please explain behind the logic of dfs(u, p, c). And, also I was confused, because on iteration of adj[u], dfs(nxt, u, !c) will again execute even the for loop hasn't completed.

1627E - Not Escaping why 143474919 wrong answer 23 ? what's wrong?

can someone pls tell me what is wrong in this solution I am unable to understand it. problem — 1627D — Not Adding — https://codeforces.com/contest/1627/problem/D solution — https://codeforces.com/contest/1627/submission/143931841 @saarang

Spoiler2

6 12

Expected ans : 0

Your ans : 3

thankyou got my mistake

Can anyone please check why my this solution for problem E using dijkstra gets TLE on test case 8.I have not used negative edges and used dijkstra for each row separately.

Link to my submission:- https://codeforces.com/contest/1627/submission/144133636

Hey did you figure out mistake ? I also have similar approach but got TLE on test 4.

147170375

Can someone explain the dp for E? It is not clear to me what are the states and how they are updated efficiently.

Can C be solved using BFS ?

Why my code TLEs for problem E? Please help I have used shortest path approach using dijkstras algo. I have written comments for easy understanding of code. Complexity for my code is O(klogk) imo. 147170375