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

14 лет назад, # |

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?

→ Ответить

14 лет назад, # |

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

→ Ответить

14 лет назад, # ^ |

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

→ Ответить

14 лет назад, # ^ |

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

→ Ответить

14 лет назад, # ^ |

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

→ Ответить

Rasifiel

14 лет назад, # ^ |

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

4
0011

→ Ответить

14 лет назад, # ^ |

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

→ Ответить

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

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

Babanin_Ivan

14 лет назад, # |

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

→ Ответить

14 лет назад, # ^ |

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

→ Ответить

steiner

14 лет назад, # ^ |

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

→ Ответить

14 лет назад, # ^ |

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

→ Ответить

primorial

14 лет назад, # ^ |

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

→ Ответить

vilcheuski

14 лет назад, # |

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

→ Ответить

1guangnian

14 лет назад, # |

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

→ Ответить

14 лет назад, # ^ |

+12

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

→ Ответить

14 лет назад, # |

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

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

→ Ответить

14 лет назад, # ^ |

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

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

→ Ответить

Ragvena

14 лет назад, # |

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

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

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

→ Ответить

14 лет назад, # ^ |

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

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

→ Ответить

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

14 лет назад, # |

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.

→ Ответить

14 лет назад, # ^ |

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.

→ Ответить

14 лет назад, # ^ |

My solution is dp instead of BFS.

I don't think BFS can work.

→ Ответить

vicky

14 лет назад, # ^ |

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

→ Ответить

vicky

14 лет назад, # ^ |

ma mail id: [email protected]

→ Ответить

http://codeforces.net/contest/49/status/E

14 лет назад, # ^ |

Ok.

I send you the code.

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

→ Ответить

vicky

14 лет назад, # ^ |

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

→ Ответить

ankit_shukla

14 лет назад, # ^ |

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.

→ Ответить

14 лет назад, # ^ |

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

14 лет назад, # ^ |

Thanx a lot..

→ Ответить

sas4eka

14 лет назад, # |

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

→ Ответить

sas4eka

14 лет назад, # ^ |

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

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

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

→ Ответить

flashmt

14 лет назад, # |

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

→ Ответить

wasi.ahmed

14 лет назад, # ^ |

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

→ Ответить

14 лет назад, # ^ |

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

14 лет назад, # ^ |

Is it unique?

→ Ответить

14 лет назад, # ^ |

what??

→ Ответить

flashmt

14 лет назад, # ^ |

The way to change given string into targer one.

→ Ответить

14 лет назад, # ^ |

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

14 лет назад, # |

there seems no case for the answer -1

→ Ответить

logic_max

14 лет назад, # |

Is answer for C unique?

→ Ответить

sas4eka

14 лет назад, # ^ |

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

→ Ответить

logic_max

14 лет назад, # ^ |

Yeah!
Thanks.

→ Ответить

1guangnian

14 лет назад, # |

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

14 лет назад, # |

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

→ Ответить

14 лет назад, # |

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

→ Ответить

mkagenius

14 лет назад, # ^ |

1 999

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

→ Ответить

gourav.bit

14 лет назад, # |

what is test case 8 for problem D ??

→ Ответить

Diego7

14 лет назад, # ^ |

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

→ Ответить

gourav.bit

14 лет назад, # |

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

→ Ответить

Diego7

14 лет назад, # ^ |

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.

→ Ответить

14 лет назад, # ^ |

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

14 лет назад, # ^ |

write your own pow then try....

→ Ответить

mkagenius

14 лет назад, # ^ |

And your program does outout 3 on my system.

This erratic behavior of pow caused me WA. :(

→ Ответить

007.chandru.vels

14 лет назад, # |

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

→ Ответить

fly-fly-fly

14 лет назад, # |

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

→ Ответить

Pouya.Payandeh

14 лет назад, # |

Why the ratings aren't updated???

→ Ответить

astrovsky

14 лет назад, # |

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

→ Ответить

golovozhop

14 лет назад, # |

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

→ Ответить

PavelKunyavskiy

14 лет назад, # ^ |

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

1000101001

1010101001

1010101011

1010101010

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

→ Ответить

golovozhop

14 лет назад, # ^ |

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

→ Ответить

giatuan

14 лет назад, # |

Can anyone tell me why this output is 3:

10
1000101001

output

Answer

1000101001->1010101001->1010101010 =>2?

→ Ответить

Garret

14 лет назад, # ^ |

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

→ Ответить

Darkstalker

14 лет назад, # ^ |

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. . .

→ Ответить

14 лет назад, # ^ |

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

14 лет назад, # ^ |

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

14 лет назад, # ^ |

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.

→ Ответить

14 лет назад, # ^ |

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

14 лет назад, # |

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

→ Ответить

astrovsky

14 лет назад, # ^ |

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

→ Ответить

giatuan

14 лет назад, # |

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.

→ Ответить