Invitation to Decathlon

Hello Codechef,

Are you the kind of person who spends sleepless nights learning new algorithms. Do you use data structures as if it’s your pen? And do you speak code?

It’s time to hone your problem-solving skills. Get ready with your laptops and put your brains in use cause this Aarohan 2020, we bring you again our very own coding challenge Decathlon where you will be put to test against some of the best coders. So bring out the gladiator within you and put the destruction mode on 9th February 2020 at 10 pm.

The contest will be held on the Codechef platform.

The contest consists of 6 problems to be solved in 2:15 hours.

Setter - Ritesh Gupta
Tester - Subhadeep Chandra

There are exciting prizes for winners:

  • Overall First Prize: Rs 3000/-
  • Overall Second Prize: Rs 2000/-
  • Overall Third Prize: Rs 1500/-
  • Top Three from Ranklist will get CodeChef Laddus.
  • Certificate and other exciting fest goodies.

#Aarohan2020
#TeamAavishkar

9 Likes

Looking forward to it!

Unrated ?

@above, the contest will be unrated. BTW, excited to participate :slight_smile:

It seems that you cant see the submissions of problems you didn’t solve.
Can you please add problems in practice section?

Btw what was the soln of DECOPAIR?

My Soln

Seems doable with MO in O(N*sqrt(N)*logN). Not sure If its TLE.

There were multiple mistakes in Sums question’s statement. Thats why many people got WA. I suggested many times in comments to clarify/change it but you guys replied “No-comments”. I guess finally after 1-hour question was updated, that you have to print “-1” in case no subarray exists.(also a(i)>=0)…Still 2-3 guys managed to get AC without this info … Just Wow…( Not very pleasant experience. )

1 Like

I solved it with MO, using block size = 500 and soln with block size = sqrt(n) TLE’d.
So ig the intended soln is not MO.

It passes by Mo’s in \mathcal{O}(n \sqrt {n}) (0.3 secs).
You can add/erase elements to left/right in \mathcal{O}(1).
Just maintain sum of indices and frequency for each distinct element in current range.

The other AC solutions to this problem are not visible to me too.

The changes in constraints of Sums problem were very late. No one answered my comment asking if the constraints were wrong, and whether negative numbers are allowed if they were wrong. Wasted too much time (and penalty) on it.

What was the block size you used?
My Java soln with same complexity takes 5.3 secs.

Same here. I wonder how people got AC when it was not mentioned for more than an hour that you gotta print “-1” in case no valid subarray found…

I just used \sqrt{10^5}. I also used odd-even trick while sorting.

1 Like

Could you please say more about odd-even trick ?

I don’t know whats its official name, if any. Its basically this

sort(idxs.begin(), idxs.end(), [&] (int i, int j) {
  int bi = L[i] / MAGIC, bj = L[j] / MAGIC;
  if (bi != bj) return bi < bj;
  if (R[i] == R[j]) return L[i] < L[j];
  return bi & 1 ? R[i] > R[j] : R[i] < R[j];
});

Sort the queries by increasing R_i in 1st block, decreasing in 2nd, and so on.
It reduces the total operations by about half.

2 Likes

Hey all,

Sorry for the problem Chef and Sum. I updated the statement earlier but forgot to sync it with the on-line contest. Apart from that, I assume that all of you like problems. Please provide your feedback about the problems.

1 Like

Can you please explain about this trick a bit more? Or any link explaining this will also be helpful.

It is fairly well known I think. @meooow has one explanation here Query regarding Mo's Algorithm - #14 by meooow

1 Like