satyam343's blog

By satyam343, 22 months ago, In English

We invite you to participate in CodeChef’s Starters 72, this Wednesday, 4th January.

Time: 8 PM — 11: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 for all users for 1 day as soon as the contest ends, after which they 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
  • +22
  • Vote: I do not like it

| Write comment?
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
22 months ago, # |
  Vote: I like it +25 Vote: I do not like it

Test comment. (Blog doesn't show up on recent actions)

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve No Sequence

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hint: attempt to set every element in the answer to 1 at first, then decrement when you need, some small optimization may be needed

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Cases $$$k = 1, 2$$$ are trivial. Notice that some element of $$$\{s - 1, s, s + 1\}$$$ should be divisible by $$$k$$$. Because $$$k \geq 3$$$ it must be exactly one element if solution exists. That way we found $$$b_1$$$. Solve recursively for others.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I have an easy intuitive solution for that.
    Just take a var = 0 and check for decreasing powers of K(from n-1 to 0), whether adding/subtracting this to/from var will result in bringing var closer to s. Fill suitably 1 or -1 at this index in the answer array, and modify var.
    After traversing all powers of K, if var != s, then print -2, else print the answer array.
    My submission
    Note why this works is because of the fact that K^N will always be greater than sum of K^(N-1) + K^(N-2) + .... + K + 1, so K^N will have the greatest hand in determining the closeness of var to required s.

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Bro why u have taken abs(curr + powers[i] — s) instead of s-powers[i]-curr

      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        You can take that also.
        It'll give the same result, abs() just compares the absolute difference.

»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Story of the contest: I am happy with my performance solving (only !) 2 problems in a div2 round, and not even a speed solve

»
22 months ago, # |
  Vote: I like it +16 Vote: I do not like it

did anyone solve XOR Tree using multiset(to find the greatest xor value of leaf)?

»
22 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Edit: I am deeply ashamed of myself to discover that I had an integer overflow in pre-computation.

How to solve Good Arrangements ?

My idea is to fix a starting value, and then using some combinatorics formula to calculate arrangements. Am I in the right direction ?

The formula I thought of:
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    We need to fix not only the starting element — $$$v$$$ but also the amount of it in the beginning — $$$c$$$. Then your formulas are almost correct

  • »
    »
    22 months ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    Try to fix the number of indices i such that b[i] is the prefix maximum, then, since we know that maximums will occur in increasing order and minimums in decreasing order, we only need to choose the indices where we will keep the maximums.

    there is a caveat, though, you need to make sure that all places other than the maximums will surely be minimums to avoid overcounting; try to figure that out, it isn't very hard.

  • »
    »
    22 months ago, # ^ |
    Rev. 3   Vote: I like it +8 Vote: I do not like it

    Yeah, your formula is correct