Блог пользователя Zeus_459

Автор Zeus_459, история, 3 года назад, По-английски

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
  • Проголосовать: нравится
  • +87
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +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.

  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
»
3 года назад, # |
  Проголосовать: нравится +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?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

»
3 года назад, # |
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?

»
3 года назад, # |
  Проголосовать: нравится 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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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.

»
3 года назад, # |
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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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!).

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 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?

      • »
        »
        »
        »
        3 года назад, # ^ |
        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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +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$$$.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
    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.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      DELETED

    • »
      »
      »
      3 года назад, # ^ |
      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.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can U please explain your observation for lucky Ali?

    • »
      »
      »
      3 года назад, # ^ |
      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
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 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 :(

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Can you please explain the logic behind your solution ?

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 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

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Dear Codechef, Please improve your plag system.

»
3 года назад, # |
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?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 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

  • »
    »
    3 года назад, # ^ |
    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 ?

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +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.

»
3 года назад, # |
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 submission

This is some other cheater's submission

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +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.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
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 :)).

»
3 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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