It is not said in the condition that the points have different coordinates. Can points have the same coordinates?

in some cases, there are more than 1 current user

Count numbers X and Y of quiet days for vacations given by intervals [1;r] and [1;l-1].

The answer to the problem would be ANS=X-Y.
How to count X and Y?

In the first step,  we eliminate every 2th.

That is,  CNT_0=r and and CNT_1=r//2

In the second step,  CNT_2=CNT_1//3.

And so on.

Until CNT > 0.

Last non-zero  CNT is the answer.

The 7th test case is:
2 5 1

And my program outputs 348.
I've tried to brute-force, and I got the same result. Did I misunderstand the problem?
What should be the output for this test case?

Input:
1 40 1
Output:
1099511627776

we can use the netflow algorithm(+ operator) to solve this problem.
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 5
using namespace std;
const int INF=1<<30;
int n,m,flow[MAXN][MAXN],pre[MAXN],cur[MAXN],gap[MAXN],d[MAXN],g[MAXN],l[MAXN][MAXN];
int Maxflow_Isap(int s,int t,int n) {
    memset(d,-1,sizeof(d));
    memset(pre,-1,sizeof(pre));
    memset(gap,0,sizeof(gap));
    gap[s]=n;
    int u=pre[s]=s,v,maxflow=0;
    while (d[s]<n) {
      v=n+1;
      for (int i=cur[u];i<=g[u];i++)
        if (flow[u][l[u][i]] && d[u]==d[l[u][i]]+1) {
          v=l[u][i];cur[u]=i;break;
        }
      if (v<=n) {
        pre[v]=u;u=v;
        if (v==t) {
          int dflow=INF;u=s;
          for (int i=v;i!=s;i=pre[i]) dflow=min(dflow,flow[pre[i]][i]);
          maxflow+=dflow;
          for (int i=v;i!=s;i=pre[i]) {
            flow[pre[i]][i]-=dflow;
            flow[i][pre[i]]+=dflow;
          }
        }
      }
      else{
        int mindist=n;
        for (int i=1;i<=g[u];i++)
          if (flow[u][l[u][i]]) mindist=min(mindist,d[l[u][i]]);
        if (!--gap[d[u]]) return maxflow;
        gap[d[u]=mindist+1]++;cur[u]=1;
        u=pre[u];
      }
    }
    return maxflow;
}
void setsize(int x,int y,int c) {
    flow[x][y]=c;
    l[x][++g[x]]=y;
    l[y][++g[y]]=x;
}
int main() {
    scanf("%d%d",&n,&m);
    setsize(1,2,n);
    setsize(2,4,n);
    setsize(1,3,m);
    setsize(3,4,m);
    printf("%d\n",Maxflow_Isap(1,4,4));
    return 0;
}

Since the requirements became stronger, and time was reduced from 2 sec down to 1 sec, now it is not possible to resolve the task using bruteforce method, python is very slow for such hard requirements.

Even I do empty loops the taken time is already about 1.3 sec.

from time import time
time_before = time()

len_lst = 20

for i in range(1, ((2 ** len_lst) // 2) - 1):

    for j in range(len_lst):

        pass

print(time() - time_before)

>>> 1.3192360401153564

I think for Python the time should be rolled back to 2 sec.
Of cause if I use bruteforce on "C" it takes about 0.2 sec, but Python is not "C".

This problem is easier than rating should be if you know the trick.

Invariant: graph G is decomposable if and only if all the connected components of G has even number of edges.

A tree is very easy to be decomposed. Creating a tree equivalent to each connected component will lead to the answer.

Hope this help, Mick :)

I don`t understant brute-force , who can give your code to me ?

mail: k13795263@yahoo.cn



Edited by author 23.08.2008 05:40

i have got WA on test #5. Help me please. Thanks

If you got TLE on test>28, try this test
50000
0 0
0 0
... 50000 points (0,0)
0 0

I tried the following:

For every recognized language find the minimum and the maximum possible lines.
Then find the maximum and minimum possible lines for all.
For minimum to maximum test if it divides N.
This solves the first four tests.

Is this the right way?

So, if you can't understand what author of the problem meant, you're not alone :o)

He meant the following: chukcha goes from A to B and he covers each K kilometers in H hours. But the speed whithin this interval is not constant: he can cover K minus eps kilometers within first second of H hours and remaining eps kilometers in the remaining time (and visa versa).

It leads to the problem itself: what speed distribution along the interval leads to the minimum time to reach destination and what distribution leads to maximum time.

как понимать _минимальное_ и _максимальное_ время ???

Edited by author 01.11.2009 13:12

why taking the biggiest fraction of remain assure that the church gets the minimized?

If you decide not to repeat my mistake, then the 49th check is that the king must bypass the black pawn in order to catch up with the white one, I will not talk further, but just give you an example:
8
a3 d7 e6
Answer:BLACK WINS

Try:
2
Correct answer is 2 1

Main idea is to split cube into 8 parts and query/add for each one.
Here is my code that have TL6.
Any ideas of how to improve it?

import java.io.*;

public class P1470 {
    static int [] tree = new int[10000000];
    private static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));

        n = Integer.valueOf(reader.readLine());

        while (true) {
            String line = reader.readLine();
            if (line.startsWith("1")) {
                add(new Ufo(line));
            } else if (line.startsWith("2")){
                writer.println(query(new Region(line)));
            } else {
                break;
            }
        }
        writer.flush();
    }

    private static int query(Region region) {
        return doQuery(region, new Region(0, 0, 0, n - 1, n - 1, n - 1), 0);
    }

    private static int doQuery(Region q, Region r, int node) {
        if (!r.overlaps(q)) return 0;
        if (q.contains(r)) {
            return tree[node];
        }
        int xMid = (r.x1 + r.x2) / 2;
        int yMid = (r.y1 + r.y2) / 2;
        int zMid = (r.z1 + r.z2) / 2;

        return
            doQuery(q, new Region(r.x1, r.y1, r.z1, xMid, yMid, zMid), node * 8 + 1) +
            doQuery(q, new Region(xMid + 1, r.y1, r.z1, r.x2, yMid, zMid), node * 8 + 2) +
            doQuery(q, new Region(xMid + 1, r.y1, zMid + 1, r.x2, yMid, r.z2), node * 8 + 3) +
            doQuery(q, new Region(r.x1, r.y1, zMid + 1, xMid, yMid, r.z2), node * 8 + 4) +
            doQuery(q, new Region(r.x1, yMid + 1, r.z1, xMid, r.y2, zMid), node * 8 + 5) +
            doQuery(q, new Region(xMid + 1, yMid + 1, r.z1, r.x2, r.y2, zMid), node * 8 + 6) +
            doQuery(q, new Region(xMid + 1, yMid + 1, zMid + 1, r.x2, r.y2, r.z2), node * 8 + 7) +
            doQuery(q, new Region(r.x1, yMid + 1, zMid + 1, xMid, r.y2, r.z2), node * 8 + 8);
    }

    private static void add(Ufo ufo) {
        doAdd(ufo, new Region(0, 0, 0, n - 1, n - 1, n - 1), 0);
    }

    private static void doAdd(Ufo ufo, Region r, int node) {
        if (!r.contains(ufo)) return;

        tree[node] += ufo.count;

        if (r.isPoint()) return;

        int xMid = (r.x1 + r.x2) / 2;
        int yMid = (r.y1 + r.y2) / 2;
        int zMid = (r.z1 + r.z2) / 2;

        doAdd(ufo, new Region(r.x1, r.y1, r.z1, xMid, yMid, zMid), node * 8 + 1);
        doAdd(ufo, new Region(xMid + 1, r.y1, r.z1, r.x2, yMid, zMid), node * 8 + 2);
        doAdd(ufo, new Region(xMid + 1, r.y1, zMid + 1, r.x2, yMid, r.z2), node * 8 + 3);
        doAdd(ufo, new Region(r.x1, r.y1, zMid + 1, xMid, yMid, r.z2), node * 8 + 4);
        doAdd(ufo, new Region(r.x1, yMid + 1, r.z1, xMid, r.y2, zMid), node * 8 + 5);
        doAdd(ufo, new Region(xMid + 1, yMid + 1, r.z1, r.x2, r.y2, zMid), node * 8 + 6);
        doAdd(ufo, new Region(xMid + 1, yMid + 1, zMid + 1, r.x2, r.y2, r.z2), node * 8 + 7);
        doAdd(ufo, new Region(r.x1, yMid + 1, zMid + 1, xMid, r.y2, r.z2), node * 8 + 8);
    }

    static class Region {
        int x1, y1, z1, x2, y2, z2;

        Region(String s) {
            String[] split = s.split("\\s");
            x1 = Integer.valueOf(split[1]);
            y1 = Integer.valueOf(split[2]);
            z1 = Integer.valueOf(split[3]);
            x2 = Integer.valueOf(split[4]);
            y2 = Integer.valueOf(split[5]);
            z2 = Integer.valueOf(split[6]);
        }

        Region(int x1, int y1, int z1, int x2, int y2, int z2) {
            this.x1 = x1;
            this.y1 = y1;
            this.z1 = z1;
            this.x2 = x2;
            this.y2 = y2;
            this.z2 = z2;
        }

        boolean contains(Ufo ufo) {
            return ufo.x >= x1 && ufo.x <= x2 && ufo.y >= y1 && ufo.y <= y2 && ufo.z >= z1 && ufo.z <= z2;
        }

        boolean contains(Region r) {
            return overlaps(r) && x1 <= r.x1 && x2 >= r.x2 && y1 <= r.y1 && y2 >= r.y2 && z1 <= r.z1 && z2 >= r.z2;
        }

        boolean overlaps(Region r) {
            return r.x1 <= x2 && r.x2 >= x1 && r.y1 <= y2 && r.y2 >= y1 && r.z1 <= z2 && r.z2 >= z1;
        }

        boolean isPoint() {
            return x1 == x2 && y1 == y2 && z1 == z2;
        }
    }

    static class Ufo {
        int x, y, z, count;

        Ufo(String s) {
            String[] split = s.split("\\s");
            x = Integer.valueOf(split[1]);
            y = Integer.valueOf(split[2]);
            z = Integer.valueOf(split[3]);
            count = Integer.valueOf(split[4]);
        }
    }
}

How can i improve my O(n ^ 2 * logN) time and O(n * n) memory too pass all tests?
int n, y[2004], index = 1, maximum = 1, rati;
pair<int, int> x[2004];
map<int, int> s[2004];
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> x[i].first;
        x[i].second = i;
        y[i] = 1;
    }
    sort(x, x + n);
    for(int i = 1; i < n; i++)
    {
        for(int j = 0; j < i; j++){
            if(y[i] < s[j][x[i].first - x[j].first] + 2 && x[i].first - x[j].first != 0){
                y[i] = s[j][x[i].first - x[j].first] + 2;
                if(maximum < y[i]){
                    index = i;
                    maximum = y[i];
                    rati = x[i].first - x[j].first;
                }
            }
            s[i][x[i].first - x[j].first] = s[j][x[i].first - x[j].first] + 1;
        }
    }
    cout << maximum << "\n";
    int val = x[index].first, i;
    cout << x[index].second + 1 << " ";
    for(i = index - 1; i >= 0; i--)
    {
        if(val - x[i].first == rati && rati != 0)
        {
            val = x[i].first;
            cout << x[i].second + 1 << " ";
        }
    }
    return 0;
}