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:
Contest Admin, and Statement Verifier: Shreyan Dominater069 Ray
Tester: Sushil SmolBrain Raaja
Text Editorialists: Nishank IceKnight1093 Suresh
Setter: Shreyan Dominater069 Ray, Sushil SmolBrain Raaja, TheScrasse.
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!
OMG , TheScrasse Round !
again no 6 stars rated :( .
u 6 stars at CC?
yeah, kind of ...
I solved first 4 problems of div2 and got the rank 626 happy af
Well your wish came true
Thanks a lot <3 . Expected same from you bhai. Go LGM !!!!!
am i the one who choose which div i do ? or iam auto. assigned according to my rate?
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
Contest starts in ~25 Minutes
Was logic for MAKETREE to find out minimum possible colours we can use for bipartite edge colourings for the given tree ?
think about degree
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
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
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
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$$$.
Got it. Thanks for your explaination. But this approach and observations does not seems intutive to me.(maybe skill issues)
Yeah this doesn't seem that intuitive. The merging of elements starting from the smallest is more intuitive.