Thursday, 7 April 2016

**D. Sereja ans Anagrams

D. Sereja ans Anagrams
Sereja has two sequences a and b and number p. Sequence a consists of n integers a1, a2, ..., an. Similarly, sequence b consists of mintegers b1, b2, ..., bm. As usual, Sereja studies the sequences he has. Today he wants to find the number of positions q(q + (m - 1)·p ≤ n; q ≥ 1), such that sequence b can be obtained from sequence aq, aq + p, aq + 2p, ..., aq + (m - 1)p by rearranging elements.
Sereja needs to rush to the gym, so he asked to find all the described positions of q.
Input
The first line contains three integers n, m and p (1 ≤ n, m ≤ 2·105, 1 ≤ p ≤ 2·105). The next line contains n integers a1, a2, ..., an(1 ≤ ai ≤ 109). The next line contains m integers b1, b2, ..., bm (1 ≤ bi ≤ 109).
Output
In the first line print the number of valid qs. In the second line, print the valid values in the increasing order.
Examples
input
5 3 1
1 2 3 2 1
1 2 3
output
2
1 3
input
6 3 2
1 3 2 2 3 1
1 2 3
output
2
1 2

------------------------------------------------------------EDITORIAL-------------------------------------------
We will divide the sequence on min(n, p) sequences. 1-st, (1 + p)-th, (1 + 2·p)-th, ... element will go to the first sequence, 2-nd,(2 + p)-th, (2 + 2·p)-th... will go to the second sequence and so on. Now you need to find an answer for each of them, considering thatp = 1. This can be solved by a simple method. You can go along the sequence from left to right and count the number of occurrences of each number. If the number of occurrences of each number will match the number of occurrences of the same number in the second sequence, then everything is OK.

FOR COUNTING ME CAN USE MAP FIRST MAP THE 2ND SEQUENCE AND THAN

GO THROUGH EACH SEQUENCE AND  INITIALLY DIFFERENCE IS M AMONG BOTH MAP
NOW INSET   1 ELEMENT AND IF SIZE  OF SLID IS> M REMOVE 1 ELEMENT FROM THE LEFT CORNET IF AFTER THESE 2 OPERATION  DIFFERENCE COUNT =0 THIS IS A VALID SEGMENT .....................
---------------------------------------------------CODE-------------------------------------------------------
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
map<lli,int> ma1,ma2;
lli arr[1000000];
vector<int> idx;
vector<int> tidx;
vector<lli> temp;
int main()
 {
   int n,m,k;
   scanf("%d %d %d",&n,&m,&k);
   for(int i=0;i<n;i++)
   {
     scanf("%lld",&arr[i]);
  }
  for(int i=0;i<m;i++)
  {
    lli a;
    scanf("%lld",&a);
    ma2[a]++;
  }
 
  lli ans=0;
 
  for(int i=0;i<k;i++)
   {
   
       temp.clear();
       tidx.clear();
  
     for(int j=i;j<n;j+=k)
         {
           temp.push_back(arr[j]);
           tidx.push_back(j);
 }

 int sz=temp.size();
 int dif=m;
 ma1.clear();

 for(int j=0;j<m &&  j<sz;j++)
  {
    ma1[temp[j]]++;
     if(ma1[temp[j]]<=ma2[temp[j]]) dif--;
     //else dif++;
  }
  if(dif==0)
  {
   ans++;
   idx.push_back(i);
  }
  for(int j=m;j<sz;j++)
   {
   
   
      ma1[temp[j-m]]--;
      if(ma1[temp[j-m]]<ma2[temp[j-m]]) dif++;
      ma1[temp[j]]++;
      if(ma1[temp[j]]<=ma2[temp[j]]) dif--;
      if(dif==0)
 {
  ans++;
  idx.push_back(tidx[j-m+1]);
 }
   }
   }
  
    cout<<ans<<endl;
    sort(idx.begin(),idx.end());
    for(int i=0;i<ans;i++)
     cout<<idx[i]+1<<" ";
 }
Posted by at No comments:

Sunday, 13 March 2016

*1303 - Ferris Wheel

1303 - Ferris Wheel
Time Limit: 2 second(s)Memory Limit: 32 MB
As we all know that not only children but Ferris-Wheel (FW) is favorite to all ages. That's why the LightOJ Park has made a special FW for the programmers. And unlike other Ferris-Wheels, this FW has m seats and every seat is different and very special. Since its circular, the seats are numbered from 1 to m in anticlockwise order, so seat 2 is adjacent to seat 1 and seat 3, seat 1 is adjacent to seat 2 and seat m.
One day n programmers (identified by 1 to n) came and each of them wanted to ride in the FW. Since every seat is special, everyone wants to taste the ride of every seat. So, they made the following algorithm:
1.      They will form a queue from 1 (front) to n (back). As they want to enjoy the ride, they want to sit alone in a seat, because two (or more) may start problem-solving in the ride.
2.      The FW moves in clockwise order. Initially the seat 1 is in bottom and after 5 seconds, it starts. And when it starts, in each 5 second interval the next seat comes to bottom. So, the order of the seats in bottom are seat 1 (at time 5), seat 2 (at time 10), ..., seat m (at time 5*m), seat 1 (at time 5*m+5), ... and in this interval, a person sits in that seat or gets out (if he is in the seat) or both (one gets out and another gets in). Assume that these kinds of movements take quite a small time and thus that can be ignored.
3.      When a programmer gets out from one seat (he just rode in that seat), then if he has ridden in all the seats, he will leave, otherwise he will join in the back of the queue.
4.      When a seat comes into bottom, if all the programmers in the queue have ridden in the seat, nothing happens. Otherwise the first person (from front) in the queue who hasn't ridden in the seat sits in that seat and other programmers keep standing. For example, the current queue is 5, 2, 3, 1 and a seat is in the bottom which has been already ridden by 5 and 2 but 3 hasn't; so, 3 will sit in that seat leaving the queue: 5, 2, 1.
Now you are the (n+1)th programmer and you are unlucky, because you are assigned a task, and the task is to find the minimum time when you are sure that everyone has ridden in all the seats.

Input

Input starts with an integer T (≤ 400), denoting the number of test cases.
Each case starts with a line containing two integers n (1 ≤ n ≤ 20) and m (2 ≤ m ≤ 20).

Output

For each case, print the case number and the time.

Sample Input

Output for Sample Input

2
2 3
3 2
Case 1: 65
Case 2: 40

PROBLEM SETTER: JANE ALAM JAN


----------------------------------------------code---------------------------------------------------------------
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define fr(i,a,b) for (int i = (a), _b = (b); i <= _b; i++)
#define frr(i,a,b) for (int i = (a), _b = (b); i >= _b; i--)
#define rep(i,n) for (int i = 0, _n = (n); i < _n; i++)
#define repr(i,n) for (int i = (n) - 1; i >= 0; i--)
#define foreach(it, ar) for ( typeof(ar.begin()) it = ar.begin(); it != ar.end(); it++ )
#define fill(ar, val) memset(ar, val, sizeof(ar))
#define uint64 unsigned long long
#define int64 long long
#define all(ar) ar.begin(), ar.end()
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define BIT(n) (1<<(n))
#define AND(a,b) ((a) & (b))
#define OR(a,b) ((a) | (b))
#define XOR(a,b) ((a) ^ (b))
#define sqr(x) ((x) * (x))
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<ii> vii;
typedef vector<int> vi;
#define PI 3.1415926535897932385
#define INF 1000111222
#define eps 1e-7
#define maxN 22
int n, m, pro[maxN];
bool done[maxN][maxN];
deque< pair<int, bool> > q;
int main() {
#ifndef ONLINE_JUDGE
freopen("test.inp", "r", stdin);
//freopen("test.out", "w", stdout);
#endif
int cases, caseNo = 0;
for (scanf("%d", &cases); cases--; ) {
scanf("%d %d", &n, &m);
fill(done, false);
q.clear();
rep(i, n) q.pb(mp(i, true));
rep(i, m) pro[i] = -1;
int i = 0, res = 0, counter = n * m;
while (true) {
if (pro[i] != -1) {
done[pro[i]][i] = true;
q.pb(mp(pro[i], true));
pro[i] = -1;
counter--;
}
rep(j, q.size())
if (q[j].ss && !done[q[j].ff][i]) {
q[j].ss = false;
pro[i] = q[j].ff;
break;
}
while (q.size() && !q.front().ss) q.pop_front();
i = (i + 1) % m;
res += 5;
if (counter == 0) break;
}
printf("Case %d: %d\n", ++caseNo, res);
}
return 0;
}
Posted by at No comments:
Subscribe to: Posts (Atom)