Athreya1900's blog

Distinct Character Queries
By Athreya1900, history, 5 years ago, In English

I recently participated in the div 3 contest and tried to solve problem D : Distinct character queries with Square Root Decomposition using a 2D array like block[denoting_which_block][charfreq] and it passed all the 50 odd pretests during contest and I was over the moon because I just recently learned this concept. But today morning, it was hacked sadly :( And I want to know why the solution fails? Should I have used seg/fenwick? This is my submission The thing is we keep looking for a small indication to denote our improvement every single time and feels bad to not grow despite practise

Thanks :)

Anyone?

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

Comments Comments (4)
| Write comment?
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I don't know much about sqrt trees but I think you should use a faster and easier-to-code data structure — For example, Fenwick tree.

Btw, I hacked the submission using this generator

#include <cstdio>
#include <cstring>
int main()
{
	for(int i=1;i<=100000;++i)printf("a");printf("\n");
	printf("100000\n");
	for(int i=1;i<=100000;++i)printf("2 1 100000\n");return 0;
}
→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You code with fast input would have passed. This is your submission with fast input which did pass the tests.

→ Reply