### chokudai's blog

By chokudai, history, 5 weeks ago,

We will hold Sciseed Programming Contest 2021（AtCoder Beginner Contest 219）.

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

We are looking forward to your participation!

• +69

 » 5 weeks ago, # |   +73 One of the best educational contests. Thanks atcoder!
 » 5 weeks ago, # |   +44 What a action packed day tommorow :0 ABC -> CF -> kickstart back to back with around 30 min break in between each of them.
•  » » 5 weeks ago, # ^ |   0 Leetcode Biweekly->Am i a joke to u?
•  » » » 5 weeks ago, # ^ |   +38 Spoiler
 » 5 weeks ago, # |   +10 so the recent AtCoder rounds have two extra problems than the regular ones we used to, these two problems have 500, 600 difficulty, maybe it worth increasing the contest time a little?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Idk why downvotes, so retracting it!
 » 5 weeks ago, # |   -26 Hope this contest will bring good luck to me in CSP-S 2021 (1st round) tomorrow :)P.S. If you don't know what CSP is click here
 » 5 weeks ago, # |   +20 HardCoder
 » 5 weeks ago, # | ← Rev. 2 →   +3 For me C/D was too hard according to previous :( Ho to solve D ?
•  » » 5 weeks ago, # ^ |   +3 felt really good after solving today's C ...actually the given string can be compared with abcde....z and then normal sort function can be used ... got it after 30 minutes ...but felt really good after solving :D
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 i did the same xDconvert given string to abcdef--- and again convert from abcdef-- to given string :3
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +12 D was dp.$dp[i][j][k]=$minimum no. of meals we can buy from first $i$ meals so that we have at least $j$ items of first type and $k$ items of second type.Transitions:$dp[i][j][k]=min(dp[i-1][j][k],1+dp[i-1][j-a_i][k],1+dp[i-1][j][k-b_i],1+dp[i-1][j-a_i][k-b_i])$ Code#include using namespace std; int main(void){ int n,x,y; cin>>n>>x>>y; int a[n],b[n]; for(int i=0;i>a[i]>>b[i]; int dp[n+1][x+1][y+1]; memset(dp,0x3f,sizeof dp); for(int i=0;i<=n;i++) dp[i][0][0]=0; for(int i=0;in) dp[n][x][y]=-1; cout<
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 what do transitions mean with fixed k and fixed j?(when we take only one part of lunchbox or something)
•  » » » » 5 weeks ago, # ^ |   +3 It means that we take the $i-th$ box but count only the items of first or second type.
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Hey, can you explain why this discrete dp doesn't work? I mean when ith lunchbox is taken then we will only get a[i] and b[i] (which is discrete). I don't understand why we are doing continuous dp, over here. It would a great help. Thnx. codeint dp[301][301][301]; int a[301], b[301]; int n, x, y; int solve(int i, int tako, int tai) { if(tako >= x && tai >= y) { return dp[i][tako][tai] = 0; } if(i >= n) return inf; int &res = dp[i][tako][tai]; if(res != inf) return res; res = min(solve(i+1, tako, tai), solve(i+1, tako+a[i], tai+b[i]) + 1); return res; } int32_t main() { FIO; cin >> n >> x >> y; int p = 0, q = 0; for (int i = 0; i < n; ++i) { cin >> a[i] >> b[i]; p += a[i], q += b[i]; } if(p < x || q < y) { cout << -1; return 0; } for (int i = 0; i < 301; ++i) for (int j = 0; j < 301; ++j) { for (int k = 0; k < 301; ++k) { dp[i][j][k] = inf; } } cout << solve(0, 0, 0); return 0; } 
•  » » » 5 weeks ago, # ^ |   0 This gives WA on the test cases added after contest.
•  » » » » 5 weeks ago, # ^ |   0 Hello, thanks for reminding, it was a small mistake in loop, I corrected it now :)
•  » » 5 weeks ago, # ^ |   +1 basically knapsack like dp
•  » » 5 weeks ago, # ^ |   0 D can be solved using Dynamic Programming. Approach: Let dp(i, j, k) be the minimum number of boxes to eat from first i boxes in order to get j octopus balls and k fish-shaped cakes. The transitions will be dp(i, j, k) = min( 1 + dp(i - 1, min(x, j + a[i]), min(y, k + b[i])), dp(i - 1, j, k) ) . Where x and y are X and Y (given as inputs) SubmissionRecursion + Memoization
•  » » » 5 weeks ago, # ^ |   0 Hi, Could you please tell the significance of min(x,j+a[i]) and min(y,k+b[i]) in your code? I wrote just 1+dp(i-1,j+a[i],k+b[i]) and got WA / RE etc. How does it affect the logic?
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 Hello!See the constraints given in the problem. It's N <= 300 and Ai, Bi <= 300 which means (j + a[i]) and / or (k + b[i]) can go upto 300 * 300 which results in RE(due to out of bounds). But, think what happens when (j + a[i]) or (k + b[i]) becomes >= x or y? Whenever (j + a[i]) becomes >= x, we have achieved the goal of getting >= x octopus balls given in the problem. So, we can consider all values (j + a[i]) >= x as x (this is done to avoid Runtime Errors) since we just need to get any number of balls >= x and so we don't care if we have got > x balls or = x balls. The same applies to (k + b[i]) too. Hence, the reason I take min(x, j + a[i]) instead of (j + a[i]) is to make sure that this parameter never exceeds x.P.S: It took me 5 incorrect submissions to find this!
•  » » » » » 4 weeks ago, # ^ |   0 I see I see I understand it now! Thank you! Whoa 5 attempts, looks like a very important optimization!
•  » » 5 weeks ago, # ^ |   0 I solved Problem D using dp.
•  » » 6 days ago, # ^ |   0 C was not too tough. i have used first mapping of characters and then mapping of (new string to index value), and since map sort the string automatically ,we have to only print the string by second element of map.
 » 5 weeks ago, # |   +9 The implemention of E and F was so painful (at least for me) !!!!!
•  » » 5 weeks ago, # ^ |   0 How did you solve F? Can you share?
 » 5 weeks ago, # |   +3 Can someone share a neat implemeantaion of pE?
•  » » 5 weeks ago, # ^ |   +1 Sure!Here is my code for solving problem E.Feel free to ask if there's any unclear part to my code.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Here is the clean code for E, I have added comments for better understanding Code
 » 5 weeks ago, # |   +6 For me the gap from D to E was big. Solved A-D in like 30 minutes, than did not found any clear idea for E or F.
 » 5 weeks ago, # |   +3 How to solve G — Propagation?
•  » » 5 weeks ago, # ^ |   +11 Similar to brute force approach. The bottleneck of the brute force approach is when x has a lot of neighbours, updating all the neightbours will take long. So we need to deal with these type of nodes separately.Call a node x big if the number of it's neighbours is >= sqrt(2e5). There are very few nodes of this type. So, the idea is to maintain an array of pairs last_propagation for the big nodes. If qi is the last query when a big node b appeared as a query, then last_propagation[b] will be equal to (value of node b at that the time of the query, qi).We also always keep the values of these big nodes updated as we process each of the queries sequentially. But we're fine if the values of the small nodes are not always kept updated, since it won't take long to get their latest value using the last_propagation array.Then, to process the queries, consider two cases: If x is big, update it's last_propagation and also update it's big neighbours' values. If x is small, get it's latest value and then update all it's neighbours the brute force way. Here's my submission using this idea. Let me know if I need to clarify anything above.
 » 5 weeks ago, # | ← Rev. 2 →   +3 DELETED
 » 5 weeks ago, # |   +3 how tf solve A? I have 1 WA and can't get what's wrong...
•  » » 5 weeks ago, # ^ |   0 Maybe you missed "If, however, his rank was Expert, print "expert", ..."I did, for one penalty.
•  » » 5 weeks ago, # ^ |   0 Tell me that you are joking.If not share your submission link
•  » » 5 weeks ago, # ^ |   0 You printed "expert" for n = 100But if n >= 90 then answer is "expert"
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +3 try writing expert in lowercase. atcoder is case sensitive
•  » » » 5 weeks ago, # ^ |   0 you better write atcoder not atocoder
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 okey guys, that's really funny, switch on C button is laggy on my keyboard, so I've sent the same wrong code twice))))))))))
 » 5 weeks ago, # | ← Rev. 3 →   +3 Why does this not work for G? (35x AC, 2x WA)Split nodes into "light" (degree $\lt \sqrt{m}$) and "heavy" (degree $\geq \sqrt{m}$).For each node we additionally keep track of all adjacent heavy nodes.For light nodes, we directly push the result of a query to all of its neighbors after a query.Additionally for all nodes (heavy or light), when we have a query, we will check for any newer values from heavy neighbors.Remember to perform a heavy neighbour pull at the end for all nodes before printing the answer.This takes a total of $O(m + (n + q) \sqrt m)$ since there can be at most $\sqrt{m}$ heavy nodes in the graph by definition. Code#include #define int long long using pii=std::pair; using namespace std; const int maxn = 2e5 + 5; int n, m, q, u, v, x, ans[maxn], last_pushed[maxn], last_pulled[maxn]; vector adj[maxn], heavy[maxn]; int is_heavy(int x) { return x * x >= m; } void heavy_pull(int x) { for(auto v : heavy[x]) if(last_pushed[v] > last_pulled[x]) { ans[x] = ans[v]; last_pulled[x] = last_pushed[v]; } } void light_push(int x) { for(auto v : adj[x]) { ans[v] = ans[x]; last_pulled[v] = last_pushed[x]; } } void apply(int x, int curtime) { heavy_pull(x); last_pushed[x] = last_pulled[x] = curtime; if(!is_heavy(adj[x].size())) light_push(x); } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> q; for(int i = 0; i < m; i++) { cin >> u >> v; u--; v--; adj[u].push_back(v); adj[v].push_back(u); } for(int i = 0; i < n; i++) { ans[i] = i + 1; for(auto v : adj[i]) if(is_heavy(adj[v].size())) heavy[i].push_back(v); last_pulled[i] = last_pushed[i] = -1; } for(int i = 0; i < q; i++) { cin >> x; x--; apply(x, i); } vector order; for(int i = 0; i < n; i++) { heavy_pull(i); cout << ans[i] << " "; } cout << "\n"; return 0; } 
•  » » 5 weeks ago, # ^ |   +8 That's what I did, and it passed (code).
•  » » » 5 weeks ago, # ^ |   0 Oops, must be an implementation mistake somewhere then. Thanks for the info.
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 I am same to you, my code 35*ac ,2*wa ...
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +1 The heavy node value might be overwritten later on, thus you need to store the value, too. 6 5 3 1 2 2 3 3 4 3 5 3 6 3 1 2 
•  » » » » » 5 weeks ago, # ^ |   0 tks, i fixed it,and get ac..
•  » » » 5 weeks ago, # ^ |   0 Thank you, how do you know when to do heavy-light splitting? I'm having trouble identifying this type of problem
 » 5 weeks ago, # |   +1 lol i hate geometry problems
 » 5 weeks ago, # |   0 I need to go debug my E. My basic idea was to represent the board as a bitmask try all 2^16 bitmasks and check a) Do i cover the required cells? b) Are the cells i have connected? (used DSU) c) Does my polygon have any holes? (used DSU) d) Do i have any self intersections (i.e. corners where one pair of opposite diagonals are included and the other pair where there are not)? However, even on the sample, I'm coming up short on the count, so I'm overkilling boards somewhere.
•  » » 5 weeks ago, # ^ |   0 You don't have to use DSU for checking holes. You can simply do a bfs starting from an edge square that is empty and check if you can visit all empty squares without leaving any behind
•  » » » 5 weeks ago, # ^ |   0 Can you please share your code?
•  » » 5 weeks ago, # ^ |   +1 What do you mean by "self intersections", I did the following in my AC code:A mask is considered good iff: The selected nodes are connected and cover all $(i, j)$ with $a_{i, j} = 1$ All non-selected node components consist of at least one boundary cell. Code#include #define int long long using pii=std::pair; using namespace std; int a[16], visited[16], steps[4] = {-1, 1, -4, 4}; int is_valid(int x, int y) { return (y >= 0 && y < 16 && (x % 4 == y % 4 || x / 4 == y / 4)); } int is_valid_visited(int from, int pos) { return is_valid(from, pos) && visited[pos]; } void dfs(int x, int mask) { visited[x] = 1; for(auto s : steps) { int ne = x + s; if(is_valid(x, ne) && (mask & (1 << ne)) && !visited[ne]) dfs(ne, mask); } } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); int vert_ans = 1; for(int i = 0; i < 16; i++) cin >> a[i]; int ans = 0; int allon = (1ll << 16) - 1; for(int mask = 1; mask < (1ll << 16); mask++) { for(int i = 0; i < 16; i++) visited[i] = 0; int from = __builtin_ctz(mask); dfs(from, mask); int bad = 0; for(int i = 0; i < 16; i++) if(!visited[i] && (a[i] || (mask & (1ll << i)))) bad = 1; for(int i = 0; i < 16; i++) if((i / 4 == 0 || i / 4 == 3 || i % 4 == 0 || i % 4 == 3) && !visited[i]) dfs(i, (mask ^ allon)); for(int i = 0; i < 16; i++) if(!visited[i]) bad = 1; if(bad) continue; ans++; } cout << ans << "\n"; return 0; } 
•  » » » 5 weeks ago, # ^ |   0 Thanks. I must have a bug in my connected checker, as I agree that the self intersections check SHOULD not be necessary. I agree on the "hole-check" piece with you. I guess I'll go use it to discover my bug elsewhere, as it shouldn't be flagging anything.
•  » » » » 5 weeks ago, # ^ |   0 Finally found the bug: i<15 vs. i<16 in for loop termination condition. Painful :(.
•  » » » » 5 weeks ago, # ^ |   0 Attatching GO code here: Codefunc solve(A [][]int) int { targbm,root := 0,-1 for i:=0;i<4;i++ { for j:=0;j<4;j++ { if A[i][j] == 1 { targbm |= 1 << (4*i+j); root = 4*i+j } } } ans := 0 for bm := 0; bm < 1<<16; bm++ { if bm & targbm != targbm { continue } uf := NewDsu(17) numsq := bits.OnesCount(uint(bm)) for i:=0;i<12;i++ { if (bm & (1<
 » 5 weeks ago, # |   +22 God save me from tasks like this E. Only you and its author know which moat is considered correct.
•  » » 5 weeks ago, # ^ |   0 Kudos to the author of E for giving us such a painful experience of implementation hell ! xD!!
 » 5 weeks ago, # | ← Rev. 3 →   -13 Can someone help me with D) . I used knapsack . why is it wrong ? My Codevector< vector > dp(n + 1, vector((x + 1)*(y + 1), mod)); dp[0][0] = 0; for(ll i=1; i<=n; ++i) { for(ll j=1; j<=(x)*(y); ++j) { ll cur_y = j / (y + 1); ll cur_x = j % (y + 1); dp[i][j] = dp[i-1][j]; if(cur_x >= a[i-1] && cur_y >= b[i-1]) { dp[i][j] = min(dp[i][j], dp[i-1][(cur_x - a[i-1])*(cur_y - b[i-1])] + 1); } } } if(dp[n][x*y] == mod){ cout << -1 << "\n"; return; } cout << dp[n][x*y] << endl; 
•  » » 5 weeks ago, # ^ |   0 The sum of the number of snacks can exceed 300.
•  » » » 5 weeks ago, # ^ |   0 i have 300*300 = 90000 states as columns (all possible pairs of (x, y)) that's why i initialised dp as dp(n, vector((x + 1) *(y + 1)))So i have covered all states right ?
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Nope, check this test case:2 300 300 250 250 300 100Here, we would need a state to represent (550, 350), which is not covered in your code.
•  » » » » » 5 weeks ago, # ^ |   0 okay thanks a lot :)
 » 5 weeks ago, # |   0 How to solve D, I got the easy $O(n^{4})$ dp, optimized it like hell for it to pass. What was the $O(n^{3})$ idea?
•  » » 5 weeks ago, # ^ |   +1 Just have a state that represents >300 for each snack instead of trying to use the actual values. So in total there should be $O(n^2)$ states which should result in $O(n^3)$ solution
•  » » 5 weeks ago, # ^ |   0 dp[i][j][k] = most taiyaki I can get after taking j of first i boxes and having k takoyaki. i did forward DP, but either need to be careful on order to avoid double counting or push updates to a queue-stack and do them at the end.
•  » » » 5 weeks ago, # ^ |   0 yaa this is exactly what I also did, need to be careful with optimization.
 » 5 weeks ago, # |   0 What a joke.solve a and b less than 5min. Then just WA-WA-WA-WA
 » 5 weeks ago, # |   0 Please someone explain why this comparator doesn't work? for C. bool co(const string s,const string t){ p=sz(s),q=sz(t); i=0; while(i
•  » » 5 weeks ago, # ^ |   0 If one of the strings is a prefix of the other one you return false. But that should be true or false, depending on which string is shorter.
•  » » » 5 weeks ago, # ^ |   0 Sir,can you give me an example plz?for input: zyxwvutsrqponmlkjihgfedcba 4 z zy zyxv zyxwvu My output: z zy zyxwvu zyxv 
•  » » » » 5 weeks ago, # ^ |   0 The comparison function needs to return true if the first string is lex smaller than the second. So it returns the wrong value if the first string is a prefix of the second. Because then the first one is lex smaller, but the return value is false. But should be true.
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   0 I used this as a comparator in the sort function, preety similar to yours Solutionmap mp; bool comp(string a,string b){ int n=min(a.size(),b.size()); for(int i=0;i mp[y]){ return false; } } if(a.size() <= b.size()){ return true; } return false; } 
 » 5 weeks ago, # |   0 This is my code for problem D, can somebody give me a counter test for this code? I got 40/50 test passed at atcoder. Codevoid solve() { int n, x, y; read(n, x, y); vector> v(n); for(auto& p : v) read(p.first, p.second); const int mxN = 650; vector> dp(mxN + 1, vector(mxN + 1, n + 10)); dp[0][0] = 0; for(int i = 0; i < n; ++i) { for(int j = mxN; j >= v[i].first; --j) { for(int k = mxN; k >= v[i].second; --k) { dp[j][k] = min(dp[j][k], dp[j - v[i].first][k - v[i].second] + 1); } } } int ans = n + 10; for(int i = mxN; i >= x; --i) for(int j = mxN; j >= y; --j) ans = min(ans, dp[i][j]); if(ans > n) cout << "-1\n"; else cout << ans << "\n"; } 
 » 5 weeks ago, # |   0 This is the first time I didn't solve C. Can someone tell me what is wrong with my implementation? I have written it 12 min after the competition has started and didn't find wrong test till the end of the contest, but I have only 2 AC https://atcoder.jp/contests/abc219/submissions/25932882
•  » » 5 weeks ago, # ^ |   0 Did you find out what's wrong? I am having similar issue, here's my implementation
 » 5 weeks ago, # | ← Rev. 2 →   0 problem D — can anyone guide me where my logic getting wrong? top-down implementation Spoiler#include using namespace std; int inf = 400; vector> vec; vector dp; int mintiffin(int n, int x, int y){ if(x<=0&&y<=0) return 0; if(n<0) return inf; if(dp[n]>=0) return dp[n]; int j = mintiffin(n-1,x-vec[n].first,y-vec[n].second)+1; int i = mintiffin(n-1,x,y); //cout << i << " " << j << endl; dp[n] = min(i,j); return dp[n]; } void solve(){ int n;cin>>n; int x,y;cin>>x>>y; vec.resize(n); dp.resize(n,-1); for(int i=0;i>vec[i].first>>vec[i].second; } mintiffin(n-1,x,y); int mn = 400; for(int i=0;i>T; while(T--){ solve(); if(T)cout << endl; } return 0; } 
•  » » 5 weeks ago, # ^ |   0 Here is my top-down implementation, you can go through it.
•  » » » 5 weeks ago, # ^ |   0 I understood top-down but I am curious to know where my logic is getting wrong.
•  » » » » 5 weeks ago, # ^ |   0 You should memorize x and y also because the same value of n can give different answers due to different values of x and y.Then your answer will be dp[n][x][y].
 » 5 weeks ago, # |   +11 I immediately related to Xenia and tree the moment I read problem G. Kudos to the authors for a really educative problem.
 » 5 weeks ago, # |   0 How to solve Problem G?
 » 5 weeks ago, # |   0 I feel like E is a little easier than D, because I think D is related to DP while E is related to brute-force.After some observations, you can figure out the solution to E, but for a beginner coder like me, I just couldn't figure out a way to solve D.Even though I didn't solve E in time, I still feel happy that it's at least solved in the end.Here's my video during the contest.
 » 5 weeks ago, # |   +5 Pretty boring, expected better from an ABC round :/
 » 5 weeks ago, # |   0 Alternate solution to $G$: We keep a bucket of size $\leq \sqrt{M}$ that stores {vertex, update_value} pairs that we haven't updated in the graph yet. When the size of this bucket becomes $\sqrt{M}$, then we iterate through every element in it and update the whole graph correspondingly. When we add a new vertex to the bucket, then search through each element in the bucket and find its updated value based on that. Total time complexity should be $O(N + Q\sqrt{M})$ or something, but my code is still TLEing on some cases. Is it because of using ordered_set?
 » 5 weeks ago, # |   0 Can someone please explain E a bit more, I have watched many sybmissions but not getting it