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)**

**Contest Link :** https://www.codechef.com/FZBZ2021

**Joining me on the organising panel are:**

**Admin:**Utkarsh Utkarsh.25dec Gupta**Setters:**Ronels ronels229 Macwan, Kaushal Kaushal_26 Solanki, Archit Alchemist_2019 Dalania, Vedant practice_2209 Shah

**Testers:**Samarth gupta_samarth Gupta, Manan mexomerf Grover, Adhish ak2006 Kancharla , Jaydeep Jaydeep999997 Machhi , Harsh harshrajani460 Rajani**Statement Verifier:**Sarthak to_be_or_not_to_be Ajmera

**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:** FizzBuzz Editorial

**UPD:** Editorial on Codechef will be published soon.

**UPD:** Congratulations to the winners!

**Div1:**

**Div2:**

**Div3:**

Auto comment: topic has been updated by Zeus_459 (previous revision, new revision, compare).As a

~~tester~~video editorialist, the problems are interesting and you will enjoy solving them.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.

You can look at https://www.a2hosting.in/kb/getting-started-guide/internet-and-networking/clearing-the-dns-cache-on-your-computer

Or these commands:

For Mac, open a terminal and run this command

For Windows,

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?

Sorry for late respose, no registration required on fest site.

Prizes for Div1:1st Prize: INR 5000

2nd Prize: INR 2500

3rd Prize: INR 1000

4th Prize: INR 500

5th Prize: INR 500

6th Prize: INR 500

For Div2 & 3 Participants:1st Prize : 1000

2nd Prize : 500

All the Prizes are open for all.

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?

The second condition doesn't hold true in this case.

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 .

The count is maintained, but the second condition is that: For each province having sena X, all provinces having sena Y, should be adjacent to it. This is not holding true in the case you mentioned. 5 is not adjacent to 2,3,4 in the graph.

Gott it now :|.

Utkarsh.25dec In problem kingdom attack Sample TC-1 why couldn't we place X at 4,5,2 .??? this satisfies all 3 conditions

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.

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.

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!).

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?

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

Oh got it now, thanks for the detailed explanation.

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$$$.

Thanks. I forgot that since the previous $$$7$$$ states are all relative and not absolute, all $$$8$$$ possible placements are valid.

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.

DELETED

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.

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

I have done exactly the same. To check if a component (of x nodes) is a complete graph or not, I checked if the sum of count of all edges from every node in the component is equal to x*(x-1) [since every edge will be counted twice in the sum]. I also handled the case that x cannot be 1, and that the input graph isn't complete itself. I got WA though (my submission). Can someone let me know what about my code is incorrect? Is the way I determine if a component is fully connected correct?

Can U please explain your observation for lucky Ali?

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.

CodeAlso, what would be their codeforces ratings according to you?

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 :(

You missed the third condition, i.e., you must place at least 1X and 1Y.

F

Can you please explain the logic behind your solution ?

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

Dear Codechef, Please improve your plag system.

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?

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

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?

Graph constructed by erased edges .

Thanks!

AlexLorintz , can you please explain this observation that why is ans = number of connected components in compliment(erased) graph which are cliques ?

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.

Thanks for the explanation. Got the solution.

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 submission

This is some other cheater's submission

All the submissions of KINGATCK towards the end of round are exactly the same :( . Why doesn't codechef do any plag check ?

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.

spy_codes Kindly change your name to

spy_cheats.Auto comment: topic has been updated by Zeus_459 (previous revision, new revision, compare).Auto comment: topic has been updated by Zeus_459 (previous revision, new revision, compare).Redacted

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 :)).

Just codechef things

Auto comment: topic has been updated by Zeus_459 (previous revision, new revision, compare).