Polichka's blog

Codeforces Round #103 (Div. 2) Разбор Задач.
By Polichka, 13 years ago, translation, In English
Problem A

It's clear that the leftmost soldier with the maximum height should be the first and the rightmost soldier with the minimum height should be the last. Thus we will minimize the number of  swaps. And the answer is number of leftmost soldier with the maximum height - 1 + n - number of rightmost soldier with the minimum height. And if the leftmost soldier with the maximum height is more right then the rightmost soldier with the minimum height we should subtract one from the answer.

Problem B

Let's try to check all integer points of the table perimeter and add to the answer such of them that don't cover by circles of radiators. Let xa < xb and ya < yb, and if it's not true then swap xa and xb, ya and yb. So generals sit in the next integer points: (xa, y), (xb, y), (x, ya), (x, yb), where  xa ≤ x ≤ xb и ya ≤ y ≤ yb. We should be attentive when we count the generals who sits in points: (xa, ya), (xa, yb), (xb, ya), (xb, yb),  that don't count them twice.

Problem C

Let's count number of each letter in the second string and save it, for example, in array a[1..26]. For the first strings' prefix of length n, where n is the length of second string, (it's the first substring) we count number of each letter in array b[1..26]. We don't count characters ``\texttt{?}''. If there are b[i] ≤ a[i] for all i, then it's good substring. Then go to the second substring: subtract from the array b the first character:  b[s[1] - 'a' + 1] –  and add n + 1 character: b[s[n + 1] - 'a' + 1] +  + . If some of these characters is ``\texttt{?}'' then we shouldn't do for it the subtraction or addition. Then repeat the showed check and go to the next substring. Let's repeat this procedure for all substrings of length n.

Problem D

d[i] --- the minimum distance from vertex s to vertex i, that counted by algorithm of Dijkstra. "et's count the number of points on each edge of the graph that are on the distance l form the vertex s (and l --- the minimum distance from these points to s).

For edge (u, v):

if d[u] < l and l - d[u] < w(u, v) and w(u, v) - (l - d[u]) + d[v] > l then add to the answer the point on this edge, the distance of which to the vertex u is l - d[u];

if d[v] < l and l - d[v] < w(u, v) and w(u, v) - (l - d[v]) + d[u] > l then add to the answer the point on this edge, the distance of which to the vertex v is l - d[v];

if d[v] < l and d[u] < l and d[u] + d[v] + w(u, v) = 2 * l then add to the answer the point on this edge, the distance of which to the vertex v is l - d[v] and to the vertex u is l - d[u].

And if d[i] = l, then let's add to the answer this point.

Problem E

It's clear that the nearest squares of the secondary diagonal to some sportsman form the "segment" of the squares of the secondary diagonal. Let's write these segments for each sportsman.

Let's consider sportsmen so that we should compare to each sportsman excactly one square of the secondary diagonal from his "segment" and to each square of the secondary diagonal no more then one sportsman. It's clear that sportsmen can reach theirs squares without occupying the same square simultaneously with another sportsman. We should maximize the number of choosen sportsmen. And solution of this reformulated problem is greedy.
  • Vote: I like it
  • +51
  • Vote: I do not like it

Comments Comments (19)
| Write comment?
»
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Thank you for the contest and fast published tutorial :-)
→ Reply
»
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Actually I'm confused by how to greedy in Pro E... I have worked out the convertion, but didn't know how to solve the "segment" problem. THX
→ Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    After sorting the left endpoints of the segments, you loop through them, and use a priority queue (heap data structure) to repeatedly select the next non-intersecting segment with the leftmost possible right endpoint.

    By the way, the editorial's question marks are not displaying properly.

    → Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I still don't know about the solution to the Pro-E "segment" problem.Could you explain it more clearly?
Thanks a lot.
→ Reply
»
13 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Very sad that its impossible to get Accepted on problem B with Ruby.

Here is my code, may be some optimizations?
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Seems like you are iterating the whole grid... of course it'll get TLE.
    Try to iterate only cells of the frame of the rectangle.
    → Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
How to prove the correctness of problem A.
I simulate 2 times.
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    The solution is a greedy approach which is proved by contradiction. Consider the best case and assume it's not the one that your algorithm produces and then come up with a contradiction to prove its correctness.
    → Reply
»
13 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Can somebody help me with this (code) problem (C) ?

Something strange starts from test #13 (look at input params).

From problem statement:
The first line is non-empty string s, consisting of no more than 105 lowercase Latin letters and characters "?". The second line is non-empty string p, consisting of no more than 105 lowercase Latin letters.

PS.
Got Accepted, but the question remains.
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Are you talking about the cases that only have one line?

    I think maybe because the string in the first line is so long that the system can only show a small prefix of it. then the whole input file remained is ignored.

    eg.

    xxxxxxxxxxxxxxxxxx
    yyyyyyyyyyyyyyyyyy
    zzzzzzzzzzzzzzzzzz
    aaaaaaaaaaaaaaaaaa
    bbbbbbbbbbbbbbbbbb

    will looks like

    xxxxxxx...

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

    In Codeforces, large test case displays first 256 characters only, after which they show ellipsis (...)

    → Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Hello! I want to know why the Pro-D could use Dijkstra to solve? That the  complexity of Dijkstra is O(v^2), isn't it ? And this time , |V| <= 10^5. 
thanks, Happy new year ~!~
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    We can improve complexity to O(V × logE) using data structures to extract minimum in O(logn), for example, prority queue based on either binary heap or sorted set.
    → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

PROBLEM A I don't understand, what my mistake is, i'm getting wrong Answer on test case 4, everytime! I implemented everything according to the Tutorial only.

Can Any1 help me?


import java.util.*;
import java.lang.*;
import java.io.*;
public class CodeForces {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] heights = new int[n];

        for (int i=0; i<n; i++) {
            heights[i] = sc.nextInt();
        }

        int maxE = Integer.MIN_VALUE, minE = Integer.MAX_VALUE;
        int minP = -1, maxP = -1;

        for (int i=0; i<n; i++) {
            if (maxE<=heights[i]) {
                maxE = heights[i];
                maxP = i;
            } 
            if (heights[i]<=minE) {
                minE = heights[i];
                minP = i;
            }
        }
        // int result = 0;
        // if (maxP > minP) {
        //     result = maxP + (n - 1 - minP) - 1;
        // } else {
        //     result = maxP + (n - 1 - minP);
        // }

        int result=maxP-1+(n-minP)-(maxP>minP?1:0);

        System.out.println(result);

        // Close the scanner
        sc.close();
    }
    
}
→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, good job! you almost got it. Now, what did you miss? as we iterate through the array we need to get the first occurance of the max height and the last occurance of the min height. This is to decrease the time required to place the soldiers in their respective positions. Here's the accepted code:


    import java.util.*;
import java.lang.*;
import java.io.*;
public class Solution {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] heights = new int[n];

        for (int i=0; i<n; i++) {
            heights[i] = sc.nextInt();
        }

        int maxE = Integer.MIN_VALUE, minE = Integer.MAX_VALUE;
        int minP = -1, maxP = -1;

        for (int i=0; i<n; i++) {
            if (maxE<heights[i]) {
                maxE = heights[i];
                maxP = i;
            } 
            if (heights[i]<=minE) {
                minE = heights[i];
                minP = i;
            }
        }
        // int result = 0;
        // if (maxP > minP) {
        //     result = maxP + (n - 1 - minP) - 1;
        // } else {
        //     result = maxP + (n - 1 - minP);
        // }

        int result=maxP-1+(n-minP)-(maxP>minP?1:0);

        System.out.println(result);

        // Close the scanner
        sc.close();
    }
    
}
    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank You! That was impressive! I really did forget about that case!

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

Hi, I just started j hope this isn’t a stupid question but any idea my code doesn’t work?

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    int a[n];
    int maxIndex = 0;
    int minIndex = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (a[i] > a[maxIndex]) maxIndex = i;
        if (a[i] <= a[minIndex]) minIndex = i;
    }
    cout << maxIndex - 1 + (n - minIndex) - (maxIndex > minIndex ? 1 : 0);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}
→ Reply