PavelKunyavskiy's blog

Codeforces Beta Round #73. Tutorial (Div2)
By PavelKunyavskiy, 14 years ago, translation, In English
Problem Div2-A. Chord.
First we need to understand a simple fact - the notes are actually residues modulo 12. It means the minor chord has the form {x, x +3, x +7} (mod 12), and the major one - {x, x +4, x +7}.

It is convenient to read the notes as strings, after that it is better to immediately replace them by a corresponding number from 0 to 11, that is, by their number. To perform the analysis, we needed to analyze consecutively the 6 possible orders in which the notes may follow one another in the chord. For each of the 6 orders we should check whether the chord is major or minor and if so, then immediately print the result.

There's no chord that would be major and minor at the same time - this is checked by the consecutive analysis of the six possible comparison systems.

Problem Div2-B. Keyboard.
Here we simply consecutively check for each letter of the alphabet in its two variants, uppercase and lowercase, whether it can be typed with one hand or not. And if we can't type it with one hand, we check whether it can be typed with two hands or can't be typed at all however how many hands one would use :-)
To verify let's consider several cases.
If the letter is lowercase, then we should simply check whether this letter is present on the keyboard, and if not, we do not type it.
If the letter is uppercase, then we must check for each key with the corresponding letter if there is a Shift nearby, simply checking all the key pairs on the keyboard one by one.
If there's no such letter or even a single Shift, then we do not type the letter as well.
If such pair was found, but the distance between the two keys is too long, then we need another hand to type the letter.
Let's sum (for all the text letters) the number of hands needed to type the text and terminate the problem with -1 if some letters just wouldn't be typed. The complexity is |T| + 52 * (n· m)2, which is quite enough.
  • Vote: I like it
  • +11
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
In Div-2 Problem B , why doesn't current position of our hand plays a role in determining the final answer.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    In this problem letters typed independently.
    → Reply
    • 10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      include<bits/stdc++.h> include <ext/pb_ds/assoc_container.hpp> include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; using namespace std;

      int main() { ios_base::sync_with_stdio(false);cin.tie(0); int n, m, x; cin >> n >> m >> x;

      vector<pair<int, int>> shifts; map<char, vector<pair<int, int>>> characters;

      for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { char cell; cin >> cell; if (cell == 'S') { shifts.push_back({i, j}); } else { characters[cell].push_back({i, j}); } } }

      int q; cin >> q;

      long long int cnt = 0; for (int i = 0; i < q; ++i) { char query; cin >> query;

      if (isupper(query) && shifts.empty()) {
    cout << -1 << endl;
    return 0;
}

char lowercase_query = tolower(query);
if (characters.count(lowercase_query)) 
{
    if (isupper(query)) {
        int p=INT_MAX;
        for (auto &char_position : characters[lowercase_query]) {
            int min_dist = INT_MAX;
            for (auto &shift_position : shifts) {
                int dist = abs(char_position.first - shift_position.first)*abs(char_position.first - shift_position.first) + abs(char_position.second - shift_position.second)*abs(char_position.second - shift_position.second);
                min_dist = min(min_dist, dist);
            }
            p=min(p,min_dist);

        }
        if (p > x*x) {
                cnt++;

            }
    }
} 
else {
    cout << -1 << endl;
    return 0;
}

      }

      cout << cnt << endl; return 0; } why i got tle in test51

      → Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Now I understood the solution.
And thanks for the good contest.
→ Reply
»
10 months ago, # |
  Vote: I like it -10 Vote: I do not like it

include<bits/stdc++.h>

include <ext/pb_ds/assoc_container.hpp>

include <ext/pb_ds/tree_policy.hpp>

using namespace std; using namespace __gnu_pbds; using namespace std;

int main() { ios_base::sync_with_stdio(false);cin.tie(0); int n, m, x; cin >> n >> m >> x;

vector<pair<int, int>> shifts;
map<char, vector<pair<int, int>>> characters;

for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
        char cell;
        cin >> cell;
        if (cell == 'S') {
            shifts.push_back({i, j});
        } else {
            characters[cell].push_back({i, j});
        }
    }
}

int q;
cin >> q;

long long int  cnt = 0;
for (int i = 0; i < q; ++i) {
    char query;
    cin >> query;

    if (isupper(query) && shifts.empty()) {
        cout << -1 << endl;
        return 0;
    }

    char lowercase_query = tolower(query);
    if (characters.count(lowercase_query)) 
    {
        if (isupper(query)) {
            int p=INT_MAX;
            for (auto &char_position : characters[lowercase_query]) {
                int min_dist = INT_MAX;
                for (auto &shift_position : shifts) {
                    int dist = abs(char_position.first - shift_position.first)*abs(char_position.first - shift_position.first) + abs(char_position.second - shift_position.second)*abs(char_position.second - shift_position.second);
                    min_dist = min(min_dist, dist);
                }
                p=min(p,min_dist);

            }
            if (p > x*x) {
                    cnt++;

                }
        }
    } 
    else {
        cout << -1 << endl;
        return 0;
    }
}

cout << cnt << endl;
return 0;

} why i got tle in test51

→ Reply