### Zeus_459's blog

By Zeus_459, history, 14 months ago,

Hello People!

We, are thrilled to invite you all to FizzBuzz 2021 ,rated for Div. 2 & Div. 3 participants. FizzBuzz, a competitive programming contest is organized by i.Fest — Gujarat’s Largest Technical Fest. i.Fest ‘21, the Annual Technical Fest of DA-IICT consists of 15+ events conducted over a span of 3 days (26th Nov- 28th Nov). Go and check out the official website of i.Fest ‘21 for more details: go here.

Time : 9 PM IST to 12 PM IST (Today)

Joining me on the organising panel are:

We would like to thank CodeChef for providing us the platform to host our contest. We would also like to thank the entire Codechef Team for their invaluable feedback and for their excellent coordination.

Good luck to all the participants!

Hope to see you participating!!

UPD: Editorial on Codechef will be published soon.

UPD: Congratulations to the winners!

Div1:

Div2:

Div3:

• +87

| Write comment?
 » 14 months ago, # |   +4 Auto comment: topic has been updated by Zeus_459 (previous revision, new revision, compare).
 » 14 months ago, # |   +3 As a tester video editorialist, the problems are interesting and you will enjoy solving them.
 » 14 months ago, # |   +18 Our domain expired on Wed, 24 Nov and we had to transfer our domain to different name servers to renew it. DNS takes a while to propagate across the internet. And thus, many of our users faced issues connecting. We sincerely apologize for this. It should be fine for most users now, but in case you are or anyone you know is still facing issues, you can try the following things. Changing the internet connection (ISP). Different ISPs rely on different DNS at different times. Changing the browser (Chromium, Firefox, Safari). Different browsers have different policy on caching. Try clearing your system’s DNS cache. Or these commands:For Mac, open a terminal and run this command sudo dscacheutil -flushcache; sudo killall -HUP mDNSResponder For Windows, ipconfig/flushdns 
 » 14 months ago, # |   +3 Registrations for prizes: NA Just to clarify, this means that we don't need to register on the fest site or fill some other form to be eligible for prizes right? Also since its not stated anywhere: Are the prizes for top 6 overall or top 6 Indians or top 6 of some other criteria? How will division rank lists be merged for prizes? Basically in Div1 do I have to solve problems from the non-scorable list or not?
•  » » 14 months ago, # ^ |   +1 Sorry for late respose, no registration required on fest site.Prizes for Div1: 1st Prize: INR 50002nd Prize: INR 25003rd Prize: INR 10004th Prize: INR 5005th Prize: INR 5006th Prize: INR 500For Div2 & 3 Participants:1st Prize : 10002nd Prize : 500All the Prizes are open for all.
 » 14 months ago, # | ← Rev. 2 →   0 Utkarsh.25dec In the problem kingdom attack : can two Y be adjacent? If yes, then in sample test 1, we can place X at node 5 and rest nodes we will fill with Y. Why this arrangement is false?
•  » » 14 months ago, # ^ |   0 The second condition doesn't hold true in this case.
•  » » » 14 months ago, # ^ |   0 But why not as Second Condition states there should be at least one X and and one Y and here cnt(X) = 1 & cnt(Y) = 5 .
•  » » » » 14 months ago, # ^ |   +1 Gott it now :|.
 » 14 months ago, # |   0 Utkarsh.25dec In problem kingdom attack Sample TC-1 why couldn't we place X at 4,5,2 .??? this satisfies all 3 conditions
•  » » 14 months ago, # ^ |   +4 If you take $X$ as : ${4,5,2}$, then $Y$ is ${1,3,6}$. Here, $5$ is not adjacent to $3$, hence it violates the second condition.
 » 14 months ago, # | ← Rev. 2 →   +22 Thoughts on the problems:Can You Eat It — ABC level cakewalk, no real comments.Can_Reach — Decent cakewalk, but even if the independenace of coordinates was the key point, I have to question the logic of putting it in the same contest as the previous problem.Magical Planks — Decent problem, but "this process continues for the newly colored planks" should really have been highlighted or the example in the statement should have had a block of size > 3.Substring Minimum Function — Decent idea, easy to implement, maybe a bit standard.Clean The Sequence — Cool problem, nice observations about the endpoints of ranges.Kingdom Attack — Interesting problem which looked super tough to me till I realized the approach. I have to ask seeing the solve count though, is the intended hashing the set $(1, 2, \ldots, n)$ and removing the nodes of destroyed edges to get the hash of the adjacent nodes or is there a simpler approach?.Lucky Ali — Cute problem, I like the observation that we only need to update a single row / single column of the dp grid per query. Surprised the solve count is as low as it is, took me less time to logically solve this than the previous problem.Sweet Change — Looks cool, unfortunately ran out of time by the time I reached here. It feels like connected components dp while maintaining the additions on the sides of each connected component somehow, but I can't think of an exact approach so I might be totally wrong.
•  » » 14 months ago, # ^ |   +18 in Sweet change, for ith position you only need order(in which we eat them) of no more that 7 last element,so can be solved using dp with number of state being n*(7!).
•  » » » 14 months ago, # ^ |   0 What are the $7!$ states here? Are they a relative ordering of the visit times of the last $7$ states? If so when we have these values for the previous $7$ positions before the position $i$, how do we figure out how many are smaller / larger than the visit time of $i$ ? Do you mind elaborating a bit?
•  » » » » 14 months ago, # ^ | ← Rev. 2 →   +23 Apologies for unclear statement, as max value of d[i] is 7, if we know answer of l length prefix then we can expand it to get the answer of l+1 length prefix, but for it we need the order the previous 7 element ( l,l-1,l-2...l-6), in which we eat them. now we can put l+1 th element inbetween 8 position among these 7 element. so dp state is the [index , order of previous of 7 element], now order of previous 7 element can be among 7! ways in which we can order them. So number of states can be upto n*7!. code
•  » » » » » 14 months ago, # ^ |   +5 Oh got it now, thanks for the detailed explanation.
•  » » » » 14 months ago, # ^ |   +8 We iterate over $8$ cases for the position of $i$ relative to the previous $7$ states. This allows us to uniquely determine which previous states contribute to the tastiness of state $i$ and the number of previous states to which state $i$ contributes tastiness: in other words, we're counting contributions from $j$ to $i$ and from $i$ to $j$ for all $j < i$, which will account for the full answer once we iterate over all $i$.
•  » » » » » 14 months ago, # ^ |   0 Thanks. I forgot that since the previous $7$ states are all relative and not absolute, all $8$ possible placements are valid.
•  » » 14 months ago, # ^ | ← Rev. 2 →   +20 For Kingdom Attack, the answer is number of components that are complete graphs (- the edge case when the given graph is a complete graph on its own ) , you can just check the number of edges for each component.
•  » » » 14 months ago, # ^ | ← Rev. 2 →   0 DELETED
•  » » » 14 months ago, # ^ | ← Rev. 3 →   0 Oops, I overkilled it then.I just noticed the problem was equivalent to the number of ways of partitioning the set of nodes $S = (1, 2, \ldots n)$ into two sets $X$, $Y$ such that the adjacency list of all nodes in $X$ is exactly $Y$ and counted that using hashing + maps.But clearly for this to occur, in the inverse graph, $X$ must be a disconnected complete graph so I don't know how I missed that.
•  » » » » 14 months ago, # ^ |   0 I had done the same thing as yours but it will not require hashing (just maps is enough).You can go through my small code here
•  » » 14 months ago, # ^ |   0 Can U please explain your observation for lucky Ali?
•  » » » 14 months ago, # ^ | ← Rev. 2 →   +9 Consider the initial problem of choosing non-overlapping subsequences. Lets call the two phone numbers $a$ and $b$ for convenience.We can calculate this using a dp on the minimum position $i$ in the magic string such that we can fit the first $x$ characters of $a$ and the first $y$ characters of $b$ in the range $[1, i]$. Lets define this as $dp[x][y] = i$.Now clearly, if we're placing the these first $x$ characters of $a$ and first $y$ characters of $b$, the last character placed will be the $x$-th character of $a$ or the $y$-th character of $b$. So $dp[x][y] = min(next[dp[x - 1][y]][a_{x}], next[dp[x][y - 1]][b_{y}])$, where $next[p][q]$ is the first occurrence of character $q$ strictly after position $p$ in the magic string. We can pre-calculate all values of $next$ in $O(n)$ time by processing the magic string $m$ in back to front order, so we can perform these transitions in $O(1)$ time.But this takes $O(|a| \cdot |b|)$ time to calculate, which is too slow to calculate for each query.But do we need to recalculate everything? What does appending / removing a value from a string constitute?The $i$-th row of the dp grid corresponds to the $i$-th position of $a$ and the $j$-th column corresponds to the $j$-th position of $b$. So adding / erasing a new digit to / from the end of the mobile number is equivalent to just adding / removing a new row or column to / from the dp.So we only have to evaluvate $|a|$ or $|b|$ new states, allowing each query to be performed in $max(|a|, |b|))$ time . So we can solve the entire problem in $O(n + d \cdot max(|a|, |b|))$ which is fast enough. Code#include #define int long long using pii=std::pair; using namespace std; const int maxlen = 1005, maxn = 5e5 + 5; int n, d, dp[maxlen][maxlen], ne[maxn][10]; string m; vector nums[2]; int get_next(int frompos, int val) { if(frompos >= n) return 2e9; return ne[frompos][val]; } int solve(int x, int y) { assert(x <= nums[0].size() && y <= nums[1].size()); if(dp[x][y] < -1e9) { int takepos = 2e9; if(x > 0) takepos = min(takepos, get_next(solve(x - 1, y) + 1, nums[0][x - 1])); if(y > 0) takepos = min(takepos, get_next(solve(x, y - 1) + 1, nums[1][y - 1])); dp[x][y] = takepos; } return dp[x][y]; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); for(int i = 0; i < maxlen; i++) for(int j = 0; j < maxlen; j++) dp[i][j] = -2e9; dp[0][0] = -1; cin >> n >> d >> m; int curne[10] = {0}; for(int j = 0; j < 10; j++) ne[n][j] = curne[j] = 2e9; for(int i = n - 1; i >= 0; i--) { curne[m[i] - '0'] = i; for(int j = 0; j < 10; j++) ne[i][j] = curne[j]; } for(int i = 0; i < d; i++) { string type, name; int val; cin >> type >> name; if(type == "append") { cin >> val; if(name == "Aryan") nums[0].push_back(val); else if(name == "Ali") nums[1].push_back(val); else assert(false); solve(nums[0].size(), nums[1].size()); } else if(type == "erase") { if(name == "Aryan") { assert(!nums[0].empty()); for(int i = 0; i < maxlen; i++) dp[nums[0].size()][i] = -2e9; nums[0].pop_back(); } else if(name == "Ali") { assert(!nums[1].empty()); for(int i = 0; i < maxlen; i++) dp[i][nums[1].size()] = -2e9; nums[1].pop_back(); } else assert(false); } else assert(false); if(dp[nums[0].size()][nums[1].size()] < n) cout << "YES\n"; else cout << "NO\n"; } return 0; } 
•  » » 14 months ago, # ^ |   +5 Also, what would be their codeforces ratings according to you?
 » 14 months ago, # |   0 How to solve Kingdom Attack ? I made a graph with the given edges and calculated count of connected component in which all the nodes of the component are connected to every other node by a proper edge . I also added number elements whose degree is n — 1 . Only 2 test passed :(
•  » » 14 months ago, # ^ |   0 You missed the third condition, i.e., you must place at least 1X and 1Y.
•  » » » 14 months ago, # ^ |   +5 F
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 Can you please explain the logic behind your solution ?
•  » » » 14 months ago, # ^ |   0 Suppose there be set of vertices (say k vertices) . Let's say we make these k vertices Y color. Now all the other one should be S colored and they must be disconnected among each of them as separation bw X should be there . So in order to be disconnected all the remaining (n — k) vertices should form a COMPLETE Graph from the erased edges(This constitutes a single Arrangement . If they do not form complete graph , then there must be two vertices which are connected and this violates 2 X adjacent to each other . Sorry for bad English
 » 14 months ago, # |   +2 Dear Codechef, Please improve your plag system.
 » 14 months ago, # | ← Rev. 2 →   0 For kingdom attack I used the following observation: an erased edge means that those edge's endpoints should have the same state(X or Y), then I created a new graph with the erased edges. It's clear that the previous observation extends to connected components of nodes in the new graph, so I said that the answer for the problem was the number of connected components of the new graph that are cliques, because I tried when counting solutions to fix the nodes having state X and I thought it's obvious that a connected component can have all the nodes equal to X if and only if it is a clique. Does anyone know what am I missing?
•  » » 14 months ago, # ^ |   0 The third condition i.e. when the whole graph is a clique . In this case you will have either all X's or all Y's
•  » » » 14 months ago, # ^ | ← Rev. 2 →   0 Are you reffering to the "almost-complete" graph or to the new one I construct with erased edges? EDIT: Nevermind, I just got it, what a stupid mistake. Why wasn't this case included in the samples?
•  » » » » 14 months ago, # ^ |   0 Graph constructed by erased edges .
•  » » » » » 14 months ago, # ^ |   +3 Thanks!
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 AlexLorintz , can you please explain this observation that why is ans = number of connected components in compliment(erased) graph which are cliques ?
•  » » » 14 months ago, # ^ |   +3 If you erase an edge from the graph, its endpoints can't have different states because of the condition that all Y's should be adjacent to an X. This implies that for a connected component, all of its nodes should have the same state, but it's not always possible to have a connected component with all X's. Consider in the sample, the connected component of 2, 3, 4 and 5, the edge 3-4 isn't present in this component so it still exists in the "almost-complete" graph from the statement, so because of the condition that 2 adjacent nodes can't have state X, this component can't have state X. Now it's easy to realize that for a connected component to have state X for all nodes it should be a clique(complete graph, so it doesn't have adjacent nodes in the complement graph and we are allowed to fill it with X). When a component's state is considered to be X, others components will not have state X because they are all connected with our component in the "almost-complete graph" from the statement, so all the others component will have state Y. Now it's clear that to count all the different solutions it's enough to count the number of connected components in the "erased-graph" which ale cliques.
 » 14 months ago, # | ← Rev. 2 →   0 Well this contest too witnessed a hell lot of cheating.I would like to point out a cheater whom I found out. spy_codes has been cheating since past few contests.This is his submissionThis is some other cheater's submission
•  » » 14 months ago, # ^ |   0 All the submissions of KINGATCK towards the end of round are exactly the same :( . Why doesn't codechef do any plag check ?
•  » » » 14 months ago, # ^ |   +3 The fact that KINGATCK had that very stupid case not included in the samples is let-alone very disappointing, at least the cheaters should be removed, because a lot of people have already lost enough in ranking.
 » 14 months ago, # |   0 Auto comment: topic has been updated by Zeus_459 (previous revision, new revision, compare).
 » 14 months ago, # |   0 Auto comment: topic has been updated by Zeus_459 (previous revision, new revision, compare).
 » 14 months ago, # | ← Rev. 3 →   0 It's just very funny that a lot of the last submitted solutions for Kingdom Attack in the contest are exactly the same, like I found 10 identical solutions and I stopped counting because I got bored(people didn't even bother to change variable names :)).
•  » » 14 months ago, # ^ |   0 Just codechef things
 » 14 months ago, # |   +14 Auto comment: topic has been updated by Zeus_459 (previous revision, new revision, compare).