Dominater069's blog

Invitation to CodeChef Starters 158(Rated upto 6 stars) — 30th October
By Dominater069, 3 weeks ago, In English

We invite you to participate in CodeChef’s Starters 158, this Wednesday, 30th October, rated upto 6 stars (i.e. for users with rating < 2500)

Time: 8:00 PM — 10:00 PM IST

Joining us on the problem setting panel are:

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here. Hope to see you participating.

Good Luck!

UPD 1: The following is the number of problems:

  • Div1 : 5 problems + 1 subtask
  • Div2 : 7 problems
  • Div3 : 7 problems
  • Div4 : 8 problems

UPD 2: The contest got changed to rated upto 6 stars. I am sorry for the late change. We decided it was hard enough for 6 stars.

UPD 3 : Congratulations to Top 5!

  • Vote: I like it
  • +63
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

OMG , TheScrasse Round !

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

again no 6 stars rated :( .

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

am i the one who choose which div i do ? or iam auto. assigned according to my rate?

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    u will ve auto assigned which goes like this 1 star div 4, 2 star div 3, 3 and 4 star div2 5 star and above div 1

    → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Contest starts in ~25 Minutes

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Was logic for MAKETREE to find out minimum possible colours we can use for bipartite edge colourings for the given tree ?

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    think about degree

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yes i thought about max degree but my
      but couldn't figure the implementation details
      is it like in each operation pick the nodes having max_degree and connect there atleast one edge

      → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes , I saw the editorial. But my thought process was find the minimum colourings required so that no two incident edges have same colour. Then I iterate over 1 to k and update my array(same logic as in editorial). But unable to prove why its wrong

      → Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone plz explain the other approach discussed in editorial of multiply 2 to minimise .

particularly this :

There are other approaches too. For instance, one way is to also allow for “reversing” the process, meaning we can break a copy of $$$2x$$$ into two copies of $$$x$$$ (which doesn’t make the answer any worse). Repeatedly perform this reverse operation till every number in the array is odd. Then, for an odd number that appears $$$k$$$ times, simulating the forward process should show you that the number of distinct values you end up with is exactly $$$\text{popcount}(k)$$$, that is, the number of bits set in $$$k$$$.

Editorial link

→ Reply
  • »
    »
    3 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    it say's that suppose for a time you have an array $$$A$$$ which consists of only odd numbers
    suppose frequency of particular odd number in array $$$A$$$ is $$$k$$$ so we separate these similar odd number in $$$popcount(k)$$$ blocks such that size of each block is in powers of $$$2$$$
    so if you apply operation only in one block repeatedly you will end up having only only element in that block

    for example $$$A$$$ = {1,3,3,3,3,3,3,5}
    so there are $$$6$$$ $$$3s$$$, we will divide them in blocks of size $$$2$$$ and $$$4$$$
    {3,3}, {3,3,3,3}
    now if you consider applying operation in each block separately you will end up having
    {6}, {12} = {6, 12} so at the end you have $$$2$$$ distinct elements as no. of set bits in $$$6$$$.

    → Reply
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Got it. Thanks for your explaination. But this approach and observations does not seems intutive to me.(maybe skill issues)

      → Reply
      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah this doesn't seem that intuitive. The merging of elements starting from the smallest is more intuitive.

        → Reply