GlebsHP's blog

Разбор задач разминочного раунда Яндекс.Алгоритма 2018
By GlebsHP, history, 7 years ago, translation, In English

A. Time Through the Glass

Consider the movement of "real" and "reflected" hands. If "real" hands rotates for some angle, "reflected" hand passes exactly the same angle in other direction. Thus, the sum of angles of two hands is always equal 360 degrees. For each hand we will find its resulting position independently. For hour hand it is 12 minus the current position, while for minute hand it is 60 minus current position. In both cases we should not forget to replace 12 or 60 with 0.

B. Palindromic Feature

Consider some substring of the given string that is a palindrome. We can remove its first character and its last character and the string will remain a palindrome. Continue this process till the string length becomes two or three (depending on parity).

The number of substrings of length two or three is linear, same as their total length. Thus, we can apply naive algorithm to select optimum palindrome. If there is no palinromic substring of length two or three, print  - 1.

C. Divide Them All

To solve this problem we will use a simple geometry fact that a line split a circle in two parts of equal area if and only if this line passes through the circle center. Similarly, a line splits a rectangle in two parts of equal area if and only if it passes through the intersection point of its diagonals. In both cases, sufficiency follows from point symmetry and necessity can be shown by considering a line that passes through the center and is parallel to a given one.

Now we only need to check whether there exists a line that contains all the centers. For the sake of simplicity we will work with doubled coordinates to keep them integer. This allows us to get the center of the rectangle by computing the sum of coordinates of two opposite vertices.

If there are no more than two distinct points among the set of all center, the answer is definitely positive. Otherwise, consider any pair of distinct points and check that each center belongs to the line they define. To check whether three points a, b and c (a ≠ b) belong to one line we can compute the cross product of vectors b - a and

Unable to parse markup [type=CF_TEX]

. Overall complexity of this solution is O(n).

D. Interview Task

We would like to start with some lemmas.

Lemma 1. Any two neighboring integers are co-prime at any step.

Use math induction. Base case is trivial as 1 and 1 are co-prime. Consider the statement is correct for first n steps. Then, any integer produced during step n + 1 is a sum of two co-prime integers. However,

Unable to parse markup [type=CF_TEX]

, thus, any two neighbors are still co-prime.

Lemma 2. Each ordered pair of integers (a, b) appears as neighbors exactly once (and at one step only).

Proof by contradiction. Let k be the first step such that some ordered pair appeared for the second time. Denote this pair as (p, q) and

Unable to parse markup [type=CF_TEX]

is the step of another appearance o this pair. Without loss of generality let

Unable to parse markup [type=CF_TEX]

, then p was obtained as a sum of

Unable to parse markup [type=CF_TEX]

and q, thus during the steps i - 1 and k - 1 there was also a repetition of some pair, that produces a contradiction.

Lemma 3. Any ordered pair of co-prime integers will occur at some step.

Let p and q be neighbors at some step. Then, if

Unable to parse markup [type=CF_TEX]

it was obtained as a sum of

Unable to parse markup [type=CF_TEX]

and q, so they were neighbors on the previous step. Two steps behind we had either

Unable to parse markup [type=CF_TEX]

and q, or

Unable to parse markup [type=CF_TEX]

and

Unable to parse markup [type=CF_TEX]

(depending on which is greater,

Unable to parse markup [type=CF_TEX]

or q) and so one. The process is similar to Euclid algorithm and continues while we don't have 1 and x. Finally, pairs

Unable to parse markup [type=CF_TEX]

and

Unable to parse markup [type=CF_TEX]

always appear at step x$. Moving along the actions in backward direction we conclude that any of the intermediate pairs should appear during the process, thus, pair (p, q) also appears.

Notice, that we are only interested in the first n steps, as any integer, produced on step x is strictly greater than x. Now, as we know that any pair of co-prime integers occurs exactly once we would like to compute the number of pairs (p, q) such that

Unable to parse markup [type=CF_TEX]

and

Unable to parse markup [type=CF_TEX]

. if

Unable to parse markup [type=CF_TEX]

, then

Unable to parse markup [type=CF_TEX]

. It means we only have to compute Euler function of integer n.

Compute Euler function is a well-studied problem. This know this is a multiplicative function, so

Unable to parse markup [type=CF_TEX]

, the number of co-prime integers is

Unable to parse markup [type=CF_TEX]

. Factorization of n can be done in time.

E. Backup

In this problem we are given a rooted tree. At one step, one node is removed. If the node is being removed and its immediate ancestor is still present, the value in this ancestor is increased by 1 (initially all values are equal to 1). If the value of some node is equal to k, it should be removed at the next step. The goal is to maximize the number of step when root is removed.

Notice, that if the root has only k - 1 descendant we can remove the whole tree before touching the node n. Otherwise, descendants should be split in three sets: totally removed subtrees, subtrees with their root remaining, and one subtree, whose root is removed at the end causing the node n to be removed as well. Run depth-first search to compute the following value of dynamic programming:

Unable to parse markup [type=CF_TEX]

is the number of nodes we can remove in subtree of v if we are allowed to remove v at any point. One can show that

Unable to parse markup [type=CF_TEX]

equals the total number of nodes in the subtree.

Unable to parse markup [type=CF_TEX]

is the number of nodes we can remove in subtree of v if we are not allowed to touch node v. If there are less than k - 1 descendants,

Unable to parse markup [type=CF_TEX]

is equal to

Unable to parse markup [type=CF_TEX]

. Otherwise, we should pick k - 2 descendant to use value

Unable to parse markup [type=CF_TEX]

, while for other we use

Unable to parse markup [type=CF_TEX]

. This k - 2 descendants are selected by maximum value of

Unable to parse markup [type=CF_TEX]

.

Unable to parse markup [type=CF_TEX]

equal to the number of nodes we can remove if we are allowed to remove node v but this should be done at the very end. Value of

Unable to parse markup [type=CF_TEX]

is the final answer. We have to select some k - 2 descendants to use

Unable to parse markup [type=CF_TEX]

, one to use

Unable to parse markup [type=CF_TEX]

and for others we take

Unable to parse markup [type=CF_TEX]

. Try every descendant as a candidate for

Unable to parse markup [type=CF_TEX]

and for other use greedy algorithm to pick best

Unable to parse markup [type=CF_TEX]

. Precompute the sorted array of all descendants and compute the sum of k - 2 best. If descendant x to be used with

Unable to parse markup [type=CF_TEX]

is among these k - 2 use the k - 1 (there should be at least k - 1 descendants, otherwise we destroy the whole subtree).

The overall complexity is .

F. Lying Processors

We are going to use the fact that

Unable to parse markup [type=CF_TEX]

and compute profile dynamic programming. If we already filled first i columns of the table and everything is correct for first i - 1 columns, we only need to know the state of last to columns in order to be able to continue.

Let

Unable to parse markup [type=CF_TEX]

, where i varies from 1 to m, m1 and m2 are bitmasks in range from 0 to

Unable to parse markup [type=CF_TEX]

mean the minimum number of processors required to fill first i columns in order to make first i - 1 columns correct and last two columns be filled as m1 and m2 respectively. The number of different states is

Unable to parse markup [type=CF_TEX]

. Finally, to compute the relaxations we try all possible masks

Unable to parse markup [type=CF_TEX]

for the new state

Unable to parse markup [type=CF_TEX]

.

Applying bit operations and some precomputations we obtain

Unable to parse markup [type=CF_TEX]

running time. We can speed it up a lot by precomputing all valid

Unable to parse markup [type=CF_TEX]

for a pair of

Unable to parse markup [type=CF_TEX]

.

Exercise: come up with

Unable to parse markup [type=CF_TEX]

solution.
  • Vote: I like it
  • +64
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by GlebsHP (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it +18 Vote: I do not like it
Faster solution to F
→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Your estimation can be improved. It seems you just count the number of independent sets in a rectangle 3 × n. But we can also use the conditions for truthful processors in the central column of this rectangle. This gives that the number of transitions is O(αn) where α is the largest root of x5 - x4 - 3x3 - 6x2 + 1, α ≈ 2.8.

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

What is wrong with this C code? Does not pass the 5th test.

#include <bits/stdc++.h>
using namespace std;
int x[100005], y[100005];
int main()
{ios_base::sync_with_stdio(0);
int n; cin>>n;
if (n<=2) {cout<<"Yes"; return 0;}
int r;
for (int i=0; i<n; i++)
{
    int t; cin>>t;
    if (t==0)  
    {cin>>r>>x[i]>>y[i];
     x[i]*=2;
     y[i]*=2;
    }
    else
    {
    int x1, y1, x2, y2, x3, y3, x4, y4;
    cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;
    x[i]=x2+x4; y[i]=y2+y4;
    }
}
for (int i=2;i<n;i++)
 if (((x[0]-x[i])*(y[1]-y[i])-(y[0]-y[i])*(x[1]-x[i]))!=0) {cout<<"No"; return 0;}
cout<<"Yes";
return 0;
}
→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it -7 Vote: I do not like it

This is my code for problem D, I don't understand wwhy it get wrong answer:

include<bits/stdc++.h>

using namespace std;

int main() { long long n; scanf("%lld",&n); if(n == 1) return !printf("2\n"); long long m = (long long)sqrtl(n); long long ans = n; for(long long i = 2;i <= m;++i) { int cnt = 0; while(n % i == 0) ++cnt,n /= i; if (cnt > 0) ans -= ans / i; } if(n > 1) --ans; printf("%lld\n",ans); }

→ Reply