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

Distinct Character Queries
Автор Athreya1900, история, 5 лет назад, По-английски

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?

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

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

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;
}
→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить