Dominater069's blog

Invitation to CodeChef Starters 154 (Rated upto 6 stars) — 2nd October
By Dominater069, 3 months 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

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

so jao sir

→ Reply
»
3 months 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
  • »
    »
    3 months 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
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

    let them cook

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

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

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

The contest starts in ~35 mins

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

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

→ Reply
  • »
    »
    3 months 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
    • »
      »
      »
      3 months 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
    • »
      »
      »
      3 months 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
      • »
        »
        »
        »
        3 months 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
      • »
        »
        »
        »
        3 months 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
    • »
      »
      »
      3 months 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
»
3 months 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
»
3 months 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
  • »
    »
    3 months 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
  • »
    »
    3 months 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
    • »
      »
      »
      3 months 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
»
3 months 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
»
3 months 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
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

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

For MINMAXPATHS, what's the proof that:

Spoiler
→ Reply
  • »
    »
    3 months 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