### chokudai's blog

By chokudai, history, 4 months ago,

We will hold AtCoder Beginner Contest 237.

We are looking forward to your participation!

• +50

 » 4 months ago, # |   0 for D I created binary tree and did inorder traversal on it. I'm sure there's better approach for it.
•  » » 4 months ago, # ^ |   +14 You process the queries backwards and see what will happen!
•  » » » 4 months ago, # ^ |   +8 Yes I did this way : link
•  » » 4 months ago, # ^ |   0 It can be done using deque if you the process string in reverse order
•  » » 4 months ago, # ^ |   +5 Linked Lists can also be used to solve this. Submission
•  » » » 4 months ago, # ^ |   +2 Note that the STL list provides the method pos=lis.insert(pos,int) which is all we need.example submission
•  » » » » 4 months ago, # ^ |   0 The fact that using STL List supports constant time insertion didn't come to mind during the contest. By the way, thanks for the info!
•  » » » » 3 months ago, # ^ |   0 thanks for this info dude.
•  » » 4 months ago, # ^ |   +4 Recursion is also a very good way to solve the problem.See this submission for more details.PS: This code isn't written by me.
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 For the first time I used linked list (+map) to solve a question on atcoder.
 » 4 months ago, # |   +42 I don't know if it's a bug in atcoder or the problem was updated, but I got the statement for problem D as problem B at first before I reloaded: https://imgur.com/a/FFEzsaY
•  » » 4 months ago, # ^ |   +1 ya it happened with me as well.
•  » » 4 months ago, # ^ |   +4 I know I was wondering why it's taking me longer to do B.
•  » » 4 months ago, # ^ |   +4 Same for me, one wrong submission.
•  » » » 4 months ago, # ^ | ← Rev. 3 →   +4 Check the clarifications tab.If you have submitted the answer to question D to question B, please contact us through the clarification tab within 5 minutes after the contest ends. We will delete your submission.
•  » » » » 3 months ago, # ^ |   +2 My bad, I didn't see clarification at that time.
•  » » 3 months ago, # ^ |   0 Me too. I skipped B(or D) and started doing C
 » 4 months ago, # | ← Rev. 2 →   +3 Can somebody explain why a super simple bfs in E does not TLE?Edit: In example this submission
•  » » 4 months ago, # ^ | ← Rev. 3 →   0 Simple BFS worked for E ? :( I had to do Bellman Ford to solve it My Code with Bellman Ford
•  » » » 4 months ago, # ^ |   +19 I used max Dijkstra
•  » » » » 4 months ago, # ^ |   0 I thought of using it then remembered it does not handle negative edges so Thought of using this
•  » » » » » 4 months ago, # ^ | ← Rev. 2 →   +12 negative edges are ok, but not negative cycles. And there are no negative cycles as this would be physically impossible
•  » » » » » » 3 months ago, # ^ |   +3 Why are negative edges ok but not negative cycles? Doesn't dijkstra work because before processing vertex v, we have already processed all vertices with distance smaller that distance to v, and negative edges would break this
•  » » » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 Depends on your implementation, if you allow to visit a node more than once you will be fine. The runtime analysis is then a bit more complicated, but I believe it should better than Bellman Ford, as latter will do the maximum amount of iterations possible, while Dijkstra might stop earlier.. Implementation using a set, to update keys inside the priority queue (from CP4)// SSSP DIJKSTRA vector dijkstra(int start, vector> &AL){ // O(E * log(V)) // Instead of PQ use a set to update nodes once you see a lower value. The complexity lower but in Big O still the same // DOES NOT WORK WITH NEGATIVE WEIGHT CYCLES ll n = AL.size(); vector dist(AL.size(), INF); dist[start] = 0; set pq; pq.emplace(dist[start], start); while(pq.size()){ auto [cost, cur] = *pq.begin(); // intotal O(V * log(V)) pq.erase(pq.begin()); for(auto [next, w]: AL[cur]){ if(dist[cur] + w >= dist[next]) continue; auto it = pq.find({dist[next], next}); if(it != pq.end()){ pq.erase(it); // O(E * log(V)); } dist[next] = dist[cur] + w; pq.emplace(dist[next], next); } } return dist; }. 
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +12 How did you do bellman Ford? It's n^2 right. And how are dijkstra solution passing for E. :(. There are negative edge weights. It should fail!!
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 Negate the costs https://atcoder.jp/contests/abc237/submissions/28945458
•  » » » » » 4 months ago, # ^ |   0 Doesn't matter, even if you negate, positives become negative, and negative become positive. Still negative will be present.
•  » » » » » » 4 months ago, # ^ | ← Rev. 10 →   +4 The problem with dijkstra in a graph that has negative edges, even if it doesn't have negative cycles, is that it works slower. I make an optimization in the dijkstra that is: when I remove a node from the priority queue, I mark it, so as not to calculate it again in the future.This works because this algorithm is greedy, and since the node that I remove from the priority queue at a given moment, I will not be able to update it in the future, because all the nodes that I analyze later will have a distance from the initial node greater than its distance. This would fail in a graph with some negative edge. The algorithm itself would work as long as there are no negative cycles. This is a graph that breaks the optimization I'm trying to explain:In this problem there is no difficulty of any kind with negative edges since we want to maximize the distance, so edges with negative weights do not suit us.
•  » » » » » 3 months ago, # ^ |   +1 Your code fails for testcase added after contest https://atcoder.jp/contests/abc237/submissions/28970593
•  » » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 Thanks. I realized that I was lucky. Now, I saw a Tweet and followed the advice to change priority queue to queue. Then the after contest test passes: submission The Tweet says AtCoder should add one more after contest test case so that changing PQ to queue still TLE.
•  » » » » 4 months ago, # ^ | ← Rev. 3 →   +7 The final happiness ending at node i can be viewed as (Initial height — final height) — All the edges where you travelled upwards. So make a graph where upward edges have positive weights and the downward edges have weight zero. Find minimum distance for each node from node 1. Submission
•  » » » » 4 months ago, # ^ |   0 My dijkstra implementation using set got TLEd but with priority queue it passed. It was a gamble since there was one problem in a recent contest from which I learned that dijkstra will fail if there is a negative weight even though there are no negative cycle. I want to know the solutions other than shortest paths or is it even possible?
•  » » » » 4 months ago, # ^ |   +3 Let dp[v] be maximum happiness reaching vertex v. We initialize dp with negative inf and dp[1] = 0. Let's say we have an edge between vertex 1 and 2, and {height of 1} < {height of 2}.When we're updating vertex 1's neighbors, dp[2] = max(dp[2], dp[1] - (h[2] - h[1]) * 2) The second one is obviously bigger since we set all values to -inf by default, and therefore values can be calculate with dijkstra's.My submission
•  » » 4 months ago, # ^ |   0 The while() cycle does what a normal while() in bfs does — goes over all nodes, so O(n) from here. For every node, we traverse all its edges and since every edge has two endpoints, this means we get O(2M) iterations from here. So all in all we get a complexity of O(n + 2m). Hope that helped!
•  » » 3 months ago, # ^ |   0 I think it's SPFA, Shortest Path Fast Algorithm. It will run in approximately O(N + M). It doesn't get TL because it's hard to construct a good graph.
•  » » » 3 months ago, # ^ |   +8 Thanks for pointing that out. Actually, that is what I referred to as "super simple bfs". It looks like dijkstra but with a simple queue instead of a priority queue.And also the problem with this is described in the article, its worst case complexity is like Bellman-Ford, so would TLE.On the other hand, the way the tree is constructed makes to edge weights not arbitrary, they obviously determine each other. It seems that this makes the simple algorythm work. Which, frankly said, makes the problem a bad one. Given the fact that this is a beginner contest, we can assume that a lot, maybe the most partitipants who solved it did not because beeing smart enough to see that.
 » 4 months ago, # | ← Rev. 2 →   +13 Me after solving A,B,C,D,E SpoilerTranslation : It's not my zone of expertise, I am out.Can anyone explain their approach for F as editorial is not published for now.
•  » » 4 months ago, # ^ | ← Rev. 3 →   +11 I solved F with DP, so dp[i][j][k][l] can count the number of sequences up to the ith number, where LIS of length 1 end with j, LIS of length 2 end with k and LIS of length 3 end with l. In each of these states you can iterate through all numbers 1,..,m, and either make one number j, k or l smaller or we are not allowed to use it (as greater than current l)So there are n*m^3 states and each state needs O(m) -> O(n*m^4) = O(1000*10000) = O(10.000.000)
•  » » » 4 months ago, # ^ |   +9 If you use a bitmask to maintain the young diagram . You can know the number of sequence which LIS is k (k<=m) in O(n2^m).
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 Is this a standard technique? If yes, can you provide resources (problems, or a blog-post) on it?
•  » » » » » 4 months ago, # ^ |   +7 I only found this (in Chinese).
•  » » » » 3 months ago, # ^ |   +13 Gary2005 your approach is lit....Just amazed me as for LIS upto M you just only have to change if condition of popcount==3 to popcount==LIS and solution Time complexity is independent of LIS length required henced amazed me great Approach. Thankyou For sharing....
•  » » 4 months ago, # ^ |   0 plz explain E same for me after doing 4 only also tell some resourses for graphs
•  » » » 4 months ago, # ^ |   0 Do max dijkstra My previous comment
•  » » 4 months ago, # ^ |   0 Spoilerlet $f_{i,x,y,z}$ be the number of cases in $a_{1..i}$ while the longest incraesing sequence is $x$, $y$ ($m+1$ if not exist) and $z$ ($m+2$ if not exist).Initially, $f_{1,i,m+1,m+2}=1\;(1\le i\le m)$. The main part for(int i=2;i<=n;i++) for(int x=1;x<=m;x++) for(int y=x+1;y<=m+1;y++) for(int z=y+1;z<=m+2;z++) if(z!=m+1){ for(int j=1;j<=m;j++) if(j<=x) f[i][j][y][z]=(f[i][j][y][z]+f[i-1][x][y][z])%MOD; else if(j<=y) f[i][x][j][z]=(f[i][x][j][z]+f[i-1][x][y][z])%MOD; else if(j<=z) f[i][x][y][j]=(f[i][x][y][j]+f[i-1][x][y][z])%MOD; } The answer is $\sum\limits_{x=1}^m\sum\limits_{y=x+1}^m\sum\limits_{z=y+1}^m f_{n,x,y,z}$.
 » 4 months ago, # | ← Rev. 2 →   0 Ex and div1f of last round are exactly the same problem.(After building the graph)
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 Excuse me, which round? Do you mean that the algorithms or the tricks are the same, or something else?UPD: I see. Thank you very much.
•  » » » 4 months ago, # ^ |   0
 » 4 months ago, # |   +3 problem G
•  » » 3 months ago, # ^ |   +10 Actually it can be solved much easily using just 3 lazy segtrees, as we just need to keep track of number X(say 1), and numbers smaller than X(say 0) and bigger than X(say 2).
•  » » » 3 months ago, # ^ |   +8 It can be solved using 1 lazy segment tree, and just keeping track of the index of $x$ after every query.My submission
•  » » 3 months ago, # ^ |   0 Can you share your submission for that? I think I am too stupid to get this blog-post :(
 » 4 months ago, # |   0 Anyone with Top Down approach for F ? It will be great if you can share your code
•  » » 4 months ago, # ^ |   +2
•  » » » 4 months ago, # ^ |   +3 Arigato :D
•  » » » 3 months ago, # ^ |   0 if(curIdx == n && rd != m+1) return ans = 1; if(curIdx==n) return 0; can u plz explaint these lines?
•  » » » » 3 months ago, # ^ | ← Rev. 4 →   0 Hey mate, I used m+1 as dummy value, when the rd ( meaning the smallest end of a LIS of length three — naming is bad here) is still m+1, we don't have no LIS of length 3.For example, If you choose 123 you will have fst = 1, snd = 2 and rd = 3. However if you have 111 you will have fst = 1, snd = m+1 and rd = m=1, meaning you only have a LIS of length 1.Not sure how the others implemented it. For me this felt the most natural.
 » 4 months ago, # |   0 I solved Ex using a greedy maximal clique solution.
 » 4 months ago, # | ← Rev. 2 →   +10 why don't atcoder amalgamate test cases like cf and cc it will be easier to copy and check on local compilers
 » 4 months ago, # |   0 The editorial is available in Japanese but not in English. Maybe there is just a script to run to make it available ?
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 The sample solution are written in C++ or Java or Python. Those are still readable without knowing Japanese.
 » 4 months ago, # |   0 can someone explain problem e solution plz
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 The problem can be expressed as a shortest path problem.To avoid negative weights, you can use a feasible potential, as explained in the lecture 4 of this course: https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15850-f18/www/Then the problem can be solved with the Dijkstra's algorithm.
•  » » 3 months ago, # ^ |   0 see aboveNote that also a simple bfs works fine. I am still not sure if this is caused by the construction of the tree, or weak tests.
 » 3 months ago, # |   +10 When will be the editorials posted? It has not been posted yet.
•  » » 3 months ago, # ^ |   +3 I translated them myself: https://atcoder.jp/contests/abc237/editorial/3347
•  » » » 3 months ago, # ^ |   0 Thanks a lot :D
 » 3 months ago, # |   +8 Since official English editorials never arrived, I translated all Japanese editorials myself. They are brief and not word-to-word precise, more like my own restatement of the official solution. Hope it helps.https://atcoder.jp/contests/abc237/editorial/3347
•  » » 3 months ago, # ^ |   0 In order to understand G, I spent 2 days now reading the segment-tree for sorting subsequences and I still didn't really get it. Now I read your translation, and after 2 mins I got it. Thanks a lot & well done :)
 » 3 months ago, # |   0 can someone tell why max Dijkstra on problem E getting TLE?My submission