Notifications

Good job! You’re all caught up

Join challenges and check your notification settings if you don’t receive notifications. We’re actively adding new notifications. Read our blog post for more info

Notifications
TOSCA Editor - Web Application Wireframe Challenge (1)
Dismiss notification
Earlier Dismiss All
You have no more notifications

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 &amp;&amp; b >= 0 &amp;&amp; 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() &amp;&amp; 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 &amp;&amp; data.get(lo).get(1).equals(t[i]) || lo < n - 1 &amp;&amp; data.get(lo + 1).get(1).equals(t[i]))
           ans[i] = "Yes";
       else if(lo < n - 1 &amp;&amp; data.get(lo + 1).get(1).compareTo(t[i]) < 0 || lo >= 0 &amp;&amp; data.get(lo).get(0).equals(t[i]) &amp;&amp; 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 &amp; -p)  ans += fen[p];
            return ans;
        }
        void upd(int p, long v){
            for(p++; p <= maxn; p += p &amp; -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 &amp;&amp; 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;
    }

GET THE WHITEPAPER

APP DESIGN & DEVELOPMENT

DOWNLOAD TODAY

a.poorakhavan

Guest Blogger


categories & Tags


UNLEASH THE GIG ECONOMY. START A PROJECT OR TALK TO SALES
Close

Sign up for the Topcoder Monthly Customer Newsletter

Thank you

Your information has been successfully received

You will be redirected in 10 seconds