Блог пользователя Wild_Hamster

Автор Wild_Hamster, 9 лет назад, По-русски

492A - Ваня и кубики.

По сути нужно выполнить то, что просят в условии. Находим в цикле максимальную высоту h, подсчитывая, сколько кубиков должно быть в i-м рядку и добавляя эти значения к результату. Выполняем цикл, пока результат не превышает n.

Авторское решение: 8924831

492B - Ваня и фонари.

Отсортируем фонари в порядке возрастания. Дальше найдем максимально возможное расстояние между двумя соседними фонарями, пусть это будет maxdist. Также учтем границы улицы, т.е. найдем расстояния от крайних фонарей к концам улицы (a[0] - 0) и (l - a[n - 1]). Ответом будет max(maxdist / 2, max(a[0] - 0, l - a[n - 1]))

Асимптотика по времени O(nlogn), учитывая сортировку.

Авторское решение: 8924823

492C - Ваня и экзамены.

Сортируем пары (ai, bi) в порядке возрастания по количеству рефератов bi, после этого проходимся от самого начала отсортированных пар и добавляем жадно по максимуму количество баллов, то есть добавляем значение min(avg * n - sum, r - ai), пока суммарное количество баллов не будет не меньше, чем avg * n.

Асимптотика по времени O(nlogn), учитывая сортировку.

Авторское решение: 8924807

492D - Ваня и компьютерная игра.

Создадим вектор rez размером x + y, в котором будут находится последовательность ударов Вани и Вовы за первую секунду. Для этого заведем 2 переменные cntx = cnty = 0. Дальше пока cntx < x и cnty < y, мы проверяем 3 условия:

1) Если (cntx + 1) / x > (cnty + 1) / y, то добавляем в вектор “Vova”, cnty++.

2) Если (cntx + 1) / x < (cnty + 1) / y, то добавляем в вектор “Vanya”, cntx++.

3) Если (cntx + 1) / x = (cnty + 1) / y, то добавляем в вектор “Both” 2 раза, cntx++, cnty++.

Дальше можем отвечать на каждый запрос за О(1), ответом будет rez[(ai - 1)mod(x + y)].

Асимптотика по времени O(x + y).

Авторское решение: 8924773

492E - Ваня и поле.

Поскольку gcd(dx, n) = gcd(dy, n) = 1, то Ваня сделает полный цикл за n движений. Сгруппируем все возможные пути в n групп, то есть те, что начинаются с точки (0, 0), (0, 1), …, (0, n - 1). Рассмотрим первый путь: он будет иметь вид (0, 0) - (dx, dy) - ((2 * dx) mod n, (2 * dy) mod n) - ... - (((n - 1) * dx) mod n, ((n - 1) * dy) mod n). Поскольку gcd(dx, n) = 1, то среди всех первых координат будут присутствовать все числа от 0 до n - 1. То есть можем занести в массив все соответствия между первой и второй координатой для пути с точки (0, 0), т.е. y[0] = 0, y[dx] = dy, ... , y[((n - 1) * dx) mod n] = ((n - 1) * dy) mod n. Теперь мы знаем, что все точки типа (i, y[i]), где 0 ≤ i ≤ n - 1, принадлежат к группе (0, 0). В таком случае точки типа (i, (y[i] + k)modn) принадлежат к группе (0, k). Тогда каждую точку (xi, yi) мы можем добавить к нужной группе k за О(1): (y[xi] + k) mod n = yi, k = (yi - y[xi] + n) mod n. Дальше просто ищем группу с максимальным количеством элементов, она и будет ответом.

Асимптотика по времени O(n).

Авторское решение: 8924746

  • Проголосовать: нравится
  • +50
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

I cant access the solution codes

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В задаче С в формуле min(avg * n - sum, r - bi) вместо bi разве не ai?

Поправьте если ошибаюсь.

»
9 лет назад, # |
Rev. 6   Проголосовать: нравится +3 Проголосовать: не нравится

В пункте D нужно поменять местами "Vova" и "Vanya".

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

There'a typo above for 492D — Vanya and Computer Game. It should be cnty++ in case 1 and cntx++ in case 2.

»
9 лет назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

Е: как-то и то же самое, но немного покороче 8925322

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Круто, а я еще думал, что у меня код короткий :D

»
9 лет назад, # |
Rev. 4   Проголосовать: нравится +8 Проголосовать: не нравится

Problem D can also be done using binary search.
Take an array of 0 to LCM(x,y). Player hitting at x would now hit at lx = LCM / x, similar for y. At every point P, number of hits = P/lx + P/ly. So, find the least point P such that number of hits is a % (x+y).
If both divide this point, then answer is both, otherwise the one who divides will be the answer.
Complexity -> O(log(x) + log(y)) per query.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Хоть много человек и сдало Е, но ведь в условии неопределенность. Если я заканчиваю в той же точке где и начал, то я вижу снова те яблони, которые были в этой точке:)

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

If (cntx + 1) / x = (cnty + 1) / y then why we add word “Both” 2 times and cntx++, cnty++. Can someone please explain.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    If i-th hit was in the same time with (i+1)-th hit, it mean that res[i]=both and it also mean that res[i+1]=both

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Here vector rez contain who will give i th hit.By (cntx+1)/x or (cnty+1)/y we are calculating the time need to perform cntx+1 th hit for x or cnty+1 th hit for y. If the times are same thats means two hit will be performed simultaneously. Let x perform 5 hits and y perform 4 hits in same time. So 8th hit and 9th hit will be performed simultaneously. If the monster die in 8th hit who will hit last? The answer is Both,because they hits simultaneously. Same for the 9th hit. So for 8th and 9th hit we will add Both in our vector.That is why when (cntx + 1) / x = (cnty + 1) / y then we add word “Both” 2 times in the vector.

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Deleted

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi! Can anyone explain the solution for problem D for this test case? 7 5 20 26 27 28 29 30 31 32

Vova makes first two strikes at 1/20 and 2/20, knocks first monster. -"Vova" Makes the next strike at 3/20 attacking the second monster. Then at 4/20, both attack together and knock second monster. So, "Both" Vova then again makes two strikes and knocks the third. "Vova" Similarly, they both knock the fourth. "Both" Where am I going wrong? PS: This is test 3

»
9 лет назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

Hi! Can anyone explain this test case for D? 7 5 20

26

27

28

29

30

31

32

Vova hits twice at 1/20 and 2/20 to knock out first monster. "Vova"

Then Vova strikes at 3/20 and Both strike at 4/20 to knock out the second monster. "Both"

Again, Vova strikes twice at 5/20 and 6/20 to knock out third.. and so on.

Why is the answer

Vova

Vova

Vova

Both

Both

Vova

Vova ?

PS: This is test 3.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    If Vova and Vanya hit at the same time, it will score as two hits. You could find it in notes of problem D:

    ''In the first sample Vanya makes the first hit at time 1 / 3, Vova makes the second hit at time 1 / 2, Vanya makes the third hit at time 2 / 3, and both boys make the fourth and fifth hit simultaneously at the time 1''.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I may be wrong, but in problem E:

shouldn't it be O(n+m)? I know that the bounds for n and m are of the same order so it shouldn't matter, just asking for technicality of the analysis.

Loved this contest, really nice problems! :)

»
9 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

For problem E, there is also an O(mlogm) solution.

Consider two points (x1, y1) and (x2, y2), if we start our move at point (x1, y1) and we can see point (x2, y2) along our path, then following equation will be true:

We can multiple each side by dx * dy and get this:

So we calculate value xi * dy - yi * dx for each apple tree and count frequency for each of these values by a data structure like map in C++. And answer is an apple tree at point (xi, yi) such that count[xi * dy - yi * dx] is maximum.

My submission: 8945734

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    good, we can do it without maps, since x1 * dy - y1 * dx(modn) < n, so it will be O(m). I tried to submit it and it got AC.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      In your solution memory complexity is O(n), My main target was achieve an efficient solution that is independent of parameter n.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I have the same solution like yours. In this case, we can archive an O(m log m) solution no matter what n is. :)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Nice solution :) Using unordered_map it should become clearly O(m)

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For problem D I have different approach that I think is correct ,but it gets wrong answer on test 11 .

So,idea is following :
We know that Vanya attacks with frequency x hits in second, and Vova y hits in second , 1/x and 1/y for 1 hit respectively or ( lcm(x,y)/x ) / lcm(x,y) and ( lcm(x,y)/y )/lcm(x,y) .Lets x1=lcm(x,y)/x and y1=lcm(x,y)/y.It's easy to see that if(n%(x1+x2)==0 or (n+1)%(x1+x2)==0) than answer is "Both" , after that lets k=y1/x1(lets assume y1>=x1) than if(n%(k+1)==0) than answer is person who shots less productively. Otherways answer is person who shots more productively. this is my solution .
Can you help me? Is my approach wrong?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    x=3, y=5 ==> k=1 Hits by user:

    1. Y
    2. X
    3. Y
    4. Y
    5. X
    6. Y
    7. Both
    8. Both
    

    Hits by your algorithm:

    1. Y
    2. X
    3. Y
    4. X
    5. Y
    6. X
    7. Both?
    8. Both?
    
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem C:

I got time limit exceeded during the system testing phase.

After contest, I compared my code with others and the only difference I found the array size.

I increased the array size and got accepted! But I don't understand why?

It is given N is 1<=N<=100000 and I took array of size 100005. Why this will give TLE? Can anyone explain please?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Please, give your codes links for clear understanding.

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    As far I saw in your last submissions, the size of array is not the main matter. You did another change in your accepted code which caused TLE before. That is in line 14:

    if(a.hw == b.hw) return a.score<=b.score; In the accepted code, you commented it. Thanks.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I don't get why the output of Test#1 B is 2.5000.

Check my drawing :P

The answer should be 2.0 not 2.5. I saw some solutions sorting for (nlogn) then doing 14 — 9 = 5/2 = 2.500 but this makes no sense if you think at it as the drawing. Don't see why you need to sort, if you can just pass a sliding window to find the biggest gap and divide by 2.0 to find that d = 2.0.

Please enlighten me ^^

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Latterns are points, not squares. So longest distance is 14 - 9 = 5,

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      No, It's not that, because if it was like you said, the second sample's answer should be 2.5 also.

      So, it's just that the answer provided in the editorial is wrong when either we consider the lanterns are squares or points in the middle of squares. So, that should be elaborated in the statement, then the editorial answer should be corrected.

      Sorry for the annoyance if it's existed.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem D can be done in O(log(x+y) + n), preprocess costs O(log(x+y)), each query costs O(1). Here is my solution http://codeforces.com/contest/492/submission/9386556

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

For problem C I think the note for the first sample input is wrong because it says he will get 1 point for writing 2 essays... Nevermind, it's 2 essays because that was the cost.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please fix my code

its not printing double values

include<bits/stdc++.h>

using namespace std;

int main(){ int n,l; double * a=new double[n];

for(int i=0;i<n;i++){
    cin>>a[i];
}

sort(a,a+n);

double rez=max(a[0],l-a[n-1]);

for(int i=1;i<n;i++){
    rez=max(rez,a[i]-a[i-1]);
}
cout<<rez/2;

}

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In qn B 3rd test case, i am getting answer as 22258200.0000000000 but it is given 22258199.5000000000 .

what should i modify ? I am already comparing and printing in float only with %0.10f precision in format specifier.

Here is my code 102146123

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In B qn , 3rd test case i got 22258200.0000000000 but it is given 22258199.5000000000.

I have already printing in float with %0.10f precision in format specifier.

Here's my code 102146123

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

in this question( 492B — Vanya and Lanterns ) after applying long double then also it is showing error in test-case 15 what can i do now??