Blog entries - Codeforces

#	User	Rating
1	ecnerwala	3649
2	Benq	3581
3	orzdevinwang	3570
4	Geothermal	3569
4	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3531
8	Radewoosh	3521
9	Um_nik	3482
10	jiangly	3468

#	User	Contrib.
1	maomao90	174
2	awoo	164
3	adamant	162
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	151
8	SecondThread	147
9	orz	146
10	pajenegod	145

snorkel's blog

How to order the points of polygon?

By snorkel, history, 23 months ago, In English

I have polygon and its vertices represented with randomly shuffled 2d points, how can I find the correct order?

In correct order I mean order so that segment between P[i] and P[(i + 1) % n] is a side of polygon.

Or if this is hard, how to solve it for 4 sides?

I'm looking for an efficient solutions. Many thanks.

Full text and comments »

snorkel
23 months ago
11

Let's expose some cheaters with this feature

By snorkel, history, 2 years ago, In English

Let's add to Codeforces profiles (probably not directly) stats — how many times a person was exposed to share a same solution code with somebody, at least they won't cheat with main accounts.

Full text and comments »

snorkel
2 years ago
0

Please add polls in Codeforces

By snorkel, history, 2 years ago, In English

Yes!

Because we could collect some statistics like: What percentage of competitive programmers touch type?

And it's not too bad to implement.

Full text and comments »

snorkel
2 years ago
4

Interesting range query problem

By snorkel, history, 3 years ago, In English

How to solve this problem?

Given an array of $$$n \leq 10^5$$$ positive integers ($$$\leq 10^9$$$) and an integer $$$m < 10^{14}$$$, find the subarrays with sum $$$\geq m$$$ and sum up their $$$min \cdot max$$$.

My Idea was to binary search from each position, then for a fixed $$$l$$$ we would have a range $$$[r_{min},n-1]$$$ of valid $$$r$$$-s. And then probably we need some kind of segment tree, but I wasn't able to figure out that.

Source — Problem 2

Thanks.

Full text and comments »

snorkel
3 years ago
7

Proof about spanning trees

By snorkel, history, 3 years ago, In English

Hi, let's consider this problem.

If you have a connected graph with edges colored red or blue, to find out whether you can construct the spanning tree with exactly $$$K$$$ number of blue edges then — find the minimum number of blue edges that can be used, also find the maximum. If $$$K$$$ is in $$$[min, max]$$$ then it's possible, otherwise, no.

What is the proof of it?

I was thinking like this — If it is possible to construct the tree with $$$A$$$ vertices, and also with $$$A + 2$$$ vertices, then $$$A + 1$$$ is also possible, but why, how? Can we probably relate the solution with $$$A$$$ vertices to $$$A + 2$$$ vertices?

Thanks.

Full text and comments »

snorkel
3 years ago
1

Coin changing variation

By snorkel, history, 3 years ago, In English

How to solve this problem about coin changing? Btw, it has a short problem statement.

Thanks.

Full text and comments »

snorkel
3 years ago
16

Interesting Sets CP problem

By snorkel, history, 3 years ago, In English

The problem can be found here.

Abridged problem statement: You are given $$$n$$$ bandits and each of them you should give some number of keys (subset of $$$1$$$ to $$$k$$$) such that to get every key ($$$1$$$..$$$k$$$) you should use at least $$$m$$$ bandits and not less! What is the value of $$$k$$$?

Full text and comments »

snorkel
3 years ago
6

Proof about Complete Graph

By snorkel, history, 3 years ago, In English

How do I prove that the Complete Graph with $$$n$$$ ($$$n$$$ is even) vertices can have as much as $$$n / 2$$$ disjoint spanning trees (spanning trees that does not share an edge between them)?

Full text and comments »

snorkel
3 years ago
8

Last non-zero digit of nPm

By snorkel, history, 3 years ago, In English

Trying to solve this problem. I got the last non-zero digit by working with $$$2$$$-s and $$$5$$$-s, but here's an easier solution by using $$$10$$$ directly.

Can anyone explain why this works? How taking modulo $$$10^9$$$ does not make it wrong?

Code

    for (int n, m;
         cin >> n >> m;) {

        long long ans = 1;
        for (int i = 0; i < m; i++) {
            int x = n - i;
            ans *= x;

            while (ans % 10 == 0)
                ans /= 10;

            ans %= (int) 1e9;
        }

        cout << ans % 10 << '\n';
    }

Thanks.

Full text and comments »

snorkel
3 years ago
33

Proof about powers of 10-s

By snorkel, history, 3 years ago, In English

Recently I was solving the problem which said that I have to find the smallest number consisting of only 1-s (1, 11, 111, ...) which will be divisible by the given number $$$n$$$. This problem is easy, but I was surprised that it is possible for any $$$n$$$ not divisible $$$2$$$ and $$$5$$$. (at least for $$$<= 100 000$$$). How can I prove this?

Full text and comments »

-7

snorkel
3 years ago
11

Proof about logarithms

By snorkel, history, 3 years ago, In English

Given numbers $$$1$$$ to $$$n$$$, we have to make all those number equal to zero by choosing some subset and subtracting same value from all of them, we have to use minimum number of operations.

My idea was to always split it into two parts and get two {$$$1,2..n/2-1,n/2$$$} sets from {$$$1,2,..n$$$} set and continue like this recursively. This approach is correct and leads to $$$ceil(log_2(n))$$$ solution. What is the proof this being optimal?

Full text and comments »

snorkel
3 years ago
4

Including project in CMakeLists.txt

By snorkel, history, 3 years ago, In English

How can I include a header file without writing #include "header.h" for example using cmakelists.txt?

For example without writing #define DEFINE I defined it from cmakelists with the command add_definitions(-DDEFINE)

Can I do the similar thing?

Full text and comments »

snorkel
3 years ago
7

Proof about tree diameter

By snorkel, history, 3 years ago, In English

What is the proof of the fact that: if we want to traverse the tree with the minimal cost then we should traverse through the diameter, so visit diameter edges once and visit other edges twice.

This is kinda obvious, but I can't find the proof of it.

Full text and comments »

snorkel
3 years ago
2

One by one multi-sources dijkstra

By snorkel, history, 3 years ago, In English

How to solve this kattis problem? It is a multi-source but not once, one by one. You should count the number of vertices with the distance at least k after each source is added. Restarting dijkstra every time is not enough.

Thanks.

Full text and comments »

snorkel
3 years ago
4

in Java I got with DFS — Memory Limit Exceeded, with BFS — Accepted

By snorkel, history, 3 years ago, In English

Recently I was solving the problem from kattis and typed DFS solution and got Memory Limit Exceeded, then I typed exactly the same thing in C++ and got AC. After not figuring out the fix, I went with BFS and it passed (in Java).

This is my DFS:

DFS Code

static boolean dfs(int i, int j, int climb) {
        if (i == n - 1 && j == m - 1)
            return true;

        vis[i][j] = true;

        boolean can = false;
        for (int di = -1; di <= +1; di++) {
            for (int dj = -1; dj <= +1; dj++) {
                if (abs(di) == abs(dj))
                    continue;

                int ii = i + di, jj = j + dj;
                if (ii < 0 || ii >= n || jj < 0 || jj >= m || vis[ii][jj] || g[ii][jj] - g[i][j] > climb)
                    continue;

                can |= dfs(ii, jj, climb);
            }
        }

        return can;
}

This is my BFS code:

BFS code

            boolean can = false;
            Queue<IntegerPair> q = new LinkedList<>();
            q.add(new IntegerPair(0, 0));
            vis[0][0] = true;

            while (!q.isEmpty()) {
                int i = q.peek().first, j = q.poll().second;
                if (i == n - 1 && j == m - 1) {
                    can = true;
                    break;
                }

                for (int di = -1; di <= +1; di++) {
                    for (int dj = -1; dj <= +1; dj++) {
                        if (abs(di) == abs(dj))
                            continue;

                        int ii = i + di, jj = j + dj;
                        if (ii < 0 || ii >= n || jj < 0 || jj >= m || vis[ii][jj] || g[ii][jj] - g[i][j] > mid)
                            continue;

                        vis[ii][jj] = true;
                        q.add(new IntegerPair(ii, jj));
                    }
                }
            }

Full Codes:

Full code - with DFS (MLE)

import java.io.*;
import java.util.*;
import java.util.function.*;

import static java.lang.Math.*;

public class Main {
    static final Scanner in = new Scanner(System.in);
    static final PrintWriter out = new PrintWriter(System.out);

    static int[][] g;
    static boolean[][] vis;
    static int n, m;

    public static void main(String[] args) throws IOException {
        n = in.nextInt();
        m = in.nextInt();
        g = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                g[i][j] = in.nextInt();
            }
        }

        int lo = -1, hi = (int) 1e9 + 5;

        while (hi - lo > 1) {
            int mid = lo + hi >> 1;

            vis = new boolean[n][m];
            if (dfs(0, 0, mid))
                hi = mid;
            else
                lo = mid;
        }

        out.println(hi);
        out.close();
    }

    static boolean dfs(int i, int j, int climb) {
        if (i == n - 1 && j == m - 1)
            return true;

        vis[i][j] = true;

        boolean can = false;
        for (int di = -1; di <= +1; di++) {
            for (int dj = -1; dj <= +1; dj++) {
                if (abs(di) == abs(dj))
                    continue;

                int ii = i + di, jj = j + dj;
                if (ii < 0 || ii >= n || jj < 0 || jj >= m || vis[ii][jj] || g[ii][jj] - g[i][j] > climb)
                    continue;

                can |= dfs(ii, jj, climb);
            }
        }

        return can;
    }
}

Full code - with BFS (AC)

import java.io.*;
import java.util.*;

import static java.lang.Math.*;

public class Main {
    static final Scanner in = new Scanner(System.in);
    static final PrintWriter out = new PrintWriter(System.out);

    static int[][] g;
    static boolean[][] vis;
    static int n, m;

    public static void main(String[] args) throws IOException {
        n = in.nextInt();
        m = in.nextInt();
        g = new int[n][m];
        vis = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                g[i][j] = in.nextInt();
            }
        }

        int lo = -1, hi = (int) 1e9 + 5;

        while (hi - lo > 1) {
            int mid = lo + hi >> 1;

            for (var i : vis)
                Arrays.fill(i, false);

            boolean can = false;
            Queue<IntegerPair> q = new LinkedList<>();
            q.add(new IntegerPair(0, 0));
            vis[0][0] = true;

            while (!q.isEmpty()) {
                int i = q.peek().first, j = q.poll().second;
                if (i == n - 1 && j == m - 1) {
                    can = true;
                    break;
                }

                for (int di = -1; di <= +1; di++) {
                    for (int dj = -1; dj <= +1; dj++) {
                        if (abs(di) == abs(dj))
                            continue;

                        int ii = i + di, jj = j + dj;
                        if (ii < 0 || ii >= n || jj < 0 || jj >= m || vis[ii][jj] || g[ii][jj] - g[i][j] > mid)
                            continue;

                        vis[ii][jj] = true;
                        q.add(new IntegerPair(ii, jj));
                    }
                }
            }

            if (can)
                hi = mid;
            else
                lo = mid;
        }

        out.println(hi);
        out.close();
    }

    static class IntegerPair implements Comparable<IntegerPair> {
        int first, second;
    
        public IntegerPair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    
        public IntegerPair(IntegerPair p) {
            this(p.first, p.second);
        }
    
        IntegerPair swapped() {
            return new IntegerPair(second, first);
        }
    
        @Override
        public int compareTo(IntegerPair o) {
            return first != o.first ? first - o.first : second - o.second;
        }
    
        @Override
        public String toString() {
            return String.format("[%d, %d]", first, second);
        }
    
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            IntegerPair that = (IntegerPair) o;
            return first == that.first && second == that.second;
        }
    
        @Override
        public int hashCode() {
            return Objects.hash(first, second);
        }
    }
}

What can cause this kind of thing?

Full text and comments »

snorkel
3 years ago
9

Column-wise MST in grid.

By snorkel, history, 3 years ago, In English

Please help me find the solution to this problem, which basically asks to find MST in grid which goes to all the columns from left to right. We can go to the adjacent cell in the grid (no diagonals).

There can be other solutions but I'm looking for one with Kruskal's or Prim's algorithm. Note that MST always has maximum weight edge as small as possible.

Thanks.

Full text and comments »

snorkel
3 years ago
4

ICPC WF 2011 Problem

By snorkel, history, 3 years ago, In English

Hello, I'm interested in the solution of "E — Coffee Central" from the following CF GYM contest. It's actually ICPC World Finals 2011 problem.

I've searched on internet but wasn't able to find the full solution. Some briefly mentioned you should rotate the points by 45 degree, but I don't understand why should I and how then proceed.

Full text and comments »

snorkel
3 years ago
5

Number of non-intersecting small sets (Repost)

By snorkel, history, 3 years ago, In English

Please help me solve the following problem:

Given N (N <= 100 000) small sets (size at most 7). find number of non-intersecting pairs among these sets.

Thanks for your attention.

P.S. I'm reposting this because the previous blog got heavily downvoted for nothing and does not get bumped up in the recent actions. Nobody has yet found the correct solution.

Full text and comments »

snorkel
3 years ago
4