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

Hint: DP on trees
Tutorial Link: https://codeforces.com/blog/entry/20935

Test 01: 10 15  15 10  13 14
Ans  01: 25

Test 02: 0 5  5 0  1 1
Ans  02: 36

Test 03: 10 15  13 14  15 10
Ans  03: 100

Test 04: 10 15  13 14  15 10
Ans  04: 100

Test 05: 10 15  13 14  15 10
Ans  05: 100

Test 06: 2 1  1 2  1 1
Ans  06: 4

Test 07: 200 200  200 300  300 200
Ans  07: 17182

Test 08: 300 300  301 301  500 101
Ans  08: 80089

Test 09: 400 400  400 410  700 405
Ans  09: 90600

Test 10: 11 16  14 11  13 14
Ans  10: 15

Test 11: 4 1  1 6  2 2
Ans  11: 20

Test 12: 11 13  14 19  12 16
Ans  12: 18

Test 13: 11 14  14 20  12 18
Ans  13: 24

Test 14: 100 110  110 100  108 106
Ans  14: 100

Test 15: 100 110  90 100  94 108
Ans  15: 100

Test 16:
Ans  16:

Test 17:
Ans  17:

Test 18:
Ans  18:

Test 19:
Ans  19:

Test 20:
Ans  20:

Test 21:
Ans  21:

Test 22:
Ans  22:

Test 23:
Ans  23:

Test 24:
Ans  24:

Test 25:
Ans  25:

Test 26:
Ans  26:

Test 27:
Ans  27:

Test 28:
Ans  28:

Test 29:
Ans  29:

Test 30:
Ans  30:

Test 31:
Ans  31:

Test 32:
Ans  32:

Test 33: 1 -1000  -1 -1000  999 0
Ans  33: 3998000

Test 34:
Ans  34:

Test 35: 1 1  11 -1  2 0
Ans  35: 30

Test 36: -200 100  -300 -200  -195 -2
Ans  36: 32400

Test 37: -10 -5  -5 -10  -5 -100
Ans  37: 18496

I understood my problem. It is about calculating sqrt, import math in python doing it wrong with very big numbers.

Edited by author 03.05.2020 00:55

does anybody have idea what it can be?

I am using a solution, where I store all the doors in a BST, and if door k is to be deleted then I delete the kth smallest element in the BST. Same for lookup, I search the kth smallest and print the number.

In test case 2 it is showing memory limit exceeded with only some 66-69KB memory usages. But the question says 64MB memory is allocated. Then why is this happening?
(I am using C++ to code this.)

Don't forget to make an endline in your pretty code....

Ровно этаже задача на региональном этапе для школьников 2018-2019 год

My python 3.3 program has TLE in problem 12.
Has anyone a hint to speed up this algorithm.

My AC program give answer 3 for a following test:
2
4 1 2 3 4
4 1 2 5 4
3 1 2 3

But I think answer must be: 3 4

Am I right?

the length of a route is determined by the number of spans only

But what's span?!

Could you give me some test data ?

I did get AC on this. I used queue and in_degree array. First pushed zero in_degree elements in queue and then visited neighbour for each element in front , reduced in_degree of neighbours by 1 each time to indicate one parent has reduced.

Edited by author 29.04.2020 12:08