#include <bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define Long long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define forn(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define SZ(a) (int) a.size()
#define all(x) (x).begin(),(x).end()
#define gc getchar_unlocked
#define PI acos(-1.0)
#define INF 1<<29
#define EPS 1e-9
#define Fr first
#define Sc second
#define Sz size()
#define lc ((n)<<1)
#define rc ((n)<<1|1)
#define db(x) cout << #x << " -> " << x << endl;
#define Di(n) int n;si(n)
#define Dii(a,b) int a,b;si(a);si(b)
#define Diii(a,b,c) int a,b,c;si(a);si(b);si(c)
#define Si(n) si(n)
#define Sii(a,b) si(a);si(b)
#define Siii(a,b,c) si(a);si(b);si(c)
#define min(a,b) ((a)>(b) ? (b) : (a) )
#define max(a,b) ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}
/*************************** END OF TEMPLATE ****************************/
const int N = 1e5+5;
struct Edge{
int x,y1,y2;
int type ;
Edge(){}
Edge(int x,int y1,int y2,int type):x(x),y1(y1),y2(y2), type(type) {}
bool operator < (const Edge &e) const {
return x < e.x;
}
};
vector<Edge> edge;
vector<int>v;
int lazy[4*N],seg[4*N];
int update(int n,int b,int e,int i,int j,int t)
{
if(b>j || e<i) {
if(lazy[n]) return v[e+1] - v[b];
else return seg[n];
}
if(b>=i && e<=j) {
lazy[n] += t;
if(lazy[n]) return v[e+1] - v[b];
else return seg[n];
}
int mid = (b+e)/2;
int k1 = update(lc,b,mid,i,j,t);
int k2 = update(rc,mid+1,e,i,j,t);
seg[n] = k1+k2;
if(lazy[n]) return v[e+1] - v[b];
else return seg[n];
}
int main()
{
//freopen("in.txt","r",stdin);
Di(t);
int cs = 0;
while(t--) {
Di(n);
Edge e;
for(int i= 0; i < n; i ++ ) {
Dii(x1,y1);
Dii(x2,y2);
v.pb(y1);
v.pb(y2);
e.x = x1;
e.y1 = y1;
e.y2 = y2;
e.type = 1;
edge.pb(e);
e.x = x2;
e.type = -1;
edge.pb(e);
}
sort(all(v));
v.resize(unique(all(v)) - v.begin());
sort(all(edge));
for(int i= 0;i < edge.size();i ++ ) {
edge[i].y1 = lower_bound(all(v),edge[i].y1) - v.begin();
edge[i].y2 = lower_bound(all(v),edge[i].y2) - v.begin() - 1;
}
int nn = v.size();
Long len = update(1,0,nn-1, edge[0].y1 , edge[0].y2 , 1);
Long prv = edge[0].x;
Long ans = 0;
for(int i = 1;i < edge.size() ; i ++ ) {
ans += len * (edge[i].x - prv) ;
len = update(1,0,nn-1,edge[i].y1,edge[i].y2,edge[i].type);
prv = edge[i].x;
}
printf("Case %d: %lld\n", ++cs, ans);
v.clear();
edge.clear();
}
return 0;
}
Category Archives: lightoj
LOJ 1279 – GRAPH COLORING
Category : Gaussian Elimination
Solution : k ^ (n- rank) % MOD;
/*
*************************
Id : Matrix.code
Task: 1279 – GRAPH COLORING
Date: 2016-01-13
**************************
*/
#include <bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define Long long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define forn(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define SZ(a) (int) a.size()
#define all(x) (x).begin(),(x).end()
#define gc getchar_unlocked
#define PI acos(-1.0)
#define INF 1<<29
#define EPS 1e-9
#define Fr first
#define Sc second
#define Sz size()
#define lc ((n)<<1)
#define rc ((n)<<1|1)
#define db(x) cout << #x << " -> " << x << endl;
#define Di(n) int n;si(n)
#define Dii(a,b) int a,b;si(a);si(b)
#define Diii(a,b,c) int a,b,c;si(a);si(b);si(c)
#define Si(n) si(n)
#define Sii(a,b) si(a);si(b)
#define Siii(a,b,c) si(a);si(b);si(c)
#define min(a,b) ((a)>(b) ? (b) : (a) )
#define max(a,b) ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}
/*************************** END OF TEMPLATE ****************************/
const int N = 1000;
typedef Long T;
typedef vector<Long> VT;
typedef vector<VT> VVT;
void show(VVT &a)
{
printf("PRINTING\n");
for(int i = 0; i < SZ(a); i++)
{
for(int j = 0; j < SZ(a[0]); j ++ ) printf("%4d",a[i][j]);
printf("\n");
}
}
int gauss(VVT &a,Long k )
{
int n= SZ(a) , m= SZ(a[0]) , r = 0;
for(int c = 0 ; c < m-1 && r < n ; c ++ ) {
int j = r;
for(int i= j+1; i < n; i ++) if(a[i][c]) { j = i; break; }
if(a[j][c] == 0 ) continue;
swap(a[j],a[r]);
T s = modinverse(a[r][c], k);
for(int i = 0; i < m ; i++ ) a[r][i] = (a[r][i] * s) % k;
for(int i = 0; i < n ; i ++ ) if(i!=r) {
if(a[i][c] == 0) continue;
Long t = a[i][c];
for(int j= 0; j < m; j ++ ) a[i][j] = ((a[i][j] - t * a[r][j]) % k + k ) % k;
}
r++;
//show(a);
}
return r;
}
vector<int> G[N];
int main()
{
//freopen("in.txt","r",stdin);
Di(t);
int cs = 0;
while(t--) {
Long n,m,k;
scanf("%lld %lld %lld",&n,&m,&k);
forn(i,m) {
Dii(a,b);
a--,b--;
G[a].pb(b);
G[b].pb(a);
}
VVT a(n,VT(n+1,0));
for(int i =0 ;i < n ; i ++ ) {
a[i][i] = 1;
for(int j = 0; j < SZ(G[i]) ;j ++) {
a[i][G[i][j]] = k-1;
}
a[i][n] = 0;
}
//show(a);
int r = gauss(a,k);
printf("Case %d: %lld\n" , ++cs , bigmod(k,n-r,1000000007LL));
for(int i = 0; i < n; i ++ ) G[i].clear();
}
return 0;
}
DP with profile
Problem Link : Link
Category: DP + Profile
Here Profile consist of two rows, Denote them Mask1,Mask2, current index,
DP states are F(Mask1, Mask2,int index)
In each stage we select such bit string that, this ensures Mask1 to be set all 1
//
// main.cpp
// 1092 - Lighted Panels
//
// Created by Repon Macbook on 12/11/15.
// Copyright © 2015 MAC. All rights reserved.
/*
*************************
Id : Matrix.code
Task:
Date:
**************************
*/
#include <bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define Long long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define forn(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define gc getchar_unlocked
#define PI acos(-1.0)
#define INF 1<<29
#define EPS 1e-9
#define Fr first
#define Sc second
#define Sz size()
#define lc ((n)<<1)
#define rc ((n)<<1|1)
#define db(x) cout << #x << " -> " << x << endl;
#define Di(n) int n;si(n)
#define Dii(a,b) int a,b;si(a);si(b)
#define Diii(a,b,c) int a,b,c;si(a);si(b);si(c)
#define Si(n) si(n)
#define Sii(a,b) si(a);si(b)
#define Siii(a,b,c) si(a);si(b);si(c)
#define min(a,b) ((a)>(b) ? (b) : (a) )
#define max(a,b) ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}
/*************************** END OF TEMPLATE ****************************/
const int N = 10;
char g[N][N];
int ar[N];
int r,c;
int dp[1<<8][1<<8][10];
int bits[1<<8];
vector<int> G[1<<8];
int oo[1<<8];
bool solve;
int F(int Mask1,int Mask2, int ind)
{
if(ind == r) {
if(Mask1== (1<<c)-1) {
solve = 1;
return 0;
}
return 1e8;
}
if(dp[Mask1][Mask2][ind] !=-1) return dp[Mask1][Mask2][ind];
int res = 1e8;
for(int j= 0; j < G[Mask1].Sz; j ++ ){
int k = G[Mask1][j];// We store all the Mask that can Make Mask1 to set all 1,
res = min(res , bits[k] + F(Mask2^oo[k] ,ar[ind+1] ^oo[k] , ind+1));
}
return dp[Mask1][Mask2][ind] = res;
}
int main()
{
Di(t);
int cs = 0;
while(t--) {
Sii(r,c);
forn(i,r) scanf("%s",g[i]);
forn(i,r) {
ar[i] = 0;
forn(j,c) if(g[i][j]=='*') ar[i] |= (1<<j);
}
forn(i,1<<c) {
forn(j,c) if(i&1<<j) bits[i] ++;
int prv = 0;
forn(j,c)if(i&1<<j){
prv ^=(1<<j);
if(j+1 < c )prv ^=(1<<(j+1));
if(j-1 >=0 ) prv ^= (1<<(j-1));
}
int M =( (1<<c)-1) ^ prv;
G[M].pb(i);
oo[i] = prv;
}
ms(dp,-1);
int res = 1e8;
solve=0;
forn(i,1<<c) {
res = min(res , F(i,ar[0],0));
}
if(solve) {
printf("Case %d: %d\n",++cs, res );
}else printf("Case %d: impossible\n",++cs);
forn(i,1<<c) G[i].clear();
ms(bits,0);
}
return 0;
}
Bitmask : Iterating Over a subset
Intended Problem : DP
Category: Bitmask DP
Discussion:
Now Let’s say, We have n elements in a set. How many subsets of this set?
Exactly 2^n. How can we find all those subset ? One way is to use recursion, another is bit mask
We take a n bit binary number to represent a subset of the set. For each element if the corresponding bit of the number is 1, then it is included , and vice-versa.
Now take n = 4, total = 2^n = 16 subset.
S = {3,5,1,6}
1011 Means -> {3,1,6}
code for following ;
for(int i = 0; i < 1<<n; i++ ) {
// i contains the mask of set S
for(int j = 0; j < n; j ++) {
if(i & 1<<j) {
// Jth element in this subset
}
}
}
Easy ? Right.
Now If I ask, Iterate through the subsets of 1011, {3,1,6} which has 2^3 possible subset
possible subsets are {{},{3},{1},{6},{3,1},{3,6},{3,1,6}}
One way to do this :
// Lets say the mask = x;
for(int i = x; ; i = (i-1)&x)
{
// i contains the mask of one of the subset of x
// Main Purpose
if(i==0) break;
}
//This little code
Here is the solution for intended problem :
/*
*************************
Id : Matrix.code
Task:
Date:
**************************
*/
#include <bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define Long long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define forn(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define gc getchar_unlocked
#define PI acos(-1.0)
#define INF 1<<29
#define EPS 1e-9
#define Fr first
#define Sc second
#define Sz size()
#define lc ((n)<<1)
#define rc ((n)<<1|1)
#define db(x) cout << #x << " -> " << x << endl;
#define Di(n) int n;si(n)
#define Dii(a,b) int a,b;si(a);si(b)
#define Diii(a,b,c) int a,b,c;si(a);si(b);si(c)
#define Si(n) si(n)
#define Sii(a,b) si(a);si(b)
#define Siii(a,b,c) si(a);si(b);si(c)
#define min(a,b) ((a)>(b) ? (b) : (a) )
#define max(a,b) ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}
/*************************** END OF TEMPLATE ****************************/
const int N = 14;
int a[N][N];
int F[1<<N];
int dp[1<<N];
int p2[(1<<N)+5];
int ar[15];
int main()
{
forn(i,14) p2[1<<i] = i;
Di(t);
int cs= 0;
while(t--) {
Di(n);
forn(i,n)forn(j,n){
Si(a[i][j]);
}
forn(i,1<<n){
int Sum = 0, cnt =0;
for(int j=i ; j ; j -=j&-j) {
ar[cnt++]= p2[j&-j];
}
for(int j=0; j <cnt ; j++ ) for(int k = 0; k < cnt ; k ++ ) Sum += a[ar[j]][ar[k]];
F[i] = Sum;
}
ms(dp,63);
dp[0] = 0;
forn(i,1<<n){
for(int j = i ; ; j = (j-1) & i) {
dp[i]= min(dp[i], F[j] + dp[i^j] );
if(j == 0) break;
}
}
printf("Case %d: %d\n", ++cs, dp[(1<<n) - 1]);
}
return 0;
}
LOJ 1110 – An Easy LCS
Category : DP
Link : Problem
Discussion:
Easy DP,
Here we keep dp[i][j]-> the lexicographic smallest LCS of A[1…i] & B[1….j]
The Transition is easily understandable
/*
*************************
Id : Matrix.code
Task:
Date:
**************************
*/
#include <bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define Long long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define forn(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define gc getchar_unlocked
#define PI acos(-1.0)
#define INF 1<<29
#define EPS 1e-9
#define Fr first
#define Sc second
#define Sz size()
#define lc ((n)<<1)
#define rc ((n)<<1|1)
#define db(x) cout << #x << " -> " << x << endl;
#define Di(n) int n;si(n)
#define Dii(a,b) int a,b;si(a);si(b)
#define Diii(a,b,c) int a,b,c;si(a);si(b);si(c)
#define Si(n) si(n)
#define Sii(a,b) si(a);si(b)
#define Siii(a,b,c) si(a);si(b);si(c)
#define min(a,b) ((a)>(b) ? (b) : (a) )
#define max(a,b) ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}
/*************************** END OF TEMPLATE ****************************/
const int N = 104;
string A,B;
string dp[N][N];
char a[N], b[N];
int main()
{
Di(t);
int cs = 0;
while(t--) {
scanf("%s %s",a+1, b+1);
int n = strlen(a+1) , m = strlen(b+1);
for(int i = 1; i <= n; i ++ ) {
for(int j = 1; j<= m ;j ++) {
dp[i][j]= dp[i-1][j];
if(dp[i][j-1].length() > dp[i][j].length()) dp[i][j] = dp[i][j-1];
else if(dp[i][j-1].length() == dp[i][j].length() && dp[i][j-1] < dp[i][j] ) dp[i][j] = dp[i][j-1];
if(a[i] == b[j]) {
if(dp[i-1][j-1].length() + 1 > dp[i][j].length() ) dp[i][j] = dp[i-1][j-1] + a[i];
else if(dp[i-1][j-1].length() + 1 == dp[i][j].length() && dp[i-1][j-1] + a[i] < dp[i][j] ) dp[i][j] = dp[i-1][j-1] + a[i];
}
}
}
if(dp[n][m] =="") printf("Case %d: :(\n",++cs);
else printf("Case %d: %s\n",++cs, dp[n][m].c_str());
}
return 0;
}
LOJ 1205 – Palindromic Numbers
Category : Digit DP
Observation:
1. If we select the half of the pallindrome, The next half is already fixed.
2. If Our current Number is smaller than The range, after adding next half, The number will always be small
Example: Lets We need to find the the number of palindrome in range 1…N.
N = 12345
Now if we select 11…, Then the rest will be always smaller than the range
/*
*************************
Id : Matrix.code
Task: 1205 - Palindromic Numbers
Date:
**************************
*/
#include <bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define Long long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define forn(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define gc getchar_unlocked
#define PI acos(-1.0)
#define INF 1<<29
#define EPS 1e-9
#define Fr first
#define Sc second
#define Sz size()
#define lc ((n)<<1)
#define rc ((n)<<1|1)
#define db(x) cout << #x << " -> " << x << endl;
#define Di(n) int n;si(n)
#define Dii(a,b) int a,b;si(a);si(b)
#define Diii(a,b,c) int a,b,c;si(a);si(b);si(c)
#define Si(n) si(n)
#define Sii(a,b) si(a);si(b)
#define Siii(a,b,c) si(a);si(b);si(c)
#define min(a,b) ((a)>(b) ? (b) : (a) )
#define max(a,b) ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}
/*************************** END OF TEMPLATE ****************************/
const int N = 1001;
int ar[20];
Long Memo[20][2][20];
Long var;
bool check(int index,int len)
{
int id = 0;
Long d = var;
int oo[20];
for( ; d ; id ++, d/=10) oo[id] = d%10;
for(int i= id-1; i> index; i-- ){
d= 10*d + oo[i];
}
for(int i = index + ((len%2)? 2 : 1); i < len ;i ++) {
d = d*10+oo[i];
}
if(d <= var) return 1;
return 0;
}
Long F(int ind, bool flag , int len)
{
if(ind == (len)/2 - 1){
if(flag && len) return check(ind,len);
return 1;
}
if(!flag && Memo[ind][flag][len] !=-1 ) return Memo[ind][flag][len];
Long res= 0,Lim = flag ? ar[ind] : 9;
for(int j= 0;j <= Lim ; j ++ ) {
res += F(ind-1, flag && (j==Lim) , j ? (len==0 ? ind +1 : len ): len);
}
if(flag) return res;
return Memo[ind][flag][len] = res;
}
Long Solve(Long a)
{
var = a;
int ind;
for(ind = 0; a; ind ++, a/=10) ar[ind]= a%10;
ms(Memo,-1);
return F(ind-1,true,0);
}
int main()
{
Di(t);
int cs = 0;
while(t--) {
Long a,b;
Sii(a,b);
if(a>b) swap(a,b);
printf("Case %d: %lld\n", ++cs, Solve(b) - Solve(a-1));
}
return 0;
}
LOJ – 1013 – Love Calculator
Link : Problem
Algo : DP
Let dp[i][j] -> The length of the shortest string that contains a[1…i] and b[1….j] as sub-sequence
Let dp2[i][j] -> Total number of unique shortest strings which contain a[1…i] and b[1….j] as sub-sequence
The recurrence relation :
if(a[i] == b[j] ) {
dp[i][j] = 1 + dp[i-1][j-1]; // Just add a[i] to the dp[i-1][j-1]
dp2[i][j] = dp2[i-1][j-1];
}
else {
dp[i][j] = 1 + min(dp[i][j-1] , dp[i-1][j]); // Check which one is minimum
if(dp[i][j-1] == dp[i-1][j]) dp2[i][j] = dp2[i][j-1] + dp2[i-1][j];
else dp2[i][j] = dp[i][j-1] < dp[i-1][j] ? dp2[i][j-1] : dp2[i-1][j];
}
Solution :
/*
*************************
Id : Matrix.code
Task: 1013 - Love Calculator
Date: 10/9/15.
**************************
*/
#include <bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define LL long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define forn(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define gc getchar_unlocked
#define PI acos(-1.0)
#define INF 1<<29
#define EPS 1e-9
#define Fr first
#define Sc second
#define Sz size()
#define lc ((n)<<1)
#define rc ((n)<<11)
#define db(x) cout << #x << " -> " << x << endl;
#define Di(n) int n;si(n)
#define Dii(a,b) int a,b;si(a);si(b)
#define Diii(a,b,c) int a,b,c;si(a);si(b);si(c)
#define min(a,b) ((a)>(b) ? (b) : (a) )
#define max(a,b) ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}template <class T> inline T bigmod(T p,T e,T M){LL ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return (T)ret;}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
void IN(){ freopen("in.txt","r",stdin); freopen("out.txt","w",stdout);}
/*************************** END OF TEMPLATE ****************************/
const int N = 35;
char a[N], b[N];
LL dp[N][N];
LL dp2[N][N];
int main()
{
Di(t);
int cs = 0;
while(t--){
scanf("%s %s", a+1,b+1);
for(int i=0;i<N;i++) dp[0][i]= dp[i][0] = i, dp2[i][0] = dp2[0][i] = 1;
int N1, N2;
for(int i=1;a[i]; i++ ) N1 = i;
for(int i=1;b[i]; i++ ) N2 = i;
for(int i=1; a[i] ; i ++) {
for(int j= 1; b[j] ; j ++ ) {
if(a[i] == b[j] ) {
dp[i][j] = 1 + dp[i-1][j-1];
dp2[i][j] = dp2[i-1][j-1];
}
else {
dp[i][j] = 1 + min(dp[i][j-1] , dp[i-1][j]);
if(dp[i][j-1] == dp[i-1][j]) dp2[i][j] = dp2[i][j-1] + dp2[i-1][j];
else dp2[i][j] = dp[i][j-1] < dp[i-1][j] ? dp2[i][j-1] : dp2[i-1][j];
}
//printf("%d %d %d\n", i,j,dp[i][j]);
}
}
printf("Case %d: %lld %lld\n",++cs, dp[N1][N2] , dp2[N1][N2]);
}
return 0;
}
Ternary Search
Discussion :
From Topcoder Blog,
Suppose you have a function f which is decreasing up to a certain point then increases (or vice versa) in the interval [a,b]. In the next paragraph, I assume decreasing first then increasing -- otherwise reverse the signs.
So, now let's say you want to find the point x in [a,b] such that f(x) is a minimum (the point of the switch). At the beginning, everything in [a,b] is a candidate. Pick numbers thirds along the way, (so pick g = a + (b-a)/3 and h = a + 2*(b-a)/3). You will calculate f(g) and f(h). If f(g) < f(h), either g and h are on opposite sides of the minimum point, or g and h are both to its right. So, we can be sure that x is not in [h,b] and can recurse on [a,h]. Otherwise, we can be sure that x is not in [a,g] and just recurse on [g,b].
Here is the code
min = a;
max = b;
while(max - min > epsilon){
g = min + (max-min)/3;
h = min + 2*(max-min)/3;
// f(h) or f(g) is the function to minimize
if(f(g) < f(h))
max = h;
else
min = g;
}
return (max+min)/2;
For further details See Topcoder
To understand whether a problem can be solved using Ternary Search should have a following property
1. The function need to be continuous in the interval [a,b]
2. The function has only one Maximum or minimum
If not , we would get a range where the value of the function is maximum/ minimum.
3. The problem needs to minimize or maximize some value
Lets look at the following problem :
LIGHTOJ – 1146 – Closest Distance
We need to find the value for which The distance is minimum.
#include <bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define LL long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define forn(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define gc getchar_unlocked
#define PI acos(-1.0)
#define inf 1<<30
#define lc ((n)<<1)
#define rc ((n)<<1 |1)
#define db(x) cout << #x << " -> " << x << endl;
#define DI(n) int n;scanf("%d",&n)
#define DII(a,b) int a,b;scanf("%d %d",&a,&b)
#define DIII(a,b,c) int a,b,c;scanf("%d %d %d",&a,&b,&c)
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
inline void sc(int &x){
register int c = gc();
x = 0;
int neg = 0;
for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}
template <class T> inline T bigmod(T p,T e,T M){
LL ret = 1;
for(; e > 0; e >>= 1){
if(e & 1) ret = (ret * p) % M;
p = (p * p) % M;
} return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
template <class T > inline void extEuclid(T a, T b, T &x, T &y, T &gcd) {
x = 0; y = 1; gcd = b;
T m, n, q, r;
for (T u=1, v=0; a != 0; gcd=a, a=r) {
q = gcd / a; r = gcd % a;
m = x-u*q; n = y-v*q;
x=u; y=v; u=m; v=n;
}
}
// The result could be negative, if it's required to be positive, then add "m"
template <class T > inline T modInv(T n, T m) {
T x, y, gcd;
extEuclid(n, m, x, y, gcd);
if (gcd == 1) return x % m;
return 0;
}
/*************************** END OF TEMPLATE ****************************/
const int N = 10;
typedef long double LLDD;
struct PT {
LLDD x,y;
PT(){}
PT(LLDD x, LLDD y) : x(x), y(y) {}
PT(const PT &p) : x(p.x), y(p.y) {}
PT operator + (const PT &p) const { return PT(x+p.x , y + p.y);}
PT operator - (const PT &p) const { return PT(x-p.x , y - p.y);}
PT operator * (LLDD c) const { return PT(x*c,y*c);}
PT operator / (LLDD c) const { return PT(x/c,y/c);}
void scan()
{
int x1,y1;
scanf("%d %d",&x1,&y1);
x=x1,y=y1;
}
};
LLDD dot(PT p,PT q){ return p.x * q.x + p.y * q.y;}
LLDD cross(PT p,PT q) {return p.x*q.y - p.y*q.x;}
LLDD dist2(PT p,PT q) {return dot(p-q , p-q);}
LLDD DIM(PT p) {return sqrt(p.x*p.x+p.y*p.y);}
PT a,b,c,d;
double ab,cd;
double calc(double t)
{
PT A = a + (b-a)*t*ab/DIM(b-a);
PT C = c + (d-c)*t*cd/DIM(d-c);
return (dist2(A,C));
}
int main()
{
DI(tc);
int cs = 0;
while(tc--){
a.scan();
b.scan();
c.scan();
d.scan();
ab = sqrt(dist2(a,b));
cd = sqrt(dist2(c,d));
double low = 0, high = 1,ans= 1e18, f,g;
forn(i,100){
f = low + (high-low) / 3;
g = low + 2*(high-low)/3;
double df = calc(f);
double gf = calc(g);
if(df < gf) {
ans = min( ans , df);
high = g;
}
else {
ans = min(ans, gf );
low = f;
}
}
printf("Case %d: %.9lf\n", ++cs, sqrt(ans));
}
return 0;
}
Another problem : CF – 439/D
LightOj 1118
Proble Link : http://lightoj.com/volume_showproblem.php?problem=1118
Method : Geometry
Three situation can occur.
1. The circles don’t touch each other
2. The circle touch ( Two centre can lie in different region or One’s centre can lie on others areas)
3. One circle is completely inscribed on other
Here is some input
For case 1 :
0 0 10 20 0 5
For case 2 :
0 0 10 7 0 5
For case 3:
0 0 10 3 0 3
We need to handle each of the case
1st Case : The area is ZERO.
2nd Case : Need to calculate ??
3rd Case : Area of the smaller circle
For the 2nd case , See The picture
Now Code :
//
// main.cpp
// 1118 - Incredible Molecules
//
// Created by Repon Macbook on 12/22/14.
// Copyright (c) 2014 MAC. All rights reserved.
//
#include <bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define LL long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define forn(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define gc getchar_unlocked
#define PI acos(-1.0)
#define inf 1<<30
#define lc ((n)<<1)
#define rc ((n)<<1 |1)
#define db(x) cout << #x << " -> " << x << endl;
#define DI(n) int n;scanf("%d",&n)
#define DII(a,b) int a,b;scanf("%d %d",&a,&b)
#define DIII(a,b,c) int a,b,c;scanf("%d %d %d",&a,&b,&c)
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
inline void sc(int &x){
register int c = gc();
x = 0;
int neg = 0;
for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}
template <class T> inline T bigmod(T p,T e,T M){
LL ret = 1;
for(; e > 0; e >>= 1){
if(e & 1) ret = (ret * p) % M;
p = (p * p) % M;
} return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
template <class T > inline void extEuclid(T a, T b, T &x, T &y, T &gcd) {
x = 0; y = 1; gcd = b;
T m, n, q, r;
for (T u=1, v=0; a != 0; gcd=a, a=r) {
q = gcd / a; r = gcd % a;
m = x-u*q; n = y-v*q;
x=u; y=v; u=m; v=n;
}
}
// The result could be negative, if it's required to be positive, then add "m"
template <class T > inline T modInv(T n, T m) {
T x, y, gcd;
extEuclid(n, m, x, y, gcd);
if (gcd == 1) return x % m;
return 0;
}
/*************************** END OF TEMPLATE ****************************/
const int N = 10;
struct PT{
int x,y;
PT(int x,int y): x(x),y(y){}
};
int sqr(int a){return a*a;}
int dist2(PT a,PT b)
{
return sqr(a.x-b.x) + sqr(a.y-b.y);
}
int main()
{
DI(tc);
int cs = 0;
while(tc--){
DIII(x1,y1,r1);
DIII(x2,y2,r2);
if(r1<r2){
swap(x1,x2);
swap(y1,y2);
swap(r1,r2);
}
double d = sqrt(dist2(PT(x1,y1) , PT(x2,y2)));
if(r1+r2 <= d ) printf("Case %d: 0\n", ++cs) ;
else if(r1+r2 >=d && fabs(r1-r2) < d ) {
double ang1 = acos((r1*r1+d*d-r2*r2) / (2.*r1*d));
double ang2 = acos((r2*r2+d*d-r1*r1) / (2.*r2*d));
double Area = .5 * r1*r1*(2*ang1) - .5 * r1*r1*sin(2*ang1) + .5*r2*r2*(2*ang2) - .5*r2*r2*sin(2*ang2);
printf("Case %d: %.9lf\n" , ++cs , Area);
}
else {
double R = min(r1,r2);
printf("Case %d: %.9lf\n", ++cs, PI*R*R);
}
}
return 0;
}
LightOj – 1017 – Brush (III)
Problem Link : http://lightoj.com/volume_showproblem.php?problem=1017
Method : DP
#include <bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define LMT 106
#define ll long long
#define ull unsigned long long
#define MOD 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define FOR(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define gc getchar_unlocked
#define PI acos(-1.0)
#define inf 1<<30
#define lc ((n)<<1)
#define rc ((n)<<1 |1)
#define debug(x) cout<<#x<<"--> " << x << endl;
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
inline void sc(int &x)
{
register int c = gc();
x = 0;
int neg = 0;
for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}
template <class T> inline T bigmod(T p,T e,T M){
ll ret = 1;
for(; e > 0; e >>= 1){
if(e & 1) ret = (ret * p) % M;
p = (p * p) % M;
} return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
template <class T > inline void extEuclid(T a, T b, T &x, T &y, T &gcd) {
x = 0; y = 1; gcd = b;
T m, n, q, r;
for (T u=1, v=0; a != 0; gcd=a, a=r) {
q = gcd / a; r = gcd % a;
m = x-u*q; n = y-v*q;
x=u; y=v; u=m; v=n;
}
}
// The result could be negative, if it's required to be positive, then add "m"
template <class T > inline T modInv(T n, T m) {
T x, y, gcd;
extEuclid(n, m, x, y, gcd);
if (gcd == 1) return x % m;
return 0;
}
/*************************** END OF TEMPLATE ****************************/
int iAr[LMT];
int CS[LMT];
int SZ;
struct Node {
int val;
int index;
int howMany;
};
Node T[LMT];
int DP[LMT][LMT];
int C[LMT];
int cal (int index , int R )
{
if(index >= SZ || R <= 0 ) {
return 0;
}
if(DP[index][R] !=-1 ) return DP[index][R];
int Rp = C[index];
int p = 0;
p = max( CS[Rp] - (index ? CS[index - 1] : 0 ) + cal(Rp + 1 , R - 1) , cal(index + 1 , R ));
return DP[index][R] = p;
}
int bs( int H)
{
int low = 0 , high = SZ - 1 , mid , ans= - 1 ;
while(low <= high ) {
mid = (low + high ) / 2;
if(T[mid].val <= H ) {
ans = mid;
low = mid + 1;
}
else high = mid - 1;
}
return ans ;
}
int main()
{
int N , w , k , tc , cs = 0 , x, y ;
sc(tc);
while (tc -- ) {
sc(N);sc(w);sc(k);
for(int i = 0 ;i < N ;i ++ ) {
sc(x);sc(y);
iAr[i] = y;
}
sort(iAr, iAr + N );
int prv = iAr[0] , cnt = 1 , dif = 0;
for(int i = 1; i < N ; i ++ ) {
if(iAr[i] != prv) {
T[dif] = {prv , dif,cnt};
dif ++;
cnt = 1;
}
else cnt ++;
prv = iAr[i];
}
T[dif] = {prv , dif,cnt};
dif ++;
SZ = dif;
CS[0] = T[0].howMany;
for(int i = 1 ;i <dif ; i++ ){
CS[i] = T[i].howMany + CS[i-1];
}
for(int i = 0; i < dif ; i ++ ) {
int R = T[i].val + w;
C[i] = bs( R ) ;
}
ms(DP, -1);
int p = cal( 0 , k);
printf("Case %d: %d\n" , ++cs, p );
}
}
Code for Fun 