Zeus_459's blog

By Zeus_459, history, 2 months ago, In English

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:

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:

  1. Geothermal
  2. Nots0fast
  3. Kude
  4. tabr
  5. Kira_1234
  6. gupta_nitin

Div2:

  1. SpyCheese
  2. wifiii

Div3:

  1. tko919
  2. ilyaxa
 
 
 
 
  • Vote: I like it
  • +87
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

As a tester video editorialist, the problems are interesting and you will enjoy solving them.

»
2 months ago, # |
  Vote: I like it +18 Vote: I do not like it

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.

  1. Changing the internet connection (ISP). Different ISPs rely on different DNS at different times.
  2. Changing the browser (Chromium, Firefox, Safari). Different browsers have different policy on caching.
  3. Try clearing your system’s DNS cache.

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

sudo dscacheutil -flushcache; sudo killall -HUP mDNSResponder

For Windows,

ipconfig/flushdns
»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 .

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Gott it now :|.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

»
2 months ago, # |
Rev. 2   Vote: I like it +22 Vote: I do not like it

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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it +23 Vote: I do not like it

        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

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +20 Vote: I do not like it

    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.

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      DELETED

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can U please explain your observation for lucky Ali?

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it +9 Vote: I do not like it

      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
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can you please explain the logic behind your solution ?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

»
2 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Dear Codechef, Please improve your plag system.

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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?

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks for the explanation. Got the solution.

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    spy_codes Kindly change your name to spy_cheats .

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Redacted

»
2 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it +14 Vote: I do not like it

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