Archive

Archive for the ‘Algorithms’ Category

[URI ONLINE JUDGE] – 1477 – Man, Elephant and Mouse

April 1st, 2017 No comments

Link: https://www.urionlinejudge.com.br/judge/en/problems/view/1477

A very popular game in Nlogonia is called Man, Elephant and Mouse. It is typically played with only two players, and works as follows: each player secretly selects one of these three symbols, and after a countdown, both simultaneously reveal the symbol chosen through hand signals, extending in front his hands signaling the choice.

Man is represented by the closed hand, like the head of a man. The elephant is represented by the open hand showing five fingers, like the paw of the nlogonense elephant. Finally, the Rat is represented by the closed hand with the index finger and middle finger outstretched, as the ears of the little animal.

Figure 1: The three symbols of the game Man, Elephant and Mouse.

To determine the winner is very simple: the man always loses to the elephant (it is crushed under his paw), the elephant always loses to the mouse (because he is afraid of him and runs away) and the mouse always loses to the Man (which spreads traps to capture it). If two players use the same symbol, a tie occurs and the game is played again.

The inhabitants of Nlogonia, that are born strategists of Man, Elephant and Mouse, are using the following technique in the national championship, held every year: they always start playing man until the moment that this symbol cause tie with the most of their opponents. They then change its approach to the the winning symbol considering that they were using previously. Thus, players will switch to Elephant Man, then to Mouse, then they back again to Man.

To assist a famous foreign competitor in a game similar to this game Man, Elephant and Mouse, you will develop a program that counts how many players will use each symbol. Suppose all N players are arranged in a row and identified by their position, from 1 to N. Your program should handle with M commands of two types: change of symbol and count the frequency of these symbols. Both commands take a contiguous range of players in the queue to be considered.

Input

The input consists of several test cases. Each test case starts with a line containing two integers N (1 ≤ N ≤ 105) and M (0 ≤ M ≤ 106) which represent respectively the number of players in the tournament, and the number of operations.

The next M lines contain, each one, the description of an operation. Operations of  strategy changing will be represented by a line of the form “M A B” where A (1 ≤ A) and B (ABN) are integers. Players whose strategies are changed are those whose position in queue is between A and B, inclusive.

Counting operations are represented by a line of the form “C A B” where A and B are integers representing the range of players that should be considered in the count. Let’s consider that players whose position in the queue is between A and B, inclusive.

inclusive.

Output

For each operation, print a line containing three integers indicating respectly the number of Men, Elephant and Mouse symbols, that are used by the players in the given interval.

Print one blank line after each test case, including the last one.

Sample InputSample Output
10 7
C 1 10
M 5 6
C 5 6
M 6 7
C 4 8
M 1 10
C 1 10
5 6
M 1 5
M 2 4
M 1 2
M 4 5
C 1 5
C 3 4
10 0 0
0 2 0
2 2 1
1 7 2

2 0 3
1 0 1

 

my solution:

 

[code lang=cpp]
<br />#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define sz size

#define MAXN 100010

#define ms(x,v) memset((x), (v), sizeof(x))

#define cl_(x) ((x) << 1)
#define cr_(x) (((x) << 1) + 1)
#define _NO_USE_LOG
#ifdef _USE_LOG
#define LOG(x) cout << x;
#else
#define LOG(x)
#endif

using namespace std;

typedef long long L;
typedef pair<L,L> PL;
typedef vector<L> VL;
typedef vector<VL> VVL;
typedef vector<PL> VPL;
typedef vector<VPL>VVPL;

#define MAN 0
#define ELEPHANT 1
#define RAT 2

class SegTree
{
private:
int st[MAXN*8][3];
int lazy[MAXN*8];
int n_;

inline void add_(int *res, int *inc) {
for(int i = 0; i < 3; ++i) res[i] += inc[i];
}

void prop_(int u, int l, int r) {
if(lazy[u] == 1) {
swap(st[u][0], st[u][1]); // 0 1 2 -> 1 0 2
swap(st[u][0], st[u][2]); // 1 0 2 -> 2 0 1
}
else if(lazy[u] == 2) {
swap(st[u][0], st[u][2]); // 0 1 2 -> 2 1 0
swap(st[u][0], st[u][1]); // 2 1 0 -> 1 2 0
}

if(lazy[u] && l != r) {
lazy[cl_(u)] = (lazy[cl_(u)] + lazy[u]) % 3;
lazy[cr_(u)] = (lazy[cr_(u)] + lazy[u]) % 3;
}

lazy[u] = 0;
}

void query_(int u, int l, int r, int i, int j, int *res) {
prop_(u, l, r);
if(l > j || r < i) {}
else if(l >= i && r <= j){
add_(res, st[u]);
}
else{
query_(cl_(u), l, (l + r)/2, i, j, res);
query_(cr_(u), (l + r)/2 + 1, r, i, j, res);
}
}

void upd_(int u, int l, int r, int i, int j) {
prop_(u, l, r);
if(l > j || r < i) {}
else if(l >= i && r <= j) {
lazy[u] = 1;
prop_(u, l, r);
}
else {
upd_(cl_(u), l, (l + r) / 2, i , j);
upd_(cr_(u), (l + r) / 2 + 1, r, i , j);
ms(st[u], 0);
add_(st[u], st[cl_(u)]);
add_(st[u], st[cr_(u)]);
}
}

void build_(int u, int l, int r) {
lazy[u] = 0;
ms(st[u], 0);
if(l == r) {
st[u][0] = 1;
}
else {
build_(cl_(u), l, (l + r) / 2);
build_(cr_(u), (l + r) / 2 + 1, r);
add_(st[u], st[cl_(u)]);
add_(st[u], st[cr_(u)]);
}
}
public:
void init(int n) {
n_ = n;
build_(1, 0, n_);
}

void update(int l, int r) {
upd_(1, 0, n_, l, r);
}

void query(int l, int r, int *res) {
query_(1, 0, n_, l, r, res);
}

};

SegTree st;

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);

int n, m;
while(cin >> n >> m) {
st.init(n);
int queryRes[3];

for(int i = 0; i < m; ++i) {
char q;
int a, b;
cin >> q >> a >> b;
–a; –b;

if(q == 'C') {
ms(queryRes, 0);
st.query(a, b, queryRes);
cout << queryRes[0] << ' '
<< queryRes[1] << ' '
<< queryRes[2] << '\n';
}
else {
st.update(a, b);
}
}
cout << '\n';
}
}
[/code]

[URI ONLINE JUDGE] – 1476 – Trucks

April 1st, 2017 No comments

Link: https://www.urionlinejudge.com.br/judge/en/problems/view/1476

The Subtle Balloons Company (SBC) is the main balloon provider for programming contests; it has huge factories and warehouses, as well as an extensive truck fleet to ensure the contestants’ happiness. There are lots of competition sites in Nlogonia, and all of them hired SBC for supplying balloons for their contests. Nlogonia is an archipelago connected by several bridges. Every island of Nlogonia may have several regional sites and may also house several SBC warehouses. When planning the routes for balloon deliveries, SBC faced a problem: for safety issues, every bridge in Nlogonia has some maximum weight limit for vehicles which cross it. And because of the great net weight of the transported merchandise, SBC operations’ chief asked you to write a program to determine the maximum weight allowed to be transported between warehouses and competition sites.

Input

The input contains several test cases. The first line of a test case contains three integers N(2 ≤ N ≤ 2 × 104), M(1 ≤ M ≤ 105) and S(1 ≤ S ≤ 5 × 104) which indicate, respectively, the number of islands, the number of bridges that connect the islands and the number of sites. The islands are numbered from 1 to N. Each of the next M lines describes a bridge. The description of a bridge consists in a line with three integers A, B and W(0 ≤ W ≤ 105), indicating respectively the two islands connected by the bridge and the maximum weight allowed in that bridge, in tons. All bridges are two-way roads; every pair of islands is connected by at most one bridge; and it is possible to reach every other island in the archipelago using only bridges (naturally it may be needed to pass through other islands to do so). Each of the next S lines describe a competition site and contains two integers L and H indicating, respectively, the number of the island where this site is and the number of the island where the wharehouse which will be used to deliver the balloons to the site is. (1 ≤ A,B,L,HN, A != B, L != H)

Output

For each site in a test case, in the order they were given, your program must produce a single line, containing a single integer, the biggest weight which can be transported by truck from the warehouse to the site.

Sample InputSample Output
4 5 4
1 2 9
1 3 0
2 3 8
2 4 7
3 4 4
1 4
2 1
3 1
4 3
4 5 2
1 2 30
2 3 20
3 4 10
4 1 40
2 4 50
1 3
1 2
7
9
8
7
20
40

 

solution:

[code lang=cpp]
#include <bits/stdc++.h>
#define MAXN 20005
#define LOGTWON 15
#define cl(x) ((x) << 1)
#define cr(x) (((x) << 1) + 1)
#define INF 99999999
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

class RMQ{
private:
int _A[2 * MAXN], SpT[2 * MAXN][2 * LOGTWON];
public :
void build ( int n , int A[] ) {
for ( int i = 0 ; i < n ; ++i) {
_A[i] = A[i] ;
SpT[i][0] = i ;
}
for (int j = 1; (1 << j) <= n; ++j)
{
for (int i = 0 ; i + (1 << j) – 1 < n; ++i)
{
if (_A[SpT[i][j – 1]] < _A[SpT[i + (1 << (j – 1))][j – 1]])
SpT[i][j] = SpT[i][j – 1];
else SpT[i][j] = SpT[i + (1 << (j – 1))][j – 1];
}
}
}
int query(int i , int j){
int k = (int)floor(log((double)j – i + 1) / log(2.0));
if (_A[SpT[i][k]] <= _A[SpT[j – (1 << k) + 1][k]])
return SpT[i][k];
else return SpT[j – (1 << k) + 1][k];
}
};
class LCA{
private:
RMQ rmq;
int L[2 * MAXN], E[2 * MAXN], H[MAXN], idx;

void dfs(int cur, int depth, vvi &children)
{
H[cur] = idx;
E[idx] = cur;
L[idx++] = depth;
for (int i = 0 ; i < (int)children[cur].size(); ++i)
{
dfs(children[cur][i], depth + 1, children);
E[idx] = cur;
L[idx++] = depth;
}
}
public:
void build(vvi &children)
{
idx = 0;
memset(H, -1, sizeof H);
dfs(0, 0, children);
rmq.build(idx, L);
}
int query(int u, int v)
{
if (H[v] < H[u]) swap(u, v);
return E[rmq.query(H[u], H[v])];
}
};

class HLD{
private:
LCA lca;
int chainNo, chainPtr, n;
int chainHead[MAXN], chainPos[MAXN], chainInd[MAXN];
int arrBase[MAXN], tree_sz[MAXN], st[4 * MAXN], parent[MAXN];

void build_tree(int x, int l, int r)
{
if (l == r) st[x] = arrBase[l];
else
{
build_tree(cl(x), l, (l + r) / 2);
build_tree(cr(x), (l + r) / 2 + 1, r);

st[x] = min(st[cl(x)], st[cr(x)]);
}
}

int query_tree(int x, int l, int r, int i, int j)
{
if (j < l || i > r) return INF;

if (l >= i && r <= j) return st[x];

int ans1 = query_tree(cl(x), l, (l + r) / 2, i , j);
int ans2 = query_tree(cr(x), (l + r) / 2 + 1, r, i , j);
return min(ans1, ans2);
}

int query_up(int u, int v)
{
if (u == v) return INF;

int uchain, vchain = chainInd[v], ans = INF;
while (1)
{
uchain = chainInd[u];
if (uchain == vchain)
{
if (u == v) break;
ans = min(ans, query_tree(1, 0, n – 1, chainPos[v] + 1, chainPos[u]));
break;
}
ans = min(ans, query_tree(1, 0, n – 1, chainPos[chainHead[uchain]], chainPos[u]));
u = parent[chainHead[uchain]];
}
return ans;
}

int dfscnt(int u, vvi &children)
{
int v;
tree_sz[u] = 1;

for (int i = 0 ; i < (int)children[u].size(); ++i)
{
v = children[u][i];
parent[v] = u;
tree_sz[u] += dfscnt(v, children);
}

return tree_sz[u];
}

void hld(int u, int cst, vvi &children, vvi &costs){
arrBase[chainPtr] = cst;
if (chainHead[chainNo] == -1) chainHead[chainNo] = u;

chainInd[u] = chainNo; chainPos[u] = chainPtr++;

int ind = n, nc, v;

for (int i = 0; i < (int)children[u].size(); ++i)
{
v = children[u][i];
if (tree_sz[v] > tree_sz[ind]){
ind = v;
nc = costs[u][i];
}
}
if (ind == n) return;

hld(ind, nc, children, costs);
for (int i = 0 ; i < (int)children[u].size(); ++i)
{
v = children[u][i];
if (v != ind)
{
++chainNo;
hld(v, costs[u][i], children, costs);
}
}
}

public:
HLD(){
lca = LCA();
}

void build(vvi &children, vvi &costs){
memset(tree_sz, -1, sizeof tree_sz);

n = children.size();
dfscnt(0, children);

chainNo = 0;
memset(chainHead, -1, sizeof chainHead);

chainPtr = 0;

hld(0, INF, children, costs);

lca.build(children);
build_tree(1, 0, n – 1);
}
int query(int u, int v){

int l = lca.query(u, v);

return min(query_up(u, l), query_up(v, l));
}
};

HLD hld;
vector<pair<int, pair<int, int > > > edges;
vvi g;
vvi custo;
vvi mst;
vi pset;
void init(int n)
{
pset.assign(n, 0);
for (int i = 0 ; i < n ; ++i) pset[i] = i;
}

int find(int i)
{
return (pset[i] == i ? i : pset[i] = find(pset[i]));
}
bool same(int i, int j)
{
return find(i) == find(j);
}

void une(int i, int j)
{
pset[find(i)] = find(j);
}

void dfs(int u, int pai)
{
for (int i = 0 ; i < g[u].size(); ++i)
{
if (g[u][i] != pai)
{
mst[u].push_back(g[u][i]);
dfs(g[u][i], u);
}
else custo[u].erase(custo[u].begin() + i);
}
}

bool cmp(pair<int, pair<int, int> > a, pair<int, pair<int, int> > b)
{
return a.first > b.first;
}
int main()
{
int n, m, s;
int u, v, w;

ios_base :: sync_with_stdio(0); cin.tie(0);

while (cin >> n >> m >> s)
{
mst.assign(n, vi());
g.assign(n, vi());
custo.assign(n, vi());
edges.clear();
for (int i = 0 ; i < m ; ++i)
{
cin >> u >> v >> w;
–u; –v;
edges.push_back(make_pair(w, make_pair(u, v)));
}
sort(edges.begin(), edges.end(), cmp);
init(n);

for (int i = 0 ; i < edges.size(); ++i)
{
pair<int, pair<int, int> > u = edges[i];

if (!same(u.second.first, u.second.second))
{
une(u.second.first, u.second.second);

g[u.second.first].push_back(u.second.second);
g[u.second.second].push_back(u.second.first);

custo[u.second.first].push_back(u.first);
custo[u.second.second].push_back(u.first);
}
}
dfs(0, -1);
hld = HLD();
hld.build(mst, custo);

for (int i = 0 ; i < s; ++i)
{
cin >> u >> v;
–u; –v;

cout << hld.query(u, v) << '\n';
}
}
}
[/code]

My new world rank on URI Online Judge

June 23rd, 2016 No comments

Rank: #49 / 71506

2016-06-24_01-23-24.jpg

TimeCalc – Tính toán thời gian

June 10th, 2016 No comments

calendar

View on Github

Khai báo:

DateCalc dateCalc = new DateCalc(14, 5, 2016);

TimeCalc timeCalc = new TimeCalc();

 

 

1. Cho biết ngày dd/mm/yyyy là ngày thứ mấy: 

dateCalc.getWeekDay() => “Thursdays”

2. Tính số ngày trong tháng: 

dateCalc.getDayInMonth() => “31”

3. Đếm số ngày dựa vào 2 mốc thời gian: 

new DateCalc().countDaysBetweenTwoDate(2016, 5, 15, 2016, 1, 1)) => 135 ngày.

4. Cho biết tên của năm hiện tại theo CAN-CHI:

dateCalc.CANCHI() => “Binh Than”

5. Cho biết thế kỷ:

dateCalc.getCentury() => “21”

6. Đếm tổng số giây dựa vào 2 mốc thời gian:

timeCalc.getSecondsBetweenTwoDay(new DateCalc(15, 5, 2016), new DateCalc(13, 5, 2016)) => “172800 s”

7. Đếm tổng số phút dựa vào 2 mốc thời gian:

timeCalc.getMinutesBetweenTwoDay(new DateCalc(15, 5, 2016), new DateCalc(13, 5, 2016)) => “2880 m”

8. Đếm tổng số giờ dựa vào 2 mốc thời gian:

timeCalc.getHoursBetweenTwoDay(new DateCalc(15, 5, 2016), new DateCalc(13, 5, 2016)) => “48”

9. Tiết khí:

dateCalc.getTIETKHI() => “Tieu Tuyet”

10. Chuyển đổi âm lịch sang dương lịch:

[code lang=java]
<br />DateCalc l = new DateCalc(4, 4, 2015);
int[] solar = l.getSolar();
System.out.println(l.toString() + ” to solar is: ” + solar[0] + “/” + solar[1] + “/” + solar[2]);

[/code]

11. Chuyển đổi dương lịch sang âm lịch:

[code lang=java]
<br />DateCalc s = new DateCalc(4, 4, 2015);
int[] lunar = s.getLunar();
System.out.println(s.toString() + ” to lunar is: ” + lunar[0] + “/” + lunar[1] + “/” + lunar[2]);

[/code]

12. Kiểm tra năm nhuận:

dateCalc.isLeapYear() // return true if the year input is leap.

………..

 

Project đơn giản này chủ yếu phục vụ cho mục đích học tập, dành cho các bạn nào cần tham khảo có thể mở source ra xem.

Nếu có thắc mắc, muốn đóng góp hoặc phát hiện bugs có thể comment bên dưới hoặc gửi mail về địa chỉ: n@mhuy.xyz 

Categories: Algorithms, Java Tags:

One Button Has Multiple State

April 8th, 2016 No comments

When you use a button with Two states, you just simply use a variable as boolean type (True/False).

But when you need a button with multiple states, How to do this?

That’s very simple by using the following statement:

 

[code lang=cpp]
<br />int state = 0

yourClickEvent(){
state = (state + 1) % numberOfStateYouWant
}

[/code]

 

an Example when  numberOfStateYouWant = 3

drrg

 

Cheers.

Huy Nguyen

Categories: Algorithms, Tips & Tricks Tags: