Instead of searching for answer for m, search for sum - m

Does anybody know what is so special about test no 29? I am positive that my solution is correct (which is obviously not the case) but it gets WA 29. I even compared it with a slow solution (BFS) but I did not find any differences.

robbers dont know the path, so at each point take farthest node from robbers.do these fo for the length of shortest path and in the end take minimum of these.

for lazy node propagation I did tree[n]+=(end-start+1)*lazy[n];
when start and end were integers. tree[n]+=(end-start+1)*(1ll)*lazy[n]; corrected error.

i got TLE 21

To all of you who cannot overcome #3 !!!

All the suggestions about redundant '\n' and about that the dictionary may have repeated words have nothing to do with WA #3 (read condition carefully).

If you use any kind of backward tracking, be it recursion or DFS, check the "no luck" condition attentively. First i used checking the next letter to be '\0' at the beginning of my recursion function, and if so returned 'true'. This is wrong! You must make word-end check BEFORE you make the next step, otherwise you may get "deadlock" "there is no direction to go" though there is no need to go anymore!!!

Test word for the example table
rabadaabracabrac: YES
(starting from [3,1] in C-like indices).

similar to strictly increasing subsequnce of length k just query and update BIT in reverse.

Clang++ 4.0.1 - 0.39s - Accepted
G++ 7.1 - 0.421 - Accepted
Visual C++ 2017 - 1.029 - Time limit exceeded

rofl

in general i noticed that for the most problems clang is usually faster then g++ or ms c++


Edited by author 21.08.2018 03:53

For WA3 try this:
3
1 2 1
Ans:
1
For WA12 try this:
5 1 2 3 1 5
Ans:
1 5

I had maintained dis[n+1][2] for distance. But visited array was vis[n+1], changed it to
vis[n+1][2] and simple bfs.

I have WA #2 ..

Can somebody give me some tests, please ?:)


Edited by author 13.03.2010 14:57

print(int(input()) % 7)

I can not make tests for which the program gives an incorrect result. Help please

Inspector can come at any point.
  after 1 ball pocketed
  after 2 ball pocketed
  or even at the end when n balls are pocketed
Inspector can collect any number of available balls
e.g if he comes after ball 3 is pocketed he can take just 3, or 3 2 or all 3 2 1

I've been stuck in this problem for a very long time, but today I got the idea of Binary Indexed Tree from wikipedia and finally solved this problem :)
Binary Indexed Tree,or BIT, can be viewed as a simplified version of Segment Tree,easier to code and less function to perform. But It's enough to solve this problem

#include<iostream>
#include<cstdio>
using namespace std;

const int Max = 32005;

int n;
int c[Max] = {0};
int level[Max] = {0};

int lowbit(int x)
{
    return x&(-x);
}

int sum(int i)
{
    int s = 0;
    while(i > 0)
    {
        s += c[i];
        i -= lowbit(i);
    }
    return s;
}

void update(int pos,int val)
{
    while(pos <= Max)
    {
        c[pos] += val;
        pos += lowbit(pos);
    }
}

int main()
{
    scanf("%d",&n);
    for(int i = 0; i < n; i ++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        x ++;
        level[ sum(x) ] ++;
        update(x,1);
    }

    for(int i = 0; i < n; i ++)    printf("%d\n",level[i]);
}

I have two loops which calls recursive function

for 1 to 9
  for 0 to 9
    ans+=f(n-2,j,i) // f(rem,prev,prev_prev)

function f(i,j,k) has dp[1001][10][10] memoized solution.why doesnt it timeout.
I'm having hard time understanding my own solution although it is ACd in one trial.

may be anybody know?

Edited by author 13.09.2016 16:35

Edited by author 13.09.2016 16:35

yes!=YES