Think about O(N) solution, task much easier than is looks like.

I use queue and got AC despite my solution probably has O(N * queue_work_complexity), not clearly O(N)

Any hints for solution? I am completely stuck at TLE.

On 21 th test
N=100000 R=0

Edited by author 24.08.2012 18:03

   I write algorithm on o(n), but wa# 15....
   I can`t find out the reason
   who can give me some hint ?


                               thanks

Edited by author 22.12.2008 05:23

i have write NlogN algo -  TLE  21
then i rewrite it in N*sqrt(N) - TLE 21
maybe something wrong with this test?

Why WA 15? Help me please.

import java.util.Arrays;
import java.util.Scanner;


public class Timus1579 {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n=in.nextInt(),r=in.nextInt();
        Shub[] a=new Shub[n];
        Xod[] x=new Xod[n];
        int ix=1,im=0,gt=0;
        a[0]=new Shub(in.nextInt(),0);
        x[0]=new Xod(a[0].size);
        for(int i=1; i<n; i++){
            a[i]=new Shub(in.nextInt(),i);
            if(x[im].size+r<a[i].size){
                x[im].size=a[i].size;
                x[im].amount++;
                a[i].num=im;
                im=(im+1)%ix;
            }else{
                a[i].num=ix;
                x[ix]=new Xod(a[i].size);
                ix++;
            }
        }
        System.out.println(ix);
        Arrays.sort(a);

        for(int i=0; i<ix; i++){
            System.out.print(x[i].amount+" ");
            while((gt<n)&& (a[gt].num==i)){
                System.out.print((a[gt].num2+1)+" ");
                gt++;
            }
            System.out.println();
        }
    }
}
class Shub implements Comparable{
    int num,num2,size;

    public Shub(int s, int n) {
        num=0;
        size=s;
        num2=n;
    }

    public int compareTo(Object o) {
        Shub a=(Shub)o;
        if(num==a.num){
            return num2-a.num2;
        }else return num-a.num;
    }
}
class Xod{
    int size,amount;
    public Xod(int i) {
        size=i;
        amount=1;
    }
}

just check your program on these tests
----------
4 3
1 5 8 10
answer:
1 8
5 10
wrong answer:
1 5
8
10
----------
4 2
3 5 7 10
answer:
5 10
3 7
wrong answer:
7 10
5
3

O(N*logN) AC 0.234

hint:

lower_bound    STL

O(N) solution ;)

    What's the test 15?Can somebody tell me?
    Thank you.
    Here is my code with O(N) soulution which is get WA on #15
program coats;
const
  maxn=200100;
var
  g,next,t:array [0..maxn] of int64;
  l,a:array [0..maxn] of int64;
  i,k,m,n:longint;
  r:int64;
procedure init;
  begin
    read(n,r);
    for i:=1 to n do read(a[i]);
  end;
procedure solve;
  begin
    m:=1;k:=1;
    next[n]:=g[1];g[1]:=n;l[1]:=a[n];t[1]:=1;
    for i:=n-1 downto 1 do
      begin
        if l[k]-a[i]>r
          then begin
                 next[i]:=g[k];g[k]:=i;l[k]:=a[i];inc(t[k]);
                 inc(k);if k>m then k:=1;
                 continue;
               end;
        inc(m);next[i]:=g[m];g[m]:=i;l[m]:=a[i];t[m]:=1;
      end;
    writeln(m);
    for i:=m downto 1 do
      begin
        write(t[i]);
        r:=g[i];
        while r<>0 do
          begin
            write(' ',r);
            r:=next[r];
          end;
        writeln;
      end;
  end;
begin
  assign(input,'coats.in');reset(input);
  assign(output,'coats.out');rewrite(output);
  init;
  solve;
  close(input);close(output);
end.

In russian: "должен превосходить размер меньшей более, чем на величину R". May be "должен превосходить размер меньшей не менее, чем на величину R"? In english the same statement.

#include <fstream>
#include <stdio.h>
#include <vector>
using namespace std;

int n, r, num = 0, g;
int arr[100100] = {0};
vector <int> v[100100];
bool can[100100] = {0};
int pr[100100] = {0};
int pr_val[100100] = {0};
int nm[100100] = {0};

int fset (int x)
{
    int i;
    /*for (i = x; i > 0; --i)
    {
        if (!can[i])
        {
            return i;
        }
    }
    return 0;*/
    if (!can[x])
    {
        return x;
    }
    int t = pr[x];
    pr[x] = fset (t);
    return pr[x];
    ++g;
}

int main ()
{
    //freopen ("a.in", "r", stdin);
    //freopen ("a.out", "w", stdout);
    int i, j = 0, t;
    scanf ("%d%d", &n, &r);
    arr[0] = -110000000;
    for (i = 1; i <= n; ++i)
    {
        scanf ("%d", &arr[i]);
        while (arr[i]-arr[j] > r)
        {
            ++j;
        }
        --j;
        pr[i] = i-1;
        pr_val[i] = j;
    }
    for (i = 1; i <= n; ++i)
    {
        j = pr_val[i];
        g = 0;
        t = fset (j);
        if (t == 0)
        {
            num++;
            v[num].push_back (i);
            nm[i] = num;
        }
        else
        {
            can[t] = true;
            v[nm[t]].push_back (i);
            nm[i] = nm[t];
        }
    }
    printf ("%d\n", num);
    int col = 0;
    for (i = 1; i <= num; ++i)
    {
        printf ("%d ", v[i].size());
        for (j = 0; j < v[i].size()-1; ++j)
        {
            printf ("%d ", v[i][j]);
            ++col;
            if (v[i][j]+r >= v[i][j+1])
            {
                int q = 1;
                q = q/(1-q);
            }
        }
        printf ("%d\n", v[i][v[i].size()-1]);
        ++col;
    }
    if (col != n)
    {
        int q = 1;
        q = q/(1-q);
    }
    return 0;
}

Edited by author 18.10.2007 02:24

My program give answer on test in sample:
3
4 1 4 6 8
3 2 5 7
1 3
But i have wa #1
It's wrong?

please, give some tests

Can we consided the problem as optimal sheduling
task raplacing a value ak with interval [ak.ak+R)
and applying greedy algotithm.
Yes!
Dilworth applying.
Having confirmed by Dilworth optimal number M
it is simply to find O(n) of right dividing:
1,2,3,1,2,3,1,2,3.. if M==3.
My O(n) 0.125Ac one of the best, but respect to them
who have 0.03 because they can build quick implementation
of simple processes.
Edited by author 17.10.2007 14:38

Edited by author 18.10.2007 10:36

Edited by author 18.10.2007 10:36

Edited by author 18.10.2007 11:03

Why I WA TEST 13 !!
I write an O(N) program but why I wa test 13??