Dominater069's blog

Invitation to CodeChef Starters 154 (Rated upto 6 stars) — 2nd October
By Dominater069, 5 weeks ago, In English

We invite you to participate in CodeChef’s Starters 154, this Wednesday, 2nd 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!

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

»
5 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

so jao sir

→ Reply
»
5 weeks ago, # |
  Vote: I like it +36 Vote: I do not like it

As a setter, participate or I will send an army of $$$10^9$$$ chefs to your home

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    Then I will solve all their problems one by one, and in return they will cook food for me and me and my friends would laugh the same way as your pfp

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

    As long as the chefs bring snacks, I'm ready

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

    let them cook

    → Reply
»
5 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

CF $$$1400$$$ $$$>$$$ CodeChef $$$2000$$$ for some reason :)

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

The contest starts in ~35 mins

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

Nice problems! I'm happy to AKed all. Thanks.

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

    can you find any issue for the code below: GCD and Xor

    Spoiler
    → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      Sorry, but ask it to gpt. I only can help your code.

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

      Add 1 or 2 Game : for N==1 alice wins else Bob wins

      GCD & XOR : observe we can greedily make all elements equal to 1 using X==1, and then make them equal to k using XOR operation with that particular X, which takes 2 operations at max. But if we have all equal to k then we don't have to make any operations so its equal to 0 , else if all are divisible by k then we have to make 1 operation else if all have same needed xor value then also we need 1 operation.

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

        did the same in the code, would be helpful if you check it. thanks

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

        should have thought of that making everything 1 by gcd (it was almost like using 1 to swap elements ,question in last contest) my baddd

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

      You're not checking if one of the numbers is k in case of two distinct values. Try this case.

      1
4 2
3 3 5 5
      → Reply
»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

cheatchef hogya aaj to 90% of div 2 participant have same code

→ Reply
»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve Tree Cut XOR if we had to maximize X instead of minimize it ?

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

    Let $$$x$$$ be the maximum integer, such that $$$2^x \le n-1$$$, then maximum value of $$$X$$$ can be $$$2^{x+1} -1$$$.

    Let do operations in the following way:

    Observe that we reach $$$2^x, 2^{x-1}, ... ,4, 2, 1$$$ while deleting leaves one by one

    If the number of leaves cut are odd at tree with size $$$4$$$, remove edges $$$1,2,1$$$(sub-tree size) otherwise remove $$$3,1,1$$$

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

    For a given value of $$$N$$$, the maximum value that $$$X$$$ can be xorred with is $$$N-1$$$. That gives an upper bound of $$$2^{\lfloor log_2(N-1)+1 \rfloor}-1$$$ on $$$X$$$. Consider $$$N = 4$$$. Note that any value of $$$0 \leq X \leq 3$$$ is obtainable. For $$$N > 4$$$, keep removing leaves till $$$N = 4$$$. After the removal of each leaf, let $$$siz$$$ denote the size of the remaining tree. Do $$$X = X \oplus siz$$$ if $$$siz$$$ is a power of $$$2$$$; $$$X = X \oplus 1$$$ otherwise. By this method, we can set all possible bits $$$\geq 2$$$ in $$$X$$$. Once $$$N = 4$$$, any combination of the last $$$2$$$ bits can be obtained. Thus, the upper bound is achievable for $$$N \geq 4$$$. The answers for $$$N = 2$$$ and $$$N = 3$$$ are $$$1$$$ and $$$3$$$ respectively.

    → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it 
      I have a little better way to explain: 

Let say current tree has n nodes,  partition leaf edge
      so we remain with  sz1 = 1  , sz2 = n-1

if n is odd ,  n-1 operation we want = even    so if initially xor = 0
   then   0 ^ (sz1 = 1) ^ (sz1 = 1) .... even time   = 0

if n is even , we can make xor = 1 by the above rule right
     but there is a catch , if n==2  xor = 1 is indeed the answer
                            if n > 2 xor = 0 is also possible

    Let see how ->   first thing  pertiton into sz1 =1  , sz2 = n-1  is still there
                            n    -->    n-1    --->    n-2
        (sz1 , sz2) =  (1 , n-1)     (1 , n-2)       (1 , n-3)

                    0 ^   (n-1)   ^   (n-2)  ^ (rest will be the same problem)
     (n-1)^(n-2) = 1

     So if you see that we start with (n =even , xor = 0)    -> apply type1 = 1 as final
     so got to                        (n-2 = even , xor =1)  -> apply type1 = 1^starting - 0
      → Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I had a doubt in COUNTWINSUB , like I interpreted it to find the number of subarrays which have more 1's than 0's , is this wrong ?

→ Reply
»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

You can check my video editorials of Count Winning Subarrays and Tree Cut Xor if needed

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

    Didn't think you'd participate. I guess holiday today :)

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

For MINMAXPATHS, what's the proof that:

Spoiler
→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    $$$a \cdot x + b \cdot y \ge min(a, b) \cdot (x + y) > min(a, b) \cdot max(x, y) $$$

    → Reply