### chokudai's blog

By chokudai, history, 6 weeks ago,

We will hold ZONe Energy Programming Contest.

The point values will be 100,200,400,300,500,600.

Attention This contest is equivalent to AtCoder Beginner Contest. Please pay attention to the point values bellow. Problem C is 400 points. We are looking forward to your participation!

• +63

•  » » 6 weeks ago, # ^ |   +4 For E, what is the use of the dummy node? Shouldn't just adding normal edges from $(i,j)$ to all $( •  » » » 6 weeks ago, # ^ | 0 Oh my bad, I had constraints differently in my mind. •  » » » 6 weeks ago, # ^ | +3 Yeah, that's what I did, and it passed in 200ms (though it TLE'ed on TC26 when I forgot that I can output the answer before calculating every path) •  » » » » 6 weeks ago, # ^ | 0 I don't think some heuristic like this is supposed to be done with the solution has intended complexity. Test case 26 was special but could be passed if for the same weight you give the lower node a higher priority, that is the reason why most of the people who used$greater<>$in priority queue with$O(N^3)$implementation passed whereas those using$-dist$TLEd. Apparently$O(N^3 * log(N^3))$might be still too much for 2 secs cause the editorial had a quadratic solution.On a side note if the quadratic solution was expected then N should have been set higher, whole contest I thought I had a bug in my Dijkstra :( •  » » » » 6 weeks ago, # ^ | 0 Thank you, that was my mistake for case 26 too!I also used another optimisation, when iterating on the$r \rightarrow r-i$move I stopped iterating$i$if$ new cost > old cost $. That way i even got it down to 80ms (Optimisation on line 124/125). Without this optimisation I got 200ms. The solution with dummy nodes is at 160ms for me. •  » » » » » 6 weeks ago, # ^ | 0 Hmm... that's a smart optimization! Interesting that it's faster than the intended solution even though it has a (technically) worse complexity. Maybe that means the tests were weak? •  » » 6 weeks ago, # ^ | ← Rev. 2 → +6 For D , I used deque and maintained a bool variable to keep track of reverse operations. https://atcoder.jp/contests/zone2021/submissions/22239816 •  » » » 6 weeks ago, # ^ | 0 Oh nice solution. Just after reading the problem, I wanted to use treaps for it but went ahead with the original one to avoid any TLE. •  » » » » 6 weeks ago, # ^ | +1 thanks :D •  » » » 6 weeks ago, # ^ | +3 MY solution with Deque// ==================== Solve ===================== void solve() { string s; cin >> s; bool r = 0; deque T; rep(i, 0, sz(s)) { if (s[i] != 'R') { if (!r) T.push_back(s[i]); else T.push_front(s[i]); } else { r = !r; } //cout << T << endl; } string tt = ""; for (auto x : T) tt += x; if (r) reverse(all(tt)); //cout << tt << endl; stack st; rep(i, 0, sz(tt)) { if (st.empty()) st.push(tt[i]); else if (!st.empty() && st.top() == tt[i]) { st.pop(); } else if (!st.empty() && st.top() != tt[i]) { st.push(tt[i]); } } string res = ""; while (!st.empty()) { res += st.top(); st.pop(); } reverse(all(res)); cout << res << endl; } // ================================================  •  » » 6 weeks ago, # ^ | 0 C, "we need to take any 3 masks from given array"How does this work in less than O(n^3)?I implemented it otherwise. In the binary search, brute force find a pair of two people with at least 4 of the 5 powers > mid. If found, quick find one person for the last of the 5 powers. •  » » » 6 weeks ago, # ^ | -8 You can use DP. •  » » » » 6 weeks ago, # ^ | 0 Can you elaborate ? •  » » » » » 6 weeks ago, # ^ | 0 You are given n bitmasks and you need to check wheter you can pick 3 of them so that thier OR is 31 (this is the part of the problem where we check wheter we can obtain team's total strength >= d in binary search). So it suffices to go from left to right and define dp[i][j][k] is true if and only if you can obtain bitmask J if you considered only prefix of length i and you took exactly k masks. So the answer will be dp[n][31][3]. •  » » » » » » 6 weeks ago, # ^ | ← Rev. 5 → 0 Can you explain what will be the transitions ? Can you also give the link to your submission •  » » » » » » » 6 weeks ago, # ^ | ← Rev. 3 → -8 https://atcoder.jp/contests/zone2021/submissions/22207745If you want to use DP without binary search I would do something like that: Go from left to right and decide for current guy whether he is in the team, and if yes what subset of parameters he is contributing to the team. So the complexity would be sth like n * (3 ^ m) where m is the number of parameters (5 in our case) and you will need to remeber similar thing for the dp: prefix of considered guys, how many of them are already taken and which subset of parameters comes from them. •  » » » » » » » » 6 weeks ago, # ^ | 0 Okkk Thanks •  » » » 6 weeks ago, # ^ | ← Rev. 2 → +1 As I said repetition of masks is allowed. So we only need to consider if at ith level we wanted to build a mask using previous mask m from level i-1 and current array element mask m1. There are 3 levels, for each level we do O(previous mask * N) iterations where number of previous distinct masks are less than equal to 32 or 2^5. PS : infact you can improve the runtime from O(32*N) per level to O(32*min(N,32)) per level. •  » » » 6 weeks ago, # ^ | 0 Yeah I had a similar approach but there was no need for binary search? submission •  » » 6 weeks ago, # ^ | +8 E, simple dijkstra with a priority queue also works. Not sure if this is caused by weak tests. submission •  » » » 5 weeks ago, # ^ | ← Rev. 3 → 0 I have also used the same method on upsolving.Just want to make sure that will this approach not get TLE? Does it pass because of weak testcases??  » 6 weeks ago, # | 0 Can someone please clarify why this is giving tle for the task D Code FastScanner fs = new FastScanner(); // int t = fs.nextInt(); int t = 1; StringBuffer res = new StringBuffer(); for (int tt = 1; tt <= t; tt++) { String s = fs.next(); int count = 0; String ans = ""; boolean flag = false; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == 'R') { if (ans.length() == 0) continue; count++; flag = !flag; } else { if (flag) { ans = s.charAt(i) + ans; } else { ans = ans + s.charAt(i); } } } if (count % 2 != 0) { ans = (new StringBuilder(ans)).reverse().toString(); } Stack st = new Stack<>(); for (int i = 0; i < ans.length(); i++) { if (st.size() > 0 && (ans.charAt(i) == st.peek())) { st.pop(); } else { st.push(ans.charAt(i)); } } StringBuffer y = new StringBuffer(); while (!st.isEmpty()) { y.append(st.pop()); } y.reverse(); res.append(y); } System.out.println(res);  •  » » 6 weeks ago, # ^ | 0 You are using string concatenation for adding each character to your ans string. On each concatenation a new copy of the string is created which has complexity of O(current length of string), so that the overall complexity is O(n^2)  » 6 weeks ago, # | 0 Can anyone explain problem B? I think it's geometry problem and anything to do with trapozoids.But could not get any idea though •  » » 6 weeks ago, # ^ | ← Rev. 4 → 0 Binary Search Solution : Let's say we have a minimum height h that you must have to climb. The proposition is that if you can do it in h, then you can do it in all h_new >= h.So basically we can Binary Search the minimum h that is possible. Now what you have to do : make an assumption for some h and connect a line from (0, h) to (D, H) and then find if all the N points lie below this or not. Either way reduce the search space to 1/2. TC : O(log(1/accuracy) * N).Alternate Solution :Lets say that for some point (d[i], h[i]) we have to make sure that the height h lies above or equal to when this line cuts the y-axis (or at x = 0).So the equation of the line can be written as : y - h[i] = ((D - d[i]) / (H - h[i])) (x - d[i]).At x = 0, we have y = h[i] - d[i] * (slope).Answer is max(0, h[i] - d[i] * (slope) for all 1 <= i <= N. TC : O(N) •  » » » 6 weeks ago, # ^ | 0 Thanks a lot  » 6 weeks ago, # | +2 Can someone explain to me the 3D DP solution of Problem C , which is mentioned in the editorial . •  » » 6 weeks ago, # ^ | +3 dp[people==3000][levels==3][bits==32].For each candidate we need to decide what mask should I take. If in the final answer if we are considering the particular mask of a person then obviously the lowest valued power of that particular person will come out in the final answer.Second thing we have to do is calculate the max value of a particular mask+level along the iteration. We also have to keep in mind if you are replacing some mask value of with another mask , if some information that might be used further is not lost (basically if our transition is not losing any information that can be use further).I would encourage you to simulate whole process with same problem diff constraints , i.e we have to choose 2 person and each have 3 powers only(power > # of people to choose).https://atcoder.jp/contests/zone2021/submissions/22254672  » 6 weeks ago, # | ← Rev. 2 → +17 F: Random solution passed the tests, just take vertices randomly vertices and take all edges incident to them and find any possible spanning tree. This way by taking around 40*n edges passed the time limit. Code •  » » 6 weeks ago, # ^ | +3 The time complexity of this code is O(40*n*(n-m)) Since 40*n times getting the random variable. and (n-m) valid elements with which we take xor to get the adjacency list. Can you try explaining why it still passes. •  » » » 6 weeks ago, # ^ | ← Rev. 2 → +3 No i am taking 40*n edges only, like start taking random nodes and take all possible edges of this node and whenever total edges cross 40*n stop everything. •  » » 6 weeks ago, # ^ | +8 This is so brilliant.  » 6 weeks ago, # | 0 F, "from each node, it is easy to see we can make a transition to other node if and only if their xor is some subset xor of this complemented set."Actually, I still do not see why this is. Can somebody explain with simple example?Let$B=(1,2)$, and$v_1\oplus v_2 = 1$and$v_3\oplus v_4 = 2$Then how can we see that$v_1$is somehow connected to$v_3\$ ?
 » 6 weeks ago, # |   0 can someone explain why the following editorial code for F works ,taking y as min of its xor with elements of elim,I tried randomly permutating elim when considering a new x and it fails the sol surprisingly so order matters int y = x; for(int b : elim) chmin(y, y ^ b); if(y){ base.push_back(x); elim.push_back(y); }