300iq's blog

Invitation to CodeChef October Long Challenge 2020
By 300iq, 4 years ago, In English

We invite you to participate in CodeChef’s October Long Challenge, this Friday, 2nd October, from 15:00 IST onwards. The contest will be open for 10 days i.e. until 12th October.

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. Joining me on the problem setting panel are:

Prizes:

P.S: For October Long Challenge, we won't be having any tie-break Challenge problem. So, instead of giving the usual cash prizes to the top-ranked users, we will give laddus, which help in the fair distribution of reward. For the Indian rank list, we'll distribute 5000 laddus amongst all the top-scorers. For the Global rank list, we'll distribute 13000 laddus amongst all the top-scorers. The top 20 performers in the Indian category and top 10 performers in the Global category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. First to solve each problem except challenge — 100 laddus. Know more here

Good Luck!
Hope to see you participating!

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

Comments Comments (21)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it -31 Vote: I do not like it

...

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

ROOTMST was very interesting!

My approach
→ Reply
»
4 years ago, # |
  Vote: I like it +22 Vote: I do not like it

For October Long Challenge, we won't be having any tie-break Challenge problem.

Was that an intentional decision or just a lack of good problem?

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

300iq orz. Great contest!

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

how to INVSMOD2?

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

I AM NOT ASKING FOR SOLUTION NOR TELLING ANSWER.

in the 3rd ques. it is giving TLE just for printing array(i was using java)??? why so?

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

Can anyone explain D-Dimensional MST, editorial is not written properly for that question?

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

    Both, DDIMMST https://discuss.codechef.com/t/ddimmst-editorial/79385 and ADDSQURE https://discuss.codechef.com/t/addsqure-editorial/79023 are badly understandable.

    In DDIMMST the key is to find a fast way (faster than O(n^2)) to identify edges with the biggest distance among a group of edges. The tutorial explains a way to "somehow" do this with masks.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -31 Vote: I do not like it

      I think that editorials are well-written. If you have any questions, ask the exact question in the editorial blog.

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

    I think this comment explains the key point.

    It refers to the tutorial of 1093G - Multidimensional Queries

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

      Can you pls explain i couldn't understand , i have the similar doubt as that author ? What i don't understand is if i query max for all the ci's then i need to sure that that max is actually present in the original segment ?

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

        I will try to explain with my words, but I am not sure about it.

        We create $$$2^d-1$$$ vectors of numbers. In each vector j we calculate for each point i a value p[i][j]. That value is calculated as the sum of the coordinates of that point. But some are added, some are subtracted. Since we do this for each of the $$$2^d-1$$$ masks, the vectors include all possible combinations of add and subtract.

        Let $$$\tilde{}$$$ be the bitwise not operation. ie, if we add a dimension $$$d_x$$$ in vector $$$j$$$, then we subtract that dimension in vector $$$\tilde{}j$$$

        Then we sort all the vectors, and foreach vector we calculate the difference between the first (ie the biggest) value of that vector, and the smallest value of the "bitwise opposite" vector, which is $$$abs(p[0][j] - p[i-1][\tilde{}j])$$$

        The biggest of these differences is the biggest distance of two of the i points. And the two points are those where we found that value.

        Actually we can directly search for min and max value in the vectors instead of sorting, with O(n) complexity instead of O(logn)

        → Reply