October 9, 2019 Single Round Match 767 Editorials
MojtabaMahdiDooz
If ‘W’ can be moved to the next cell, move it. If the next cell is ‘B’ and the next cell of the next cell is ‘-’, jump 2 cells.
public static String replace(String s, int p, char c){
return s.substring(0, p) + c + s.substring(p + 1);
}
public static String play(String board) {
for(int i = 0; ; i++)
if(i + 1 >= board.length() || board.charAt(i + 1) == 'B' && (i + 2 >= board.length() || board.charAt(i + 2) == 'B'))
return replace(replace(board, 0, '-'), i, 'W');
}
for i in range(50):
board = board.replace('W-','-W')
board = board.replace('WB-','-BW')
ArpaKonkoori
s = (a + b)(a – b). So (a + b) must be one of the divisors of s. For each divisor of s like div:
let div = (a + b) ⇒ s / div = (a – b)
⇒ a = (div + s / div) / 2, b = (div – s / div) / 2.
Check if gcd(a, b) is d or not.
private static long gcd(long a, long b){
return b != 0 ? gcd(b, a % b) : a;
}
public static long getA(long d, long s) {
for(long diff = 1; diff * diff <= s; diff++)
if(s % diff == 0){
long sum = s / diff;
long a = (sum + diff) / 2, b = sum - a;
System.err.println(String.format("%d %d %d %d", sum, diff, a, b));
if(sum % 2 == diff % 2 && b >= 0 && gcd(a, b) == d)
return a;
}
return -1;
}
if S % (D*D): return -1
maxA = -1
S //= D*D
for S1 in range(1,1000001):
if S1 * S1 > S: break
if S % S1: continue
S2 = S // S1
if (S1 % 2) != (S2 % 2): continue
A, B = (S1+S2) // 2, (S2-S1) // 2
if gcd(A,B) == 1:
maxA = max( maxA, A )
if maxA == -1: return -1
return maxA * D
MahdiJumping
One can build the graph simply. But using Dijkstra to find the distance will not work because of the constraint (n might be 5,000,000).
The solution is to keep the Dijkstra queue (or BFS queue), updated in another way. Consider a < b, and v is on the top of the queue. (v * A + B) % n must be inserted at the end of the queue. Consider we can find the correct position to insert v + 1 in the queue and keep the iterator. While going forward, the iterator goes forward.
So, we need to define the queue as linked list. Another solution is to keep two queues.
When we are on node v, d[u] < d[v] + a is satisfied for all of the elements in the first queue like u. Also, d[u] >= d[v] + a is satisfied for all of the elements in the second queue like u.
When you want to add v + 1 (which has and edge with weight a to v), add it at the end of the first queue. When you want to add (v * A + b) % n (which has and edge with weight b to v), add it at the end of the second queue.
Keep the first condition satisfied while going forward. While the first element of the second queue (let it be u) satisfy the condition d[u] < d[v] + a, pop it from the second queue and push it into the first one.
public static long minDis(int n, int A, int B, int a, int b) {
ArrayDeque<Integer> q1 = new ArrayDeque<>();
ArrayDeque<Integer> q2 = new ArrayDeque<>();
q1.addLast(0);
long d[] = new long[n];
for(int i = 1; i < n; i++)
d[i] = (long) 1e18;
d[0] = 0;
while (true){
if(q1.isEmpty()) {
q1.add(q2.getFirst());
q2.removeFirst();
}
Integer v = q1.getFirst();
q1.removeFirst();
if(v == n - 1)
return d[v];
while(!q2.isEmpty() && d[q2.getFirst()] < Math.min(d[v] + a, d[v] + b)) {
q1.addLast(q2.getFirst());
q2.removeFirst();
}
if(d[v + 1] > d[v] + a){
d[v + 1] = d[v] + a;
if(a > b)
q2.addLast(v + 1);
else
q1.addLast(v + 1);
}
if(d[(int) (((long) v * A + B) % n)] > d[v] + b){
d[(int) (((long) v * A + B) % n)] = d[v] + b;
if(a < b)
q2.addLast((int) (((long) v * A + B) % n));
else
q1.addLast((int) (((long) v * A + B) % n));
}
}
}
ArpaAsDevotee
There are several conditions to verify data:
- a[i] >= b[i]
- a[i] = a[j] ⇒ b[i] = b[j]
- a[i] > a[j] ⇒ b[j] = b[i] or b[i] > a[j]
To answer a query, find two adjacent a’s to t (using binary search is not necessary), you can find the answer easily. Check the solution for more information.
private final static int maxt = 86400, maxn = 50;
static class ArrayComparator implements Comparator<ArrayList<Integer> > {
@Override
public int compare(ArrayList<Integer> a, ArrayList<Integer> b) {
if(a.get(0) < b.get(0))
return -1;
if(a.get(0) > b.get(0))
return 1;
if(a.get(1) < b.get(1))
return -1;
if(a.get(1) > b.get(1))
return 1;
return 0;
}
}
public static String[] solve(int n, int q, int[] a, int[] lastSeen, int[] t){
ArrayList<ArrayList<Integer> > data = new ArrayList<>();
for (int i = 0; i < n; i++) {
ArrayList<Integer> tmp = new ArrayList<>();
tmp.add(a[i]);
tmp.add(lastSeen[i]);
data.add(tmp);
if(a[i] < lastSeen[i])
return new String[0];
}
data.sort(new ArrayComparator());
for(int i = 1; i < n; i++)
if(data.get(i).get(0).equals(data.get(i - 1).get(0))) {
if (!data.get(i).get(1).equals(data.get(i - 1).get(1)))
return new String[0];
}
else if(!(data.get(i).get(1).equals(data.get(i - 1).get(1)) || data.get(i).get(1) > data.get(i - 1).get(0)))
return new String[0];
String[] ans = new String[q];
for(int i = 0; i < q; i++){
int lo = 0, hi = n;
while(hi - lo > 1){
int mid = (lo + hi) / 2;
if(data.get(mid).get(0) <= t[i])
lo = mid;
else
hi = mid;
}
if(data.get(lo).get(0) > t[i])
lo--;
if(lo >= 0 && data.get(lo).get(1).equals(t[i]) || lo < n - 1 && data.get(lo + 1).get(1).equals(t[i]))
ans[i] = "Yes";
else if(lo < n - 1 && data.get(lo + 1).get(1).compareTo(t[i]) < 0 || lo >= 0 && data.get(lo).get(0).equals(t[i]) && data.get(lo).get(1).compareTo(t[i]) < 0)
ans[i] = "No";
else
ans[i] = "Not Sure";
}
return ans;
}
InThePathToMosque
Consider a query starting from a vertex like v. If we have a few liters of fuel, we’ll stop on v itself. Consider we pass the edge connecting v and its parent somehow, then we have at least 2 * (length of the edge from v to its parent) liters of fuel. So, if we stop on a vertex like u, the length of an edge connecting u to its parent is at least 2 * (length of the edge from v to its parent). So, for every value for f, answer to the query (starting from vertex v) can have at most O(log(10^9)) cases.
For each vertex, keep vertices that can be the answer to the query if we start from v (in the code below, block[v]). The remaining part is to handle parked cars. Keep a Fenwick tree. A Fenwick tree with updates on vertices and queries on the sum of values written on a path.
The code below can make everything clear.
private static int[] startingTime = new int[maxn];
private static int[] finishingTime = new int[maxn];
private static int[] topEdgeWeight = new int[maxn];
private static ArrayList<ArrayList<Integer>> g, blocks;
private static int[] par = new int[maxn];
private static long[] sumWeights = new long[maxn];
private static class Fenwick{
long[] fen = new long[maxn + 1];
Fenwick(){
Arrays.fill(fen, 0);
}
long get(int p){
p = startingTime[p];
long ans = 0;
for(p++; p != 0; p ^= p & -p) ans += fen[p];
return ans;
}
void upd(int p, long v){
for(p++; p <= maxn; p += p & -p)
fen[p] += v;
}
void upd(int l, int r, long v){ // adds v to range [l, r)
upd(l, v);
upd(r, -v);
}
void update(int vertex, long value){
upd(startingTime[vertex], finishingTime[vertex], value);
}
long getPath(int u, int par) {
return get(u) - get(par);
}
}
private static Integer currentTime = 0;
private static void getStartingTimeFinishingTime(int vertex){
startingTime[vertex] = currentTime++;
for (int i = 0; i < g.get(vertex).size(); i++) {
int u = g.get(vertex).get(i);
getStartingTimeFinishingTime(u);
}
finishingTime[vertex] = currentTime;
}
private static ArrayList<Integer> reverse(ArrayList<Integer> arrayList){
ArrayList<Integer> ret = new ArrayList<>();
for (int i = arrayList.size() - 1; i >= 0; i--)
ret.add(arrayList.get(i));
return ret;
}
private static void getBlocks(int v, ArrayDeque<Integer> bls) {
while (bls.size() > 1 && topEdgeWeight[bls.getLast()] <= 2 * topEdgeWeight[v])
bls.removeLast();
bls.addLast(v);
blocks.get(v).addAll(bls);
blocks.set(v, reverse(blocks.get(v)));
for (Integer u : g.get(v)) {
ArrayDeque<Integer> finalBls = new ArrayDeque<Integer>();
finalBls.addAll(bls);
getBlocks(u, finalBls);
}
}
public static long solve(int n, int q, int A, int B, int t){
currentTime = 0;
g = new ArrayList<>();
blocks = new ArrayList<>();
for (int i = 0; i < n; i++) {
g.add(new ArrayList<>());
blocks.add(new ArrayList<>());
}
int p = 0, w = 0;
for (int i = 1; i < n; i++) {
p = Math.max(0, (int) (i - ((long) p * A + B) % t - 1));
w = (int) (((long) w * A + B) % maxt);
g.get(p).add(i);
topEdgeWeight[i] = w;
par[i] = p;
sumWeights[i] = sumWeights[p] + w;
}
getStartingTimeFinishingTime(0);
getBlocks(0, new ArrayDeque<>());
Fenwick fenwick = new Fenwick();
int u = 0, f = 0;
long ans = 0;
for (int i = 0; i < q; i++) {
u = (int) (((long) u * A + B) % n);
f = (int) (((long) f * A + B) % maxt);
int v = -1;
for (int j = 0; j < blocks.get(u).size(); j++) {
v = blocks.get(u).get(j);
if (v == 0 || f + sumWeights[u] - sumWeights[v] + fenwick.getPath(u, par[v]) < topEdgeWeight[v])
break;
}
ans += v;
fenwick.update(v, f + sumWeights[u] - sumWeights[v] + fenwick.getPath(u, par[v]));
}
return ans;
}
Guest Blogger
