saarang's blog

By saarang, history, 4 months ago,

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

Hint 1
Hint 2
Solution
Implementation (C++)
Implementation (Java)
Implementation (Python)

1627B - Not Sitting

Hint
Hint Solution
Solution
Implementation (C++)
Implementation (Java)
Implementation (Python)

1627C - Not Assigning

Hint
Solution
Implementation (C++)
Implementation (Java)
Implementation (Python)

Hint
Solution
Implementation (C++)
Implementation (Java)
Implementation (Python)

1627E - Not Escaping

Hint
Hint 2
Hint 3
Solution
Implementation (C++)
Implementation (Java)
Implementation (Python)

1627F - Not Splitting

Hint 1
Hint 2
Hint 3
Solution
Implementation (C++)
Implementation (Java)
Implementation (Python)
Author Notes

• +238

 » 4 months ago, # |   +15 saarang orz
 » 4 months ago, # | ← Rev. 2 →   +38 As a rated account on CF, I hope you enjoyed giving this round officially as much as I did testing it!
•  » » 4 months ago, # ^ |   -31 Yeah, everyone did. Now stop pulling the "as a tester" tag out of your ass everywhere. One time's enough, idiot.
•  » » » 4 months ago, # ^ |   +27 ok
•  » » » 4 months ago, # ^ |   +10 real id se aao
•  » » » » 4 months ago, # ^ |   -21 Please refrain from using any language other than English on this site. It makes it harder for others to understand.
 » 4 months ago, # |   +7 This was an awesome contest with well balanced problem (Difficulty wise). Really enjoyed the problems. Looking forward to your future contests.
 » 4 months ago, # |   +38 Editorials with Hints listed first are best :)
•  » » 4 months ago, # ^ | ← Rev. 2 →   +23 They have really done a very good job(Fast editorial,video editorial,good questions)Thank u very much such a good round.
•  » » » 4 months ago, # ^ |   -6 exactly
 » 4 months ago, # |   0 Can someone share the C++ implementation for problem C?
•  » » 4 months ago, # ^ |   0 It's been added :)
•  » » 4 months ago, # ^ |   0
•  » » » 4 months ago, # ^ |   0 Thanks :)
 » 4 months ago, # |   0 When hacking solutions, how do I filter out submissions that have been made after the contest has finished?
•  » » 4 months ago, # ^ |   +2 just untick the show unofficial checkbox at the top right corner in standings.
 » 4 months ago, # |   +18 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?
•  » » 2 months ago, # ^ |   0 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!
 » 4 months ago, # |   +1 To put it in the language of problem setter, this contest was NOT BAD ( ;
 » 4 months ago, # |   0 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...
 » 4 months ago, # |   +10 Auto comment: topic has been updated by saarang (previous revision, new revision, compare).
 » 4 months ago, # |   -16 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. Input 7 1 2 1 3 3 4 3 5 6 2 7 2  Output -1 
 » 4 months ago, # |   -19 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...
•  » » 4 months ago, # ^ |   +36 Hey, That is IMPOSSIBLE. Because you must print n*m numbers as answers.
•  » » » 4 months ago, # ^ |   0 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.
•  » » » » 4 months ago, # ^ |   0 You are right. But I think that will be easy. Emmm, maybe?
•  » » » » » 4 months ago, # ^ |   0 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.
•  » » » 4 months ago, # ^ |   0 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
•  » » 4 months ago, # ^ |   0 same here T__T
 » 4 months ago, # |   0 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?
•  » » 4 months ago, # ^ |   +28 Regular Dijkstra's algorithm doesn't work with negative weights, or rather, it TLEs.
•  » » » 4 months ago, # ^ |   0 I see, thanks.
•  » » » 4 months ago, # ^ | ← Rev. 5 →   0 Regular dijkstra? is there some version that does work for negative weights?
•  » » » » 4 months ago, # ^ |   +33 Monogon has a blog about it here. Advertising not paid for.
•  » » 4 months ago, # ^ |   +6 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
 » 4 months ago, # |   +11 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.
•  » » 4 months ago, # ^ |   +39 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})$.
•  » » » 4 months ago, # ^ |   0 Got it. Thanks!
•  » » » 4 months ago, # ^ |   0 Isn't the complexity of just finding gcd(a,b) O(logb) ?
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   +9 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.
 » 4 months ago, # |   0 I want to know whether i can use spfa to solve E, i get Time limit exceeded on test 31 o(╥﹏╥)o
•  » » 4 months ago, # ^ |   +2 use mcfx heuristic: 142882998or terminate spfa after some time and run dijkstra: 142886644 (thanks to polarity- for this idea)
•  » » » 4 months ago, # ^ |   0 amazing! thanks~
•  » » » 4 months ago, # ^ |   0 Can you please explain about "mcfx" or share a link? Thanks!
•  » » » » 4 months ago, # ^ |   +7 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 why it works, just that it's some Chinese antihack heuristic :v
 » 4 months ago, # | ← Rev. 2 →   +26 Not 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
 » 4 months ago, # |   +32 grid-Forces
 » 4 months ago, # |   +5 Nice contest
 » 4 months ago, # |   0 Here are my video solutions for people looking for video format.
•  » » 4 months ago, # ^ |   0 Thank you
 » 4 months ago, # | ← Rev. 2 →   0 I did almost the same in D as in editorial, but it gives TLE.142886157My solution does $(10^6-n)*n*\log_2 10^6$, which is at worst $40*10^6$ operations.Please helpUPD: got it, nevermind
•  » » 4 months ago, # ^ |   +1 This part here takes $O(mn)$. for(int i = 1; i < m; i++) { if(used[i] == 1)continue; t = 0; for(int j = 0; j < n; j++) { if(a[j] % i == 0) { t = gcd(t, a[j]); } } if(t == i)ans++; } 
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 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}$
•  » » 4 months ago, # ^ | ← Rev. 2 →   +1 Let's say n = (10^6)/2. Then the number of operations n * (1e6 — n) becomes huge.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 Thank you! Got it
 » 4 months ago, # |   0 Can someone help me by explaining the proof of the editorial of problem D.
 » 4 months ago, # |   0 solved c shortly after the contest :(
 » 4 months ago, # |   +8 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.
•  » » 4 months ago, # ^ |   +32 The problem is that paths can be very squiggly:
•  » » » 4 months ago, # ^ |   +8 Ohhh right!! Got it. Thanks a lot
 » 4 months ago, # |   +2 Where were Anjali when Tina was being so harsh on Rahul.
•  » » 4 months ago, # ^ |   +22 Anjali was removed by Monogon just before the contest :(
•  » » » 4 months ago, # ^ |   +14 hahahaha.... So Monogon was the real villain.
 » 4 months ago, # | ← Rev. 3 →   0 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?SolutionI 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
 » 4 months ago, # |   0 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
 » 4 months ago, # |   0 For B i just simulate backward and figure out we will have the max distance to the 4 corners
 » 4 months ago, # | ← Rev. 2 →   0 .
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 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.
 » 4 months ago, # |   0 Became Expert after 111 contests. Thanks for the contest. Happy coding everyone.
 » 4 months ago, # |   0 This is possibly the most amazing editorial I've seen gosh dam
 » 4 months ago, # |   0 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
 » 4 months ago, # |   +12 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.
•  » » 4 months ago, # ^ |   +17 Legend has it that Monogon only decided to coordinate our contest to promote his blog.
 » 4 months ago, # |   0 In-contest submission 142874701 using 'map' TLE's but AC's on using 'unordered_map' 142897768 rest of the code exactly same :(
 » 4 months ago, # | ← Rev. 3 →   0 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?
•  » » 4 months ago, # ^ |   +1 Yes, Dijkstra does not work with negative edges even if there are no negative cycles. See this comment for further information.
•  » » » 4 months ago, # ^ |   0 Thanks
•  » » » 4 months ago, # ^ |   0 However, Dijkstra can be applied in this problem if we process 'nodes' level by level: submission
 » 4 months ago, # |   0 So am I the only one who solved B with BFS from corners? Such a shame but at least I got it.
 » 4 months ago, # | ← Rev. 3 →   +5 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$.
•  » » 4 months ago, # ^ |   +8 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.
•  » » » 4 months ago, # ^ |   +3 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?  if(cnt[i]>=1&&!a[i]) { res++,a[i]=1; for(int j=2*i;j<=(int)1e6;j+=i) { cnt[i]+=a[j]; } } Thanks in advance!
•  » » 4 months ago, # ^ |   +3 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)
•  » » » 4 months ago, # ^ |   0 Just uphacked your solution 142857475, though I intended it to be a WA hack but ended up getting a TLE one lol.
 » 4 months ago, # |   0 It's a good contest, but E may be too easy. hope to see a more interesting problem next time.
 » 4 months ago, # |   0 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
•  » » 4 months ago, # ^ |   0 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.
•  » » » 4 months ago, # ^ |   +3 Hi, I solved it using the same way, you can see my implementation 142879486
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 Hey can you explain your code a bit, please.
•  » » » » » 4 months ago, # ^ |   0 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
 » 4 months ago, # | ← Rev. 2 →   0 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.
•  » » 4 months ago, # ^ |   0 Hey, Can you please share any resource about this concept of finding gcd or about what exclusion DP is?Thank you!
 » 4 months ago, # |   0 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
 » 4 months ago, # |   0 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 !!!!!!!!!!!!!! #include using namespace std; #include void dfs(ll i ,vector>*adj , bool *vis ,ll c, map&mp ) { vis[i]=true; for(auto it:adj[i]) { if(!vis[it.first]) { mp[it.second] = c; if(c==5) { c=2; } else { c=5; } dfs( it.first ,adj ,vis,c,mp); } } } void solve() { ll n;cin>>n; vector>adj[n+1]; map,ll>p; mapmp; ll deg =0; ll start; for(int i=0;i>x>>y; x--; y--; adj[x].push_back({y,i}); adj[y].push_back({x,i}); if(adj[x].size()>=3 ||adj[y].size()>=3 ) { cout<<-1; return ; } } for(int i=0;i>t; while(t--) { solve(); cout<<"\n"; } } 
•  » » 4 months ago, # ^ |   0 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.
•  » » » 4 months ago, # ^ |   0 Thank you so much !!!!!!!!!!!!!!!!!!
 » 4 months ago, # |   0 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
•  » » 4 months ago, # ^ |   0 GOT IT .... MAP MUST NOT BE USED HERE
 » 4 months ago, # |   0 In problem C What is the meaning of this sentence A path should not visit any vertex twiceCan someone please give me an example where a path visit a vertex twice.
•  » » 4 months ago, # ^ |   0 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).
 » 4 months ago, # | ← Rev. 2 →   0 can anyone explain me which seats do Tina paint if she plays optimally? I find the solution incomprehensible.
•  » » 4 months ago, # ^ |   0 Tina paints in a cell whose maximum distance to all the four corners is minimum.
•  » » » 4 months ago, # ^ |   0 i got it! thanks
 » 4 months ago, # |   0 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.
•  » » 4 months ago, # ^ |   +3 Hello, please read this comment.
 » 4 months ago, # |   0 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?
•  » » 4 months ago, # ^ |   +8 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.
 » 4 months ago, # |   0 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
 » 4 months ago, # |   0 Nice Contest!! Thankyou!!
 » 4 months ago, # |   0 fastest editorial!!
 » 4 months ago, # | ← Rev. 4 →   0 B: O(mn) using BFS 142943120
 » 4 months ago, # |   0 the time complexity of problem B in edutorial is O((mn)*logmn) but i think it should be O(mn+log(mn)).. maybe a typo..
•  » » 4 months ago, # ^ |   0 It is correct. You have to sort an array of $nm$ elements. That's $O(nm \cdot log(nm))$
•  » » » 4 months ago, # ^ |   0 I am still not getting it..can you please explain it a little bit more
•  » » » » 4 months ago, # ^ |   +3 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))$.
•  » » » » » 4 months ago, # ^ |   +8 oh now i got that,was congused in mn.. thanks a lot dear
 » 4 months ago, # |   0 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
 » 4 months ago, # |   +6 Problem D can be solved in $O(n + A log log A)$ using multi-demension prefix/suffix sum technique143170028
 » 4 months ago, # |   +3 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
•  » » 4 months ago, # ^ |   0 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
 » 4 months ago, # | ← Rev. 4 →   0 Hey Everyone!Can anyone point out why I am getting a memory error in problem C? Here is my submission : 143317279Thanks in advance!
 » 4 months ago, # |   +3 Problem can also be solved using breadth first search technique in time complexity of O(NM). My solution: 143357988 Thanks
 » 4 months ago, # |   0 Can problem E be solved using djakstra ??
•  » » 4 months ago, # ^ |   +8 No
 » 4 months ago, # |   0 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.
 » 4 months ago, # |   0 1627E - Not Escaping why 143474919 wrong answer 23 ? what's wrong?
 » 4 months ago, # | ← Rev. 4 →   0 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 vi p(1000005,0); void solve(int t){ int n; cin>>n; int mx=-1; rep(i,1,n){ int tmp; cin>>tmp; p[tmp]=1; mx = max(mx,tmp); } int ans=0; repi(i,mx,1){ if(p[i]) continue; int cnt=0; for(int j=i*2;j<=mx;j+=i){ if(p[j]) cnt++; } if(cnt>=2){ ans++; p[i]=1; } } cout<
•  » » 4 months ago, # ^ |   0 Spoiler2 6 12 Expected ans : 0 Your ans : 3
•  » » » 3 months ago, # ^ |   0 thankyou got my mistake
 » 4 months ago, # | ← Rev. 2 →   0 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
•  » » 3 months ago, # ^ |   0 Hey did you figure out mistake ? I also have similar approach but got TLE on test 4.147170375
 » 4 months ago, # |   0 Can someone explain the dp for E? It is not clear to me what are the states and how they are updated efficiently.
 » 3 months ago, # |   0 Can C be solved using BFS ?
 » 3 months ago, # | ← Rev. 2 →   0 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