zzyzzy12's blog

Codeforces Round #116 E-Cubes 180E
By zzyzzy12, 14 years ago, In English

180E - Cubes I just pasted C,F in the contest . Both C and F are very easy , and E is the most people passed except C,F. Just now , I got accepted!! According to the input , we can know that if we want to solve it , the program must be O(n) or O(nlogn) . So I followed this thought and got right answer.

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<queue>
#define oo 2000000000
#define ll long long
using namespace std;
struct node
{
       int next,w;
}point[200005];
int s[200005],b[200005],last[200005],n,m,k,x,q;
int main()
{      
       freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout);
       int t,ans,m,p;
       memset(s,0,sizeof(s)); 
       memset(point,0,sizeof(point));
       memset(b,0,sizeof(b)); 
       scanf("%d%d%d",&n,&m,&k);
       ans=q=0;
       for (t=1;t<=n;t++)
       {
             scanf("%d",&x);
             s[x]++;
             if (!b[x]) 
             {
                    b[x]=t;     // get b[] initial value
                    last[x]=t;   //  get last[] initial value
                    point[t].w=s[x]; // record s[x] in position t
             }else
             if (x!=q)
             {
                    point[last[x]].next=t; // 
                    point[t].w=s[x];       //  record s[x] in position t
                    last[x]=t;            // update last[x] 
             }
             q=x;       
             m=t-b[x]+1;              //    get the length of interval
             while (m-(s[x]-point[b[x]].w+1)>k)  // repeat until delete number isn't bigger than k
             {  
                    b[x]=point[b[x]].next;      // try bigger start point
                    m=t-b[x]+1;                 // get the length of interval
             } 
             if (s[x]-point[b[x]].w+1>ans) ans=s[x]-point[b[x]].w+1;  // update answer
       }
       printf("%d\n",ans);
       return 0;
}
  • Vote: I like it
  • -2
  • Vote: I do not like it

»
14 years ago, hide # |
← Rev. 6  
Vote: I like it 0 Vote: I do not like it

(I submitted duplicate comments for mistake. I deleted it.)

→ Reply
»
14 years ago, hide # |
← Rev. 3  
Vote: I like it +1 Vote: I do not like it

Wow!

I solved A, C, D and F during the contest. Then, I got this solution for E after it. I used a data structure called "segment tree" for calcuating the maximum number of colors in the section. I think this code will work at O(n log m) .

Here is my code:

#include <cstdio>
#include <cstring>

#define SEGTREE_MAX 131072

#define SEGTREE_INTERNAL_MAX (SEGTREE_MAX*2-1)

int segtree_table[SEGTREE_INTERNAL_MAX];

void segtree_init(void) {
	memset(segtree_table,0,sizeof(segtree_table));
}

void segtree_update_internal(int youso) {
	int max=segtree_table[youso];
	if(youso*2+1<SEGTREE_INTERNAL_MAX && segtree_table[youso*2+1]>max) {
		max=segtree_table[youso*2+1];
	}
	if(youso*2+2<SEGTREE_INTERNAL_MAX && segtree_table[youso*2+2]>max) {
		max=segtree_table[youso*2+2];
	}
	segtree_table[youso]=max;
	if(youso>0)segtree_update_internal((youso-1)/2);
}

void segtree_plus(int pos,int delta) {
	pos+=SEGTREE_MAX-1;
	segtree_table[pos]+=delta;
	segtree_update_internal((pos-1)/2);
}

int segtree_getmax_internal(
		int youso,int left,int right,int kleft,int kright) {
	if(youso>=SEGTREE_INTERNAL_MAX)return 0;
	if(right<=kleft || kright<=left)return 0;
	else if(left<=kleft && kright<=right)return segtree_table[youso];
	else {
		int max=-0x7fffffff;
		int now;
		now=segtree_getmax_internal(youso*2+1,left,right,
			kleft,kleft+(kright-kleft)/2);
		if(now>max)max=now;
		now=segtree_getmax_internal(youso*2+2,left,right,
			kleft+(kright-kleft)/2,kright);
		if(now>max)max=now;
		return max;
	}
}

int segtree_getmax(int left,int right) {
	return segtree_getmax_internal(0,left,right,0,SEGTREE_MAX);
}

int n,m,k;
int colors[200000];

int main(void) {
	int i;
	int start,end;
	int max_num,result;
	scanf("%d%d%d",&n,&m,&k);
	for(i=0;i<n;i++)scanf("%d",&colors[i]);
	segtree_init();
	start=0;
	result=0;
	for(end=0;end<n;) {
		segtree_plus(colors[end++],1);
		max_num=segtree_getmax(1,m+1);
		while((end-start)-max_num>k) {
			segtree_plus(colors[start++],-1);
		}
		if(max_num>result)result=max_num;
	}
	printf("%d\n",result);
	return 0;
}

Unfortunately, I can't understand what your code is doing. I would appreciate it if you would explain it.

→ Reply
  • »
    »
    14 years ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it 0 Vote: I do not like it

    I trust segment tree can solve this problem,but there has another easy way. I update my code and explained it . My program is nearly O(n) . my thought is settling data with sweeping. I need three arraies and one struct array . array No.1 : s[] recode the number of each color [1,m] between input data 1 to now...changing as sweeping. array No.2 : b[] recode the last legal start point...only change when some illegitimate situation. array No.3 : last[] recode the first point of each color's nearest interval to now...changing as sweeping. One struct array record every point[x]'s data ( 1<=x<=n ) , it has two element , "next" is in order to update b[] when illegitimate situation happen. "w" recode the number of color same point[x] between 1 to x. It's easy find that if there a series cubes with same color,we choose the serie's first element as start point is better then others.So I recode each color's last legitimate start point while sweeping. For exmple , when sweep to a point[t],and it's color is x,we can get the length of interval is m=t-b[x]+1 . we know the number of x color between 1 to b[x] and between 1 to t..so we make a subtration get the number of x between b[x] to t,called "num".Then we can get the number of the cube we must delete in order to the interval is full of color x cube : m-num .. but if (m-num>k) , it's illegitimate,so we must change b[x] vulue bigger . In this situation,we follow the point[b[x]].next until (m-num<=k) Sorry , Im chinese and my English is really poor,hope you can understand my program. ( PS: I know you a Nihonjin , I love Toda && Gakki very mush ! ^_^ )

    → Reply