Блог пользователя 300iq

Автор 300iq, 4 года назад, По-английски

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!

  • Проголосовать: нравится
  • +131
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -31 Проголосовать: не нравится

...

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

ROOTMST was very interesting!

My approach
»
4 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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?

»
4 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

300iq orz. Great contest!

»
4 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

how to INVSMOD2?

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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?

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -31 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think this comment explains the key point.

    It refers to the tutorial of 1093G - Многомерные запросы

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 ?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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)