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

Автокомментарий: текст был обновлен пользователем FalseMirror (предыдущая версия, новая версия, сравнить).

При попытке нажать на Решение задачи 983A выдает сообщение "недостаточно прав для просмотра страницы"

В разборе этой задачи, видимо, допущена опечатка: вместо q = q / gcd(p, q) нужно q = q / gcd(b, q)

Ну и в предложении "..., то есть простые делители q..." пропущено "существуют": ".., то есть существуют простые делители q, которые не являются простыми делителями b...".

Кстати, мне одному показалось, что задача C div2 была довольно сложная для обычного уровня таких задач? Сложность задач div2 после введения div3 повысилась?

Can't access codes. Thanks for the editorial though !

Your code(38299456) for problem Div2. C / Div1. A is not accessible. Please fix it.

Задачи интересные , без спор. Но не по духи КФ =). Div 2 задачи имею ввиду.

1) Задача A  -- очень очень легкая.

2) Задача B  -- легкая, но чуть больше кодид надо.

3) Задача C -- можно решать только и только по авторским идеям. Например, q | b^64  проверка всегда даёт TL.  cin, cout  - TL,  printf, scanf  gcd - TL.

4) Задача D -- чисто математический, незнаю как у других, но как прийти к выводу что f(a1, a2, ..,an) = f(a1, a2, .., a[n-1]) XOR f(a2, a3 ,..., an) ??? 
Это можно доказать через мат. индукций. Но найти сама формула очень сложно, мне кажеться.

5) Задача E -  Здесь ,кажеться, после C и D -- 90% людей не читал  =).

Прощу, за мою субъективное мнение.

The codes are accessible. Click on the "tutorial" link to reveal a "solution" link towards the end.

Can you prove that your optimization in A improves complexity? Or have you just put there some random opt and noticed that it significantly sped up on tests you prepared? The way it is put right now is for me kinda unserious.

Look here for relevant discussion: http://codeforces.me/blog/entry/59457?#comment-431043

Необходимо было применить некоторые оптимизации, чтобы уложиться в TL.

Вот что должно быть в разборе этой задачи, дак это анализ, почему куча участников в первой посылке получила ТЛ и почему их вторая посылка имеет лучшую асимптотику. Если авторы этот анализ не провели, то это очень серьезная ошибка (хоть здесь и повезло — скорее всего все соптимизировали действительно асимптотику): если бы нужны были неасимптотические оптимизации в А, здесь поднялось бы намного больше шума. Ну и вообще отсекать лог квадрат в самой простой задаче контеста, который все напишут, идея имхо не очень. Надеюсь, в претестах плохой тест был сразу? Боюсь представить, что было бы в комментах после фестиваля хаков.

Can anyone explain div2 C more clearly?

I think problem div 2 C the whole round and i can't figured it out till i read the tutorial and know that a problem is finite only if exist k that q | p*b^k. But how do we figure out this fact?If you know this fact,then the problem will be easily solved.

Sorry for poor English.

For Div 1.C, the state can be defined as: the number of employees that have already entered to the elevator (m), the destinations of the employees that are currently in the elevator (x₁, x₂, x₃, x₄) (x_i may be zero, which means the corresponding position is empty), and the floor where the elevator currently is (f). However, there are 2000 × 10⁴ × 9 ≈ 2e8 different states; to reduce the number of states, we may ''canonicalize'' destinations of the employees that are currently in the elevator, by sorting x₁, x₂, x₃, x₄ to make sure that they are in ascending order. Now the number of states is only about 1e7, which is small enough. Now we can directly perform BFS with memoization. For each state (m, x₁, x₂, x₃, x₄, f), we can

• Go up one floor, if f < 9;
• Go down one floor, if f > 1;
• Let one employee get out of the elevator, if x_i = f;
• Let the next employee get in the elevator, if x₁ = 0 && m < n && a_m + 1 = f;

Each of these operations takes exactly one second, so we do not need Dijkstra or other shortest path algorithm; BFS works here. Note that, we ''violate the atomicity'' of the second command described in the problem; however, it is not hard to prove that such violation won't imporove the final answer.

am i the only one solved div 1 C using BFS?

In div2 B in some test cases input says 100 n and 100 m but the input given was 5 n and varying m . My code is giving wrong answers on those types of cases. Please look upon it.

detailed explaination about div2 C. my proof to div 2.C(div 1. A)

UPD: Thanks to I_LOVE_SMRITI_KIRAN and thanglong, they find some unclear sentences and welcome you to give me more so that i can do it better. Here is what i rewrite.

For div 2 C, after dividing q by gcd(p,q), I calculate (b^(10e18))%q. The answer is finite if the result is 0 else infinite. Since q<10e18, the exponent of any of its prime factor is less than 64. So b^(10e18) should always be divisible by q if all prime factors of q are factors of b as well. Can anyone explain why this gives a wrong answer on test case 11?

Code: http://codeforces.me/contest/984/submission/38308682

I didn't like the way the last paragraph of 1E was written (took quite a bit to figure out), so for anyone who might be struggling to understand it, I hope this helps:

We have reduced the question to the following cleaner problem:

Given some paths in a tree, determine if there is a subpath between s_i and t_i. (2e5 queries on the same set of paths). If one is an ancestor of the other, we can possibly handle it together with the earlier binary lifting. Otherwise, this is equivalent to asking if there exists a path with endpoints in the subtrees of s_i and t_i.

Using the Euler's Tour technique, a subtree gets transformed into a range. So now each path can be represented by a start and an end point, and we want to know if there is some path which starts in the range corresponding to the subtree of s_i and ends in the range corresponding to the subtree of t_i (wlog assume s_i comes before t_i in the tour).

If we represent a path as a pair (a, b) -- the start and end points, we realise that this is an offline 2D range query. We now solve the black-boxed problem.

If we had a good bookcode for 2D segment tree we were confident in, we could stop here now, but we can do better since it is offline:

We will be using a 1D fenwick tree to count the number of points with x-coordinates in a certain range. Furthermore, for a rectangle, we will be making 2 queries: the number of points under the top of the rectangle and the number of points under the bottom of the rectangle (and we can then subtract).

We process points and queries simultaneously in increasing y-coordinate. Hence, when a query is processed, the fenwick tree on the x-coordinate reflects all points under the current y-coordinate which gives us what we require.

Did anyone do recursive dp solution for Div2 D / Div1B ?

"It's neccesary to do some optimizations to pass TL."

For Div1 A, I couldn't come up with the iterative reducing technique of Q until it reaches 1. Nice technique, by the way. To my surprise, java BigInteger worked within TL.

BigInteger Solution

Can anybody explain me please at div1 B, why f( l , r ) = f( l , r-1 ) ^ f( l+1 , r) ?

Div1C. Any relation with editorial and solution code? The definition of 'state' is different at least i think. The solution code is just representing the state in base of 10.

Can anybody point me to the proof of the maths applied in Div2 C problem

How to observe "dp[i][j] = dp[i — 1][j + 1] ^ dp[i — 1][j" in Div2 D or Div1 ?

Can someone give detailed explanation of Div 2 D. How the array dp[n][n] is formed?

q ∣ p⋅b^k Что означает верхний слеш | ?

In div1B , f(l,r) seems to be f(l,r-1) ^ f(l+1,r) , any intuitive or easy proof of this?

My code for div2C (div1A) is failing on the 7 case. Can someone please help me debug it?

Thanks in advance.

Code link

good problems in this problemset.

Anyone solved D with dp + segment tree? I observed how to calculate f values, but to calculate max value in range I used segment tree.

Thank you for the contest. However, I think the time limit for problem C div 2 is too tight. I tried your solution without fast input/output. It still got TLE. Here is my submission: http://codeforces.me/contest/983/submission/38354529.

I think it would be better if you consider to extend the time limit a little bit more next time.

...

Задача Div1E заходит и без двоичных подъемов. Просто люблю держать в курсе.

For Div 2 E, could someone explain how state is stored? I want to use an integer, so that the ith digit (i from 1 to 4) is the floor that the ith person wants to go. The 5th digit is the current floor the elevator is on. But there must be a better way.

Also, "The fast one is we say we go from the floor a[i] to the floor a[i + 1] and iterate over the persons who we let come in on the way." What does this mean?

What is the state of dp in DIV.2 D? Thanks in advance :-)

For the div1 D, how can I figure out this fantastic segment tree. it's to difficult for me to choose the three features to describe this problem... Please help me understand this algorithm further.. THX!

used priority queue but not working properly please help https://ideone.com/JE16M9

983A - Finite or not?

Tutorial says "...changes iterations of the first type and when it doesn't change — iterations of the second type."

I do not see two types of iterations. Can someone explain how that is meant?

Why is my submission for Div. 2C/1A wrong?

I'm checking if q divides b^k or not.

290874707