Omega1's blog

By Omega1, history, 9 years ago, In English

Hello to all,today I solve problem A. Greg and Array and I have and misunderstanding: I have two submission,one get accepted and another get wrong answer on test 11.

Accepted

Wrong answer

the difference between this both submission is the line below:

for (i=1;i<=n;i++) dp[i]=dp[i]+dp[i-1];

if I change n with m I get Accepted,Can someone explain me why,I didn't use element on position bigger than m and I didn't exceed the limits of the array dp???

I'm very interesting why this happens,because during the contest this mistake can cost me one problem.

Full text and comments »

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

By Omega1, history, 9 years ago, In English

Hello,I'm very interested how to build a suffix array for a 2D matrix?.Can someone help me.Thanks...

Full text and comments »

  • Vote: I like it
  • -17
  • Vote: I do not like it

By Omega1, history, 9 years ago, In English

Hello to all,today I find a interesting problem on codeforces B. The least round way,when I submit my code I get wrong answer on test 3 but at my PC I have a correct solution on this test,what is the problem?can someone help me?Thanks.

Full text and comments »

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

By Omega1, history, 9 years ago, In English

Today I solved problem E. A Simple task that was given at last contest,and I find something intersting and new for me, posible and for other users.Why if I declare k,l,st,dr as a global variable I get TLE on test 9 and if I declare as a local variable my code past all tests?

Can someone explain why?

k=x;
for (l=26;l>=1;l--) {
    st=lower_bound(g[l].begin(),g[l].end(),x)-g[l].begin();
    dr=upper_bound(g[l].begin(),g[l].end(),y)-g[l].begin();
    for (;st<dr;st++) {
         g[l][st]=k; k++;
    }
}

get TLE;

int k=x;
for (int l=26;l>=1;l--) {
    int st=lower_bound(g[l].begin(),g[l].end(),x)-g[l].begin();
    int dr=upper_bound(g[l].begin(),g[l].end(),y)-g[l].begin();
    for (;st<dr;st++) {
         g[l][st]=k; k++;
    }
}

past all tests.

Full text and comments »

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

By Omega1, history, 9 years ago, In English

I have a question , need fast to do to two types of operations:

update: 1 x y element on position x become y;

query : 2 x y number of distinct numbers from the interval [ x , y ];

How to solve this problem,can someone help me??

Full text and comments »

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