Codeforces Beta Round #46 (Div. 2, Codeforces format)

15 лет назад, скрыть # |

Good Problems, but i have found that sentences in the question were not clear.

eg.Problem C He thinks that it does "not do to arrange" the book.
eg Problem B It was not written whether the numbers are Integer?

→ Ответить

15 лет назад, скрыть # |

В задаче D. там финальных ответа два: либо раскраска начинается с черной, либо с белой. И для каждых двух этих ответов смотрим разницу с нашим стрингом: c каким ответом разница меньше то и будет ответ...Это решение правильно?

→ Ответить

15 лет назад, скрыть # ^ |

Да. У меня такое решение только что прошло.

→ Ответить

15 лет назад, скрыть # ^ |

прошло в смысле претесты или все тесты?

→ Ответить

15 лет назад, скрыть # ^ |

Все основные тесты.

→ Ответить

Rasifiel

15 лет назад, скрыть # ^ |

Если считать разницей просто количество отличий, то нет.
Два теста:
4
1100

4
0011

→ Ответить

15 лет назад, скрыть # ^ |

Оба теста можно привести к 0101 или 1010. В обоих случаях количество различающихся позиций - 2 и ответ очевидно тоже 2.

→ Ответить

RAD	15 лет назад, скрыть # ^ \| 0 Почему нет? Разница в обоих случаях будет 2. Правильный ответ: выбрать пару 1-2 и получить 0100, выбрать 3-4 и получить 0101 → Ответить

RAD	15 лет назад, скрыть # ^ \| +1 Да, это правильно. → Ответить

Babanin_Ivan

15 лет назад, скрыть # |

Как доказать решение задачи C?

→ Ответить

15 лет назад, скрыть # ^ |

i=1 очевидно всегда будет делителем расстановки, а все остальные можно сделать не делителем, если на j-ое место поставить j+1-ый том, т.к. GCD(j, j + 1) = 1. Первый том поставить на оставшуюся последнюю позицию.

→ Ответить

steiner

15 лет назад, скрыть # ^ |

Какое именно решение? я выводил 2, 3, ..., n, 1. Числа k и k + 1 всегда взаимно просты, ну и 1, разумеется, взаимно просто с n.

→ Ответить

15 лет назад, скрыть # ^ |

Если n четное то ответ на i->i+1, i+1->i
Если n нечетное то ответ 1->1 2->3 3->2 а дальше как в случае с четным

→ Ответить

primorial

15 лет назад, скрыть # ^ |

Выводил n, 1, 2, 3... Решение и доказательство, по сути, аналогично описанному выше в данной ветке.

→ Ответить

vilcheuski

15 лет назад, скрыть # |

Что за тест 20 в задаче B?

→ Ответить

1guangnian

15 лет назад, скрыть # |

I didn't get the meaning of Problem C.What problem does it want us to solve?

→ Ответить

15 лет назад, скрыть # ^ |

+12

it just asked to minimize number of toms that is relatively prime to its position

→ Ответить

15 лет назад, скрыть # |

Спасибо за задачи!

Эх, жаль не рейтинговый для меня тур, да и вместо попыток взлома я пошел ужинать...

→ Ответить

15 лет назад, скрыть # ^ |

В этом то и плохая сторона участие вне конкурса, хотя когда дают пять задач на два часа времени для взлома не остается...

Кстати а на рейтинге видно что неофициально участвовал ?

→ Ответить

Ragvena

15 лет назад, скрыть # |

В первоначальном тексте задачи B была опечатка, которую потом исправили (результат сложения при основании 9 ). Но сообщение о поправке, по крайней мере мне, не пришло.

В вопросах его тоже не было. Обидно, потому что задачи как открыла после старта, так больше длительное время не обновляла.

С такой проблемой столкнулась только я?

→ Ответить

15 лет назад, скрыть # ^ |

По сути дела я не смотрел на детали. Я задачу понял примерно. Решил не писать сумму по основанию вручную, посчитал на Java (эх ленивый же я).

Но иногда можно и пролететь(со мной такое часто на Topcoder)

→ Ответить

RAD	15 лет назад, скрыть # ^ \| 0 Да, действительно была такая опечатка (для основания 9), но мы ее сразу исправили, как только узнали о ней. Приносим свои извинения. А вообще если сталкиваетесь с подобной опечаткой, и она мешает Вам решить задачу, лучше сразу задавайте вопрос жюри. → Ответить

15 лет назад, скрыть # |

Aha, a good contest with nice problems!

Problem C is not so easy to understand, but really interesting.The answer looks very easy,but hard to get.

Problem D confused me.I can't pass it till now. But also a good problem.

Problem E is really nice, I got a O(N⁴) dp after long thinking.

→ Ответить

15 лет назад, скрыть # ^ |

I wonder whether problem E can be solved using BFS....

if we have some string s1 we try to get shorter s2 by reverse operation described in problem. To avoid repetition we use memoization.

→ Ответить

15 лет назад, скрыть # ^ |

My solution is dp instead of BFS.

I don't think BFS can work.

→ Ответить

vicky

15 лет назад, скрыть # ^ |

can u share me ur code for prob E plz... i don hav any idea abt this

→ Ответить

vicky

15 лет назад, скрыть # ^ |

ma mail id: venkat.june11@gmail.com

→ Ответить

http://mirror.codeforces.com/contest/49/status/E

15 лет назад, скрыть # ^ |

Ok.

I send you the code.

By the way, you can look the code of anyone here:

→ Ответить

vicky

15 лет назад, скрыть # ^ |

ya i just found this feature! i'm new to code forces

→ Ответить

ankit_shukla

15 лет назад, скрыть # ^ |

Hey can you explain how u approached the problem E. I used kinda brute-force but got TLE on test case 8.
I dont need the code; just the approach would be quite helpful.

→ Ответить

15 лет назад, скрыть # ^ |

For example:

ababa
aba
2
c->ba
c->cc

The answer is :

ac =>

[a][baba]

[a][ba]

So, we can use dp[i][j]: the shortest common ancestor of a[1]...a[i] and b[1]...b[j].

dp["a"]["a"] = 1

dp["ababa"]["aba"] = dp["a"]["a"] + 1

If we know, "baba" & "ba" can generate by the same letter "c" , we can obtain the answer.

To get that, we also use a dp.

bool dp2[string][char]: can a string generate by the letter char.

But it cost O(N⁵) in time.

So we can compress it into an int.

→ Ответить

ankit_shukla

15 лет назад, скрыть # ^ |

Thanx a lot..

→ Ответить

sas4eka

15 лет назад, скрыть # |

Какой был тест 19 в задаче B?

→ Ответить

sas4eka

15 лет назад, скрыть # ^ |

Тест был таким:

Ввод
1 466
Ответ
3

З.Ы. Я думаю многие, как и я, не знали, но тесты можно увидеть под своим исходным кодом, кликнув на номер посылки в разделе "Мои посылки"

→ Ответить

flashmt

15 лет назад, скрыть # |

I used greedy algorithm for D and got AC (?!). How did you solve it?

→ Ответить

wasi.ahmed

15 лет назад, скрыть # ^ |

I used a DP with states (position, color of position-1)

→ Ответить

15 лет назад, скрыть # ^ |

We have only two possible anwers in the end:. one which starts with black and another starts with white.
(sort of chess coloring)

So we calculate the difference between our target string and our given string. (we choose minimal)
it's easy to see there always exist way of reduction of our string to the target function

→ Ответить

flashmt

15 лет назад, скрыть # ^ |

Is it unique?

→ Ответить

15 лет назад, скрыть # ^ |

what??

→ Ответить

flashmt

15 лет назад, скрыть # ^ |

The way to change given string into targer one.

→ Ответить

15 лет назад, скрыть # ^ |

no it's not
easy way to see it:
11101
target string:
10101
we could have chosen first and second as well as second and third

→ Ответить

1guangnian

15 лет назад, скрыть # |

there seems no case for the answer -1

→ Ответить

logic_max

15 лет назад, скрыть # |

Is answer for C unique?

→ Ответить

sas4eka

15 лет назад, скрыть # ^ |

No, for example:
n, 1, 2, ... , n-1
2, 3, ... , n-1, n, 1

→ Ответить

logic_max

15 лет назад, скрыть # ^ |

Yeah!
Thanks.

→ Ответить

1guangnian

15 лет назад, скрыть # |

What a pity!I have thought of the easy solution,but I can't figure out when the answer will be -1.So I want to judge it by DFS,but if failed

→ Ответить

Denor

15 лет назад, скрыть # |

Разбор задач будет?

→ Ответить

15 лет назад, скрыть # |

What is test21 for Problem B, i am getting WA?

→ Ответить

mkagenius

15 лет назад, скрыть # ^ |

1 999

I also got it wrong, finally found that pow function was not giving desired answer.

→ Ответить

gourav.bit

15 лет назад, скрыть # |

what is test case 8 for problem D ??

→ Ответить

Diego7

15 лет назад, скрыть # ^ |

You can see the test cases now if you look at your uploaded code!

→ Ответить

gourav.bit

15 лет назад, скрыть # |

i didnt get it , where to see the test case?

→ Ответить

Diego7

15 лет назад, скрыть # ^ |

Go to "My submissions" and click the id of your submission (in the "#" column, the first one). You can do it with others solved submissions too.

→ Ответить

15 лет назад, скрыть # ^ |

For problem B
-------------------My failed test case----

Test: #21, time: 10 ms., memory: 1316 KB, exit code: 0, checker exit code: 0, verdict: WRONG_ANSWER

Input

1 999

Output

Answer

Checker Log

wrong answer 1st numbers differ - expected: '4', found: '3'

------------------------------
When i run the program on my system i get Anser as 4 not 3
here is my program (i have removed the header files)

→ Ответить

mkagenius

15 лет назад, скрыть # ^ |

write your own pow then try....

→ Ответить

mkagenius

15 лет назад, скрыть # ^ |

And your program does outout 3 on my system.

This erratic behavior of pow caused me WA. :(

→ Ответить

007.chandru.vels

15 лет назад, скрыть # |

Can anyone give a glimpse of the solution for problem E?

→ Ответить

fly-fly-fly

15 лет назад, скрыть # |

Видимо, намного позднее)

→ Ответить

Pouya.Payandeh

15 лет назад, скрыть # |

Why the ratings aren't updated???

→ Ответить

astrovsky

15 лет назад, скрыть # |

как скоро обновят рейтинг? И интересно почему задержка в чём там проблемы?

→ Ответить

golovozhop

15 лет назад, скрыть # |

почему в задаче D в тесте 10 1000101001 нужно выдавать 3 а ни 2? (8й тест в системе)

→ Ответить

PavelKunyavskiy

15 лет назад, скрыть # ^ |

Корректная последовательность преобразований выглядит так

1000101001

1010101001

1010101011

1010101010

Сделано 3 действия. Сделать за 2 у вас не получится.

→ Ответить

golovozhop

15 лет назад, скрыть # ^ |

опять моя невнимательность

→ Ответить

giatuan

15 лет назад, скрыть # |

Can anyone tell me why this output is 3:

10
1000101001

output

Answer

1000101001->1010101001->1010101010 =>2?

→ Ответить

Garret

15 лет назад, скрыть # ^ |

It's because Petya can recolor two cells with one color only, you had recolored 01 -> 10 at a last step

→ Ответить

Darkstalker

15 лет назад, скрыть # ^ |

well i don't use spesial algorithm for solve this problem. Just using simple logic but I'm hard to understand it. . . and me got accepted. . . what a miracle. . .

→ Ответить

15 лет назад, скрыть # ^ |

There is actually a simple logic to do this question,

Finally the strip has to be like 1010.... or 0101.....

So basically you compare the input with both the two forms of the string and see the difference. Lets say the nth block doesnt match, then that means (n-1)th block has to be the same color as nth block and thus in one step you can paint it the right color.

Eg,

Input: 1101011

compare this with 1010101... we know the second position doesnt match, that means we simply take the 1st and the 2nd blocks and paint them the right way.

If two blocks don't match in a row that means they are of the opposite colors and you can't take them together and paint it... thus needing two steps... and similarly for 3 unmatching blocks you will take 3 steps etc. So basically you count the differences from both the types of final outputs and whichever one is smaller, you output that.

→ Ответить

Darkstalker

15 лет назад, скрыть # ^ |

aaaaa. . . that's what I mean. . . Actualy i'm not understand about BFS or another algorithm. . . Can you help me . . . I solve all problem with simple algorithm without know what algorithm i use to. . .

→ Ответить

http://www.codeproject.com/KB/java/BFSDFS.aspx

15 лет назад, скрыть # ^ |

BFS and DFS are two different types of search methods for graphs.

This link describes both the methods. Do not worry about the code snippets if you do not understand Java. Just understand the theory and you can have your own implementations.

→ Ответить

15 лет назад, скрыть # ^ |

In the second step,

10101010[01] -> 10101010[10]

This cannot be done as [01] are not of the same color.

You would have to do it in this order,

1010101001 -> 1010101011 -> 1010101010

→ Ответить

Denor

15 лет назад, скрыть # |

Напишите пожалуйста 10 тест к задаче D.

→ Ответить

astrovsky

15 лет назад, скрыть # ^ |

вообще-то тест на котором у вас ошибка вы можете увидеть клинкнув на ID своей посылки и пролистав немного вниз

→ Ответить

giatuan

15 лет назад, скрыть # |

Thanks all.Does anyone use BFS for prob E.My BFS for E : from S1 we create all the shortest ancestor of S1 by BFS ,the same with S2, then we compare all the ancestor of S1 and S2(using binary search) to find the result.

→ Ответить