RAD's blog

Codeforces Round #161 Tutorial
By RAD, 12 years ago, In English

263A - Beautiful Matrix

If the single 1 is located on the intersection of the r-th row and the c-th column (1-based numeration), then the answer is |3 - r| + |3 - c|.

263B - Squares

If k > n, then the answer doesn't exist. Otherwise let's sort the squares by descending of their sizes. Now you can print any point that belongs to the k-th square and doesn't belong to the k + 1-th square. One of the possible answers is (ak, 0).

263C - Circle of Numbers

First of all, we have to check that each number occurs in the input exactly 4 times. If it's not true, then the answer definitely doesn't exist.

Otherwise, let's try to restore the circle. As cyclic shift of circle doesn't matter, let 1 to be the first number. As the second and the third number must be connected to each other and to 1, there are only few possibilities. So let's try them all. And when we know first three numbers, the rest of the circle could be easily and unambiguously restored in O(n). Just find a number, which is not included in the circle yet, and is connected to the last two numbers of the circle. Add this number to the resulting circle (as new last number), and repeat the procedure while possible. If we succeeded to add all the numbers to the circle, than the resulting circle is the answer.

263D - Cycle in Graph

Consider any simple path v1, v2, ..., vr which cannot be increased immediately (by adding a node to it's end, vr). In other words, all the neighbours of vr are already included in the path. Let's find the first node of the path (say, vl), which is connected to vr. It is clear that vl, vl + 1, ..., vr is a cycle and it contains all the neighbours of vr. But according to the problem's statement, each node has at least k neighbours. So length of the cycle is at least k + 1 ( + 1 is for node vr itself).

263E - Rhombus

Divide the rhombus of size k into 4 right-angled triangles as shown on a picture below. One of them has size k, two — size k - 1, and another one — size k - 2.

Let's solve the problem separately for each triangle. The most convenient way to do that is to rotate the input 4 times and run the same solving function 4 times. The result of this function will be a 2D array. Cell (x, y) indicates the answer we get if the right-angled vertex of triangle is located at cell (x, y). So it will be easy to combine 4 such arrays (just rotating and shifting properly) to get the actual answer for rhombus.

The main idea of the solution for triangle is the following. If we know the answer for a cell, we can easily move our triangle by one cell in any direction (right, down, left, or up) and recalculate the answer for that new cell in constant time. In fact, we need only 2 directions: right and down. And the values for top left corner should be calculated with straightforward cycles in O(k2) time.

More precisely, let's define 5 functions:

  1. The sum on diagonal segment of k elements:

  2. The sum on vertical segment of k elements:

  3. The weighted sum on vertical segment of k elements:

  4. The sum on a triangle:

  5. The weighted sum on a triangle:

Calculating the first 3 functions in O(nm) in total is quite obvious. Formulas for the others are following:

triangle(x, y + 1) = triangle(x, y) - diagonal(x, y - k + 1) + vertical(x, y + 1)

triangleWeighted(x, y + 1) = triangleWeighted(x, y) - triangle(x, y) + verticalWeighted(x, y + 1)

Formulas for moving in other directions are similar.

  • Vote: I like it
  • +58
  • Vote: I do not like it

Comments Comments (25)
| Write comment?
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You also need to mention that, for 263C - Circle of Numbers, how: - N=5 is trivial (any combination works) - N=6 there are 12/(6C2=)15 possible pairs, so ensure that the missing 3 pairs are not neighbours - N>6 probably your approach will work (N>=10 would be safest)

and also, please clarify what you mean by ..., there are only few possibilities. So let's try them all... For example, for N=1, say i discover that 1 is neighbours to 6 and 3, and 6 and 3 are neighbours to each other, it could be '1 (either 3 or 6) (either 3 or 6) ...' or '(either 3 or 6) 1 (either 3 or 6)...' What are you trying to say? maybe illustrate with a link to a AC submission, please.

much appreciated.

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Let's consider the number of the common neighbours of 1 and 3(say,t1) and the number of the common neighbours of 1 and 6(say,t2).

    If t1=2 and t2=1, then it should be 1 3 6.

    If t1=1 and t2=2, then it should be 1 6 3.

    If t1=2 and t2=2, then it should be 3 1 6.

    → Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

[deleted]

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

+1 for the tutorial! I hope that all next contests will have a similar one! And nice contest by the way :)

→ Reply
»
12 years ago, # |
  Vote: I like it +12 Vote: I do not like it

My solution to problem C is quite different from the tutorial:

  1. for n == 5, any combination will work;
  2. for n == 6, try all permutations;
  3. for n >= 7, scan every edge and see how many "triangles" can it construct; if it is two, then this edge should be a "side edge", i.e. two vertices are neighbors.

Triangle means: for an edge(u, v), there exists k that both edge(u, k) && edge(k, v) exist.

Special cases should be noted: the given graph may not be connected!

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't get it, why N = 6 is special case, can someone point it out please?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Actually I make use of this property: If N >= 7, then for three consecutive vertices (a, b, c), a will be connected with (d, e) and c will be connected with (f, g), and (d, e, f, g) will be distinct vertices. For N == 6, this property does not hold.

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For N>=7, nodes X and Y are next to each other in the circle iff their adjacency lists look like this:

    X(A,B,Y,E1) Y(A,B,X,E2)

    where E1 != E2.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    for special case, if each point is exactly connected to 4 other points and there're 2*n nodes, the whole graph must be connected

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Do you mean 2n edges? Consider this case: put two valid n=5 cases together to get an n=10 case, this graph is disconnected but all nodes is connected with 4 other nodes.

      → Reply
»
12 years ago, # |
  Vote: I like it +6 Vote: I do not like it

It was really unfair not to rejudge problem D as many clearly wrong solutions passed(see this thread) and thus decreased the point of the problem. My solution may fail too in rejudge but fair result should be ensured.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    take vertex = 1 + ( n * m + ( n ^ m ) + ( n & m ) + ( n | m ) ) % n; find max distance to all its neighbour, get accepted what is logic to solve it?

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anybody have an idea for the problem E ?

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I have wrote a solution in Chinese, anyone can view it. here is my blog

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is my approach for case N = 6 in problem C:

Because each node connects to exactly 4 others, there're always 3 pairs of nodes which are not neighbors. Find these 3 pairs and put them into the circle. Place node a of pair (a, b) in any position i from 1 to 3 (make sure it's still available), then place node b in position i + 3.

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I wonder why I got TLE in Div1.C by not checking if all numbers are repeated 4 times... It doesn't change the order, does it?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please explain me that why we use |3-x| + |3 — y| in beautiful matrix

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The problem asks to move the only '1' to the center of the matrix, which is located as (3, 3). For any position with (x, y), we need |x-3| + |y-3| steps to move it to the center. You may refer to Manhattan Distance for more details, and if you still have questions, welcome to discuss.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i am getting tle my code is for beautiful matrix question``

include include using namespace std;

int main() { int arr [5][5]; int x,y =0; for (int i = 1; i <=5; i++) { for (int j = 1; j <= 5; j++) { cin>>arr[i][j]; if (arr[i][j]== 1) { x =i ; y =j ;

} } } cout<<(abs(3-x)+abs(3-y)); return 0; } please help me out

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you use arr[5][5], then both i and j should not exceed 4. In other words, when i=5 or j=5, it leads to out of bound. You may use arr[6][6] instead.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why be have to take arr[6][6] as when we have to define an array we define it by its size ie is 5x5

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The index in general starts from 0, and thus for arr[5], we could only use arr[0], arr[1],...,arr[4]

        → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

A pretty neat trick for Problem A.

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define dbg(x) cout<<#x<<" "<<x<<endl;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
typedef vector<string> vs;

void solve() {
    int r=0,c=0;
    for(int i=1; i<=25; i++) {
        int tmp;
        cin>>tmp;
        if(tmp==1) {
            // dbg(i);
            r=(i-1)/5;
            c=(i-1)%5;
            break;
        }
    }
    // dbg(r);
    // dbg(c);
    cout<<abs(r-2)+abs(c-2)<<endl;
}

int main() {
    fastio;
    // int t;
    // cin>>t;
    // while(t--) {
        solve();
    // }
    return 0;
}
→ Reply