Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

Um_nik's blog

By Um_nik, history, 2 weeks ago, ,

SharpIJustWantNegativeContribution

В этом году я не участник и не тренер, и в Питер не поехал, поэтому решил провести очень неофициальную трансляцию NEERC. Да, я буду тупо 5 часов жать F5 и иногда что-то говорить.

Ключевые особенности:
- не Снарк
- нет админки контеста
- не умею стримить
? нет обсуждения задач (не хочу их себе спойлерить)
? ярковыраженное обожание Moscow SU Red ?an?a
? скорее всего нецензурная лексика
? Руссиан ленгуаге
+ не Виталик Аксенов
+ нет интервью с Парфеновым и другими уважаемыми людьми
+ буду читать чат
+ в кадр будет заглядывать милейший песель

Скорее всего, будет скучно, но если вы все равно собираетесь следить за ходом контеста, то почему бы не делать это с очень непрофессиональной трансляцией, когда есть типа профессиональная.

Чтобы убедиться, что ничего не работает, в 17:30 (время Московское, это примерно через полчаса от публикации блога) начнется тестовый стрим, и я планирую в 18:00 начать виртуальное написание Lyft Level 5 Challenge 2018 — Elimination Round с лайв комментариями о том, что я пытаюсь делать. Опять же, язык русский. После стрима можно попытаться заставить меня порешать что-то еще.

Подписывайтесь, ставьте лайки на все 0 видео, жмите колокольчик, воруй-убивай.

•
• +49
•

By Um_nik, 2 months ago, ,

I wanted to write super-harsh blog but then I decided to split it into educational part and whining part. This is whining part. To read some cool stuff go here. This one will also be educational on a slightly different topic. And there will be A LOT of harsh stuff.

I'm not saying that I'm perfect. That round had some really bad problemsetting issues. Problem E was googleable, problem D had very weak tests against very stupid solution (so stupid that none of the authors and testers come up with it, moreover, it is so counter-intuitive that I don't know how so many people independently did it). In two constructive problems participants could look at jury's output, the feature of which I didn't know. And I'm sorry for these issues. BUT. This comment has very negative rating despite being so true. And no one are here to back me up. So I want to speak my truth as I always do.

Let me accompany you to the world of supposedly BAD STATEMENTS. aka statements written by Um_nik.

Problem C from 2nd division of CF Round #518 gets a lot of praise for having very bad statement. Let us look at clarification requests we get on this problem. My answers here are not answers to clarifications from real contest, they are my emotions.

I think that you should be ashamed for your clarifications so I will include handles. This is probably not ethical as a problemsetter to do it. But I don't care anymore. Maybe I will be banned from setting rounds on CF. That looks like a good thing for all of us. You don't want to solve my problems, I don't want to do anything good for you.

"Is it also necessary that if 2 colors harmonize each other they should be connected?" and similar
by sam29, arif.ozturk, aman28rwt, ryansee, Vshining, Gritsaev, goyal_sidds06, Huvok, seo, Nordway, Apptica, yuricardoso, sparsheatu, iGotMyEyesOnYou, ddeennyyss, chrome, SecondHandle, cjc, math_codet, GhostDrag, GhostDrag
Answer: Yes. That's what "if and only if" means. Literally. That is the meaning of these words.

"Excuse me, what is number k in prob C?"
by Gritsaev, dungdq2002, ddeennyyss
Answer: That's a good question, number k is not important for the problem, but I decided to introduce it to ensure that you'll understand that you should place only colored rooks on a chessboard.

"A,B harmonize; B,C harmonize; do A,C Harmonize?"
by harshit601, Fighter.human, Gudleyd, atrophy98, tshr
Answer: No. I have no idea where did you get it from. There is nothing resembling in the statement. Probably it's an attempt to explain some samples, but it is wrong on first sample.

"are there many solutions for sample tests or it's one solution only?"
by MohamedAhmed04, XMORE, __P_K_B__, mahdibuet3
Answer: Another good question, we made global clarification about this later. This was obvious from the samples, I think, but it was a mistake not to write it. I'm sorry.

"In the first sample, we can't go from the blue rook to every green rook!!" and similar
by cfalas, OmarBazaraa, showoff, DesiChamp, cjc, aman_shahi2, DesiChamp, showoff, S.Jindal
Answer: Samples are correct. Statement is correct.

by chan_iitp
"The statement looks like it was done with google translate, i don't understand anything"
by AlexArdelean

"if there is a harmonized pair (a,b). do the ans must contain a set of union of a and b? or i can arrange without any union set."
by sparsheatu
"if there is a harmonized pair (a,b). is it a must to make the both set of color a and b connected?" by sparsheatu
"And any rook of one color is connected with any other rook of another color that means all rook of 1st color is connected with all other rook of 2nd color if both color harmonise with each other?"
by Fighter.human
"Is it necessary for two rooks of different colors to be in one set?" by bktl1love
"What is harmonize of color??"
by Infinite_S
"can i connect colors other than the described in the input"
by KyRillos_BoshRa
"Specail Judge?"
by C20192413
Answer: Do you fucking read your questions? I like that "I can't solve the problem with operations in statement, can you provide better operations for me?"

Many questions just asking to clarify what the hell is happening in this hellish statement. There are a lot more stupid questions, I just tired.

Don't ask "please explain the problem, I don't understand it". We already did explain the problem. The thing called "statement". Read it. Carefully. Why do you think that we will come up with better explanation right now? We prepared this statement several days, we asked testers to read it and say if something is unclear.

Don't say that statement is bad because you can't understand it. The statement can be hard to understand because it requires some knowledge, not because it is badly written. And some statements require to know mathematical notation like "if and only if" in this particular case. I can't come up with better explanation of why there are so many people asking the same question. basically "what if and only if means".

Please assume that authors spend some time on your contest. Much more time than yours 2 hours. Because it is true.

You can remember that once I made round unrated because I found the mistake in authors solution. I didn't wrote a clarification "I think your problem suck" without explanation. I continued my attempts to solve the problem and waited for the end of the contest, then asked what is authors answer for my test. Because I expected that authors did their job well and too busy answering stupid questions during the round.

One more time I spend ~15 minutes trying to prove that my answer for sample is incorrect. When I did it, I send this clarification: "Are you sure that answer for third sample is 34? For me it seems that there are 3 valid trees, in each of them there are 6 possible ways to choose pair of vertices, and for each path there are two possible winning moves for Ember, so the answer should be 36." Compare this to what you do.

I also think that CF should abandon the practice of answering every clarification if possible. It will decrease the number of clarifications and decrease the time to answer one clarification. If I can answer "Read the problem statement", that should be the answer. If I can answer "No comments", that should be the answer.

The thing you did called bullying. There are people who downvote everything I write independent of content. Next there are people who disliked the consequences of my words, even my comment is correct. And there are also people who don't like that I'm saying my thoughts and don't respect their idols.

I liked first comment about "should stop creating problems", and first comment about this after the round. All others don't have own thoughts and have to repeat one thing over and over again. Now it is not a joke, it is being animals.

The same goes for "mind is weak". Yeah, guys, you are so original, it was not me who said it first.

To adequate people in this community: I'm tired of speaking truth. This not your truth? Explain me why am I not right, change my point of view. You think that I'm right in some cases? Speak it up. These animals can attack lone people, but if they will see that I'm not alone, they could think for once. You think that I have no right to insult people, but the idea is correct? Downvote me, say that wording is bad, but express that you agree with meaning.

MikeMirzayanov, I understand that for you quantity is more important than quality. I'm happy that you have your army of stupid fanatics who will write "You forget to hail Mike" under each post. This army has defeated me. Congrats.

•
• +157
•

By Um_nik, 2 months ago, ,

But Um_nik, we all know how to read, we have our whooping 2 month of experience! Oh, my sweet summer child, my experiments show that many people with kinda cool achievements like medals on ROI don't know how to read statements. But don't worry, I'll teach you. Well, probably you won't understand anything, because you didn't try to understand anything in your life, you expect all hard work to be done for you by someone else. Let's start!

Basic rules

• The result of reading the statement is usually pure math model. If story helps to build correct understanding, you can keep it, but still try to discard as many unnecessary details as possible.
• Imagine you want to tell the problem to someone else. What parts you want to tell? (According to my PM, this rule won't help you).
• Shorter = better.
• Simpler = better.
• Limitations are part of problem statement. Especially small limitations, because for small data you can try all the possibilities.
• Samples are part of problem statement. After building math model, check that you model working correct on samples, at least on small samples where you can check everything fast.
• Notes are part of problem statement.
• Try to find familiar patterns, maybe objects you already know something about. If you are given some connected graph with exactly one simple path between each pair of vertices, it's called tree. 4 letters instead of 12 words, see?
• Try even harder to spot something strange, something you not expecting. That probably will be the cornerstone of the problem.
• If there is some part of the statement you don't like, try to change that to something you like. Start with understanding the object, then simplify it. There are some problems which can be completely solved by this technique.
• If the model you get is very big, try to split it into some pieces. It would be great if pieces are independent, like 'solve problem1, then use its answer as input to problem2 and so on'.
• On first stages it can be useful to write your new statement. On paper. By hand.
• Problemsetters do not write random things in statements. But why would you believe me, since I'm a bad problemsetter? I don't know, maybe you shouldn't.

Some examples

I'll use Timus for almost all examples. If you see statement in Russian and you don't want to, there is a language switch in upper-left corner.
Assumed workflow: read the statement on Timus, try to understand and simplify it using the rules above. You don't have to read "solution" parts, but I warn you that my concept of reading statements works. I mean, "statement" parts will often contain huge hints to solution.
In most cases I won't write step-by-step explanations how I get the final version. You can say that that's not how teaching works. I can say that you don't want to study. I'll win, because that's my blog.

Statement
Solution

Magic Programmer

Statement
Solution

Scheduled Checking

Statement
Solution

Work for Robots

Statement

Coffee and Buns

Statement

Harder examples

Now I'll try to explain something.

GOV-internship 2

Statement
Solution

Martian Plates

Statement

Winnie the Pooh

Statement

Titan Ruins: Serial Control

Statement
Solution

Statement

Different math models will lead you to different solutions

Well, only if you have some patterns of how you should solve problems. And you should have them, patterns are good, they're the fastest way to solve problems.

Empire Strikes Back

Statement and Solution
Statement and Solution 2

Eliminating things you don't like can solve the problem

Last example in this blog will be not from Timus, it is 2016 Yandex.Algorithm Round 3, Problem F, shout-out to Endagorion for creating such pearl.

Problems visible only to participants, so I'll give already simplified problem statement here:

Given a tree, all vertices are initially white. Two players, Red and Blue, take turns coloring white vertices (surprise) red and blue. The game ends when there are no white vertices left. The score of the game is CR - CB, where CR is a number of connected components on red vertices, and CB is a number of connected components on blue vertices. Red wants to maximize the score, Blue wants to minimize it. Find the score if both play optimally. n ≤ 2·105.

Solution

•
• +381
•

By Um_nik, history, 3 months ago, translation, ,

I guess, for international readers all the important information is:

ICPC season 2019-2020, team KAN, Um_nik and someone who we hope to find using this blog.

If you are scared of us and want to skip this season, please do it, we want easy medals, thanks.

•
• +294
•

By Um_nik, history, 5 months ago, ,

Using Google Translate I read that this time only people living in Japan are allowed to participate (at least in the final round).

rng_58, can you confirm this?

Main reason for asking now is that the Finals date is 17.11 which is very close to TCO onsite dates (13.11-16.11).

•
• +83
•

By Um_nik, history, 7 months ago, translation, ,

I want to apologize once more for queue problems. It has also aggravated some tight ML/TL issues which probably would be not so big otherwise. I hope you enjoyed the problems nevertheless.

38799778

38799800 — logs
38799811 — case analisys

38799824

38799831

38799840

I hope that Petr is not mad at me for my joke.

38799850
38799853 — completely different solution with complexity O(6n / 2)

38799873

38799881

I hope that DarthPrince is not mad at me for my joke.

38799887

•
• +161
•

By Um_nik, history, 7 months ago, ,

Hello!

I'm glad to invite you all to Round 485 which will take place on Tuesday, May 29 at 18:35 UTC+3.

There will be 6 problems in each division, 3 of them are shared between divisions. 2 of div.2 problems created by KAN, 7 others created by me. The contest duration is 2 hours. My problems were originally used in HSE Championship.

I would like to thank Merkurev and GlebsHP with whom I discussed the problems, I_love_Tanya_Romanova for testing, KAN for round coordination and Codeforces and Polygon team for these beautiful platforms. I would also like to thank HSE for organizing the event. Oh, and kb. for writing great legend for one of the problems (he will be surprised).

For those who for some reason like to know score distribution in advance:
div.2: 500 — 1000 — 1250 — 1750 — 2250 — 3000
div.1: 500 — 1000 — 1750 — 2500 — 2750 — 3000
But I didn't properly discuss it with KAN so this is subject to change :)
UPD: Discussed with KAN, scores for C and D in div.2 increased by 250.

Good fun, have problems, read all the luck. As usual.

Oh, and if there will be no bad things, round will be rated. I hope.

I'm very sorry for issues with queue. I understand that it could ruin the contest for many of you. But please be understanding. Bad things happen. It could be some network problems or some electricity problems. MikeMirzayanov, KAN and other people behind Codeforces trying their best to provide good service. But sometimes it's very hard for some reasons. I hope that you enjoyed the problems despite all the bad things.

We decided that round will be rated.

Editorial will be posted tomorrow.

div.1 winners:
1. tourist
2. OO0OOO00O0OOO0O00OOO0OO
4. mcfx
5. LHiC

div.2 winners:
1. sminem
2. Fortza_Gabi_Tulba
3. cheburazshka
4. I_Love_KFC
5. CantGetAnyWaWhyImSoSmart

Editorial is up.

•
• +656
•

By Um_nik, history, 7 months ago, ,

Всем привет.

27 мая пройдёт личное первенство ВШЭ по спортивному программированию. К участию приглашаются (очевидно) студенты ВШЭ, а также школьники Москвы и Московской области, показавшие высокие результаты на региональном туре ВсОШ по информатике (500+ баллов, если у вас немного меньше, тоже можете подать заявку, если мы сможем вас разместить — разместим). Более подробную информацию можно прочитать здесь. Регистрация.

Задачки делаю я, другие плюшки — ФКН ВШЭ.

Ещё раз подчеркну — это не открытое первенство. Пожалуйста, не надо регистрироваться, если вы студент другого вуза :)

Дисклеймер и попытка ограничить количество участников: если ваш рейтинг ниже 1400, скорее всего вам будет весьма грустно на контесте.

На этих же задачах будет проведён Codeforces раунд 29 мая. Разумеется, о раунде будет ещё отдельное объявление :)

•
• +102
•

By Um_nik, history, 8 months ago, ,

Когда-то давно я хотел сделать канал с какими-то мыслями по поводу задач с регулярных контестов
Сегодня я даже что-то сделал
Получилось стремно, на мой взгляд
Но я надеюсь, что
1. кто-то кроме меня тоже захочет что-то писать
2. формат постепенно трансформируется во что-то прикольное

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

К сожалению, RUS only. Я не готов писать так много на английском.

Ну и раз уж зашла речь: У меня есть более персональный канал, но там тоже почти все про ACM. Настолько почти все, что канал даже был признан блогом года по версии snarknews :)

•
• +38
•

By Um_nik, history, 16 months ago, ,

I think that most of us know about situation with problem 843B - Interactive LowerBound. The intended solution (and it looks like all possible solutions) was randomized and it generates huge amount of hacks based on fixed randseeds.

I want to mention that I'm not against good randomized problems and I even set one myself.

But for me it seems that hacks can ruin such type of problems. The only thing author's solution is better than contestant's is that it is invisible during the competition. I can even imagine that some tester's solutions (maybe not the solution which is used to generate judge answers) was broken by some hacks.

I think that it breaks the problem as art piece and breaks the contest format too. You solved the problem just like authors wanted and now... it depends on is there a hacker in your room. It also breaks the idea of hacking. There is no bug in my solution, why should I be hacked? And why should the guy get 100 points for hacking me? He didn't crack my solution, he abused CF 'Run' tab.

And for me it looks like authors didn't think about that bug/feature and now they try to protect themselves in comments. For me it could be a good enough reason not to use this problem on CF round. This problem would be a good problem in ACM contest and I know that these guys do ACM contests. But maybe there were a way to prevent such abuse of hack system?

What about forbidding hacking this particular problem? It has two obvious flaws (maybe more).
1. After this post it can give a hint that you should use randomized solution — Yes, this is a problem.
2, All problems should be equal! You are taking away our sacred right to hack!!!1! — Are they? There are a lot of problems with no hacks on CF. There can be many reasons: the problem was too easy, or too hard, or it has no corner cases, or it can be solved only in one way, or, or... You can say that I propose unnatural way to prohibit hacking and in those cases it was prohibited by the problem itself. But (in my opinion) such randomized problem also naturally prohibits hacks because hacks can ruin the problem.

And it is also not true that all problems were 'equal' in this sense before. There were some problems with multitests which allow to hack with only one test in multitest. There can be a bug in handling multitesting but we cannot hack this bug.

This brings us to less cardinal solution: make some bounds on hacks. Like n ≤ 100 or (in this particular problem) let only choose values in list, but not their order.

Anyway, I think that problemsetters and coordinator should think about these matters in the future.

•
• +69
•

By Um_nik, history, 16 months ago, ,

cgy4ever, when will the round be? clist.by says that it will be tomorrow in 19:00 (MSK), but three days ago it was 18:00 (MSK) and I also cannot find anything related on TopCoder itself. For example, there is no such competition in Web Arena calendar.

•
• +47
•

By Um_nik, history, 20 months ago, ,

Я получил футболку с надписью "CODEFORCES THREADS 2017", но я не помню такого контеста.
С другой стороны, за Good bye 2016 обещали футболки.

Возможно, я не знаю какого-то перевода слова thread.

Так или иначе, MikeMirzayanov (или gKseni), можете рассказать, что это за футболка?)

•
• +12
•

By Um_nik, history, 2 years ago, ,

Suppose we want to solve a problem by doing binary search on answer. Then the answer will be checked against jury's answer by absolute or relative error (one of them should be smaller then ε). For simplicity we will assume that our answer is always greater than 1 and smaller than B. Because of that, we will always use relative error rather than absolute.

Suppose we have made n iterations of our binary search — what information do we have now? I state that we know that real answer is lying in some segment [xi, xi + 1], where 1 = x0 < x1 < ... < xi < ... < x2n = B. And what is great — we can choose all xi except for x0 and x2n.

Now, for simplicity, we will also assume that we will answer xi + 1 for segment [xi, xi + 1] and the real answer was xi — it is the worst case for us. It is obvious that we will not do that in real life, any other answer would be better, but you will get the idea.

So, what is our relative error? It is . Worst case for us is when relative error is maximal. It is logical to make them equal — exactly what we do by binary search with absolute errors. . We can assume that so . Now we have , but , so . How large should be n to get error less than ε? . Much smaller than .

How to write such binary search? We want to choose m in such a way that or simply .

Now I want to deal with some assumptions I made.

How to choose answer in the end? Again, (it is basically the same as dividing the segment in binary search).

What to do if the answer can be smaller than 1? Try 1; if answer is smaller than 1~--- use standard binary search (because absolute error smaller than relative); is answer is bigger than 1~--- use the binary search above.

P.S. I have never heard about this idea and come up with this while solving 744D - Hongcow Draws a Circle. I'm sorry if it is known for everyone except for me.

•
• +375
•

By Um_nik, history, 2 years ago, translation, ,

If you are registered on Timus, then you should have been received e-mail with invitation to this contest. The contest will be on 19 November in 11 Moscow time.

It was a junior championship but it was 'a little' harder than it was intended. As I remember, Merkurev solved all the problems with only 15 minutes to go, so I think that this contest may be interesting for participants with different levels, up to the strongest ACM teams.

The duration is 5 hours, standard ACM rules. It is a team (up to 3 participants) contest but you are welcome to partcipate individually too.

The authors of the problemset are Um_nik, Umqra, kb., Tinsane and dieglaube.

•
• +99
•

By Um_nik, history, 2 years ago, ,

Hello!

October Clash on HackerEarth has started and you have 23 more hours to go.

I am the author of this problemset and niyaznigmatul is a tester. I want to thank Umqra who helped me a lot with preparation.

I hope you find the problems interesting and wish you good luck!

•
• +47
•

By Um_nik, history, 2 years ago, ,

Q1: I'm a newbie. What should I do to become great coder?
A1: Stop doing competetive programming Solve problems.

Q2: I'm doing CP for two months and I'm still not red green. What should I do?
A2: You are lazy and impatient Solve more problems.

Q3: You became a red in less than two years, it is unbelievable!
A3: No, it isn't. You can do it too if you will solve fucking problems.

Q4: You became a red blah-blah-blah such a huge fan blah-blah. Oh, and what should I do to become as great as you?
A4: ... right. You already know the answer. Solve problems. I hate you.

Q5: I'm not good at DP [or something]. What can you suggest?
A5. Maybe you should try to stop asking stupid questions and solve some problems on DP? Or read some blogs and editorials.

Q6: I can't solve a problem / understand your code. Can you help me?
(Well, it is not a bad question in general. It is a good (if you really want me to explain something not to write the solution instead of you) question. But...)
A6: Sure. Can you provide the link to the problem / code?
(I'm not joking, it is a real story).

Bonus!
Q0: Hello bro/sir.

•
• +628
•

By Um_nik, history, 2 years ago, ,

Codeforces said 20 minutes ago when I was trying to login. The same was about two weeks ago. In both cases I was unable to login for about 10 minutes.
And I constantly logout. Sometimes I can't read 3-4 blog posts before logout.

There were a post about logouting two or three days ago but I can't find it now because search is not working too.

•
• +38
•

By Um_nik, history, 3 years ago, ,

I've noticed during the contest that we can see all the hacks in our room.

Now MikeMirzayanov says that it was a bug and will be fixed soon.

I think it really will be bad if there are tons of hacks. But it is very useful to know which problems can be hacked (I mean which problems was already hacked by someone). Can you add number of successfull and unsuccessfull hacks on each problem to the PROBLEMS page?

•
• +130
•

By Um_nik, history, 3 years ago, ,

Допустим, вы проводите соревнование для очень разной по силе аудитории. Например, у нас завтра отбор на ВКОШП.

В каком порядке вы бы стали рассказывать задачи на разборе?

Можно рассказывать в порядке A, B, C ... Правда, если в середине встретится сложная задача, то слабые участники могут забить и перестать слушать.

Логичное решение: давайте отсортируем задачи в порядке предполагаемой сложности (в конце концов, по количеству AC). Но тогда сильные участники не будут слушать сразу, а потом могут забыть "включиться". Или, того хуже, начнут шуметь и мешать остальным слушать.

Что бы вы сделали?

•
• +24
•

By Um_nik, history, 3 years ago, translation, ,

I would like to invite you to participate in Ural Regional School Programming Contest.

It is the Ural's qualifying round for All-Russian School Programming Contest and I think that it can be good opportunity for schoolboys to take part in this contest. It will be interesting for students too, I suppose.

Contest starts at 17 October 11:00 MSK at the same time with the onsite contest.

The problemsetters are Um_nik, Umqra, kb., hx0, Merkurev, KuchumovIlya, MikhailRubinchik (spoiler: it's not about palindromes).

Duration of the contest is 5 hours, ACM ICPC rules. Problem statements will be both in Russian and English. Link to the contest page

•
• +117
•

By Um_nik, history, 3 years ago, ,

Пользуетесь ли вы prewritten-кодом на раундах OpenCup?)
Разделю вопрос на два:
1) Если вы используете шаблон, пишите ли вы его каждый раз в начале контеста? (понятно, что это не влияет на результаты почти никак, просто интересно)
2) Пользуетесь ли вы заранее написанными стандартными алгоритмами (поток, венгерка, суфструктуры, что-нибудь ещё)?

Про нас (Ural FU Dandelion): Мы пишем шаблон каждый раз в начале контеста (может, за редкими исключениями), стандартные алгоритмы не копируем.

Ни в коей мере не хочу никого пристыдить или в чём-то обвинить, тем более что использование prewritten-кода разрешено правилами. Всем добра :)

•
• +54
•

By Um_nik, history, 3 years ago, ,

Тест:
{1}
{1}
Ответ жюри: 2
Количество перестановок с каким-то свойством больше, чем количество перестановок вообще.
UPD: Они уже заметили.

•
• +22
•

By Um_nik, history, 3 years ago, translation, ,

569A - Music

Suppose we have downloaded S seconds of the song and press the 'play' button. Let's find how many seconds will be downloaded when we will be forced to play the song once more. . Hence x = qS.

Solution: let's multiply S by q while S < T. The answer is the amount of operations.

Complexity —

569B - Inventory

Let's look at the problem from another side: how many numbers can we leave unchanged to get permutation? It is obvious: these numbers must be from 1 to n and they are must be pairwise distinct. This condition is necessary and sufficient.

This problem can be solved with greedy algorithm. If me meet the number we have never met before and this number is between 1 and n, we will leave this number unchanged. To implement this we can use array where we will mark used numbers.

After that we will look over the array again and allocate numbers that weren't used.

Complexity — O(n).

568A - Primes or Palindromes?

It is known that amount of prime numbers non greater than n is about .

We can also found the amount of palindrome numbers with fixed length k — it is about which is .

Therefore the number of primes asymptotically bigger than the number of palindromic numbers and for every constant A there is an answer. Moreover, for this answer n the next condition hold: . In our case n < 107.

For all numbers smaller than 107 we can check if they are primes (via sieve of Eratosthenes) and/or palindromes (via trivial algorithm or compute reverse number via dynamic approach). Then we can calculate prefix sums (π(n) and rub(n)) and find the answer using linear search.

For A ≤ 42 answer is smaller than 2·106.

Complexity — .

568B - Symmetric and Transitive

Let's find Johnny's mistake. It is all right in his proof except If '' part. What if there is no such b for an given a? Then obviously otherwise we'll take b = a.

We can see that our binary relation is some equivalence relation which was expanded by some "empty" elements. For "empty" element a there is no such b that .

Thus we can divide our solution into two parts:

1. Count the number of equivalence relations on sets of size 0, 1, ..., n - 1

2. For every size count the number of ways to expand it with some "empty" elements.

We can define equivalence relation using its equivalence classes.

So first part can be solved using dynamic programming: dp[elems][classes] — the numbers of ways to divide first elems elements to classes equivalence classes. When we handle next element we can send it to one of the existing equivalence classes or we can create new class.

Let's solve second part. Consider set of size m. We have found that there are eq[m] ways to build equivalence relation on this set. We have to add n - m "empty" elements to this set. The number of ways to choose their positions is Cnk. We can calculate all the binomial coefficients using Pascal's triangle.

So the answer to the problem is .

Complexity — O(n2)

568C - New Language

Suppose we have fixed letters on some positions, how can we check is there a way to select letters on other positions to build a word from the language? The answer is 2-SAT. Let's see: for every position there is two mutually exclusive options (vowel or consonant) and the rules are consequences. Therefore we can do this check in O(n + m) time.

Let's decrease the length of the prefix which will be the same as in s. Then the next letter must be strictly greater but all the next letters can be any. We can iterate over all greater letters and then check if we can made this word the word from the language (via 2-SAT). Once we have found such possibilty we have found the right prefix of the answer. After that we can increase the length of the fixed prefix in a similar way. This solution works in O(nmΣ ) time. We can divide this by Σ simply try not all the letter but only the smallest possible vowel and the smallest possible consonant.

And you should remember about the case when all the letters are vowel (or all the letters are consonant).

Complexity — O(nm)

568D - Sign Posts

Suppose, that solution exist. In case n ≤ k we can put one signpost on each road. In other case let's choose any k + 1 roads. By the Dirichlet's principle there are at least two roads among selected, which have common signpost. Let's simple iterate over all variants with different two roads. After choosing roads a and b, we will remove all roads, intersecting with a and b in common points and reduce k in our problem. This recursive process solves the problem (if solution exist).

Complexity of this solution — . If implement this solution carefully — you will get AC =)

But in case of TL we can add one improvement to our solution. Note, that if we find point, which belongs to k + 1 or more roads, then we must include this point to out answer. For sufficiently large n (for example, if n > 30k2) this point always exist and we can find it using randomize algorithm. If solution exist, probability that two arbitrary roads are intersects in such a point not less than . Because of it, if we 100 times pick two random roads, then with probability such a point will be found and we can decrease k.

All operations better to do in integers.

Complexity — .

568E - Longest Increasing Subsequence

Let's calculate array c: c[len] — minimal number that can complete increasing subsequence of length len. (This is one of the common solution for LIS problem).

Elements of this array are increasing and we can add new element v to processed part of sequence as follows:

1. find such index i that c[i] ≤ v and c[i + 1] ≥ v

2. let c[i + 1] = v

We can process this action in time.

When we handle a gap, we must try to insert all numbers from set b. If we sort elements of b in advance, then we can move with two iterators along arrays b and c and relax all needed values as explained above. This case requires O(n + m) time.

Authors implied solution with O(n) space complexity for answer restoring. We can do this in the following way:

1. Together with array c we will store array cindex[len] — index of element, which complete optimal increasing subsequence of length len. If this subsequence ends in a gap — we will store  - 1.

2. Also, we will store for every not gap — length of LIS(lenLIS[pos]), which ends in this position (this is simply calculating while processing array c) and position(prevIndex[pos]) of previous element in this subsequence (if this elements is gap, we store  - 1)

Now we will start recovery the answer with this information.

While we are working with not gaps — it's all right. We can simply restore LIS with prevIndex[pos] array. The main difficulty lies in processing gaps. If value of prevIndex[pos] in current position equal to  - 1 — we know, that before this elements must be one or more gaps. And we can determine which gaps and what values from b we must put in them as follows:

Let suppose that we stand at position r (and prevIndex[r] =  - 1). Now we want to find such position l (which is not gap), that we can fill exactly lenLIS[r] - lenLIS[l] gaps between l with increasing numbers from interval (a[l]..a[r]). Position l we can simply iterates from r - 1 to 0 and with it calculating gaps between l and r. Check the condition described above we can produce via two binary search query to array b.

Few details:

1. How do we know, that between positions l and r we can fill gaps in such a way, that out answer still the best?
Let countSkip(l, r) — count gaps on interval (l..r), countBetween(x, y) — count different numbers from set b, lying in the range (x..y).
Then, positions l and r are good only if lenLIS[r] - lenLIS[l] = min(countSkip(l, r), countBetween(a[l], a[r])). countSkip we can calculate while iterates position l, countBetween(x, y) = max(0, lower_bound(b, y) - upper_bound(b, x)).

2. What to do, is LIS ends or begins in gaps?
This case we can solve by simply adding  - ∞ and  + ∞ in begin and end of out array.

Complexity — . Memory — O(n + m).

•
• +110
•

By Um_nik, history, 3 years ago, translation, ,

Hello everyone!

Codeforces Round #315 will take place soon. The authors of this round are students of Ural FU Umqra and Um_nik. This is our second round. First one was in the black days of Codeforces and we hope that this will not happen again after our round :)

We want to thank Codeforces team for great Codeforces and Polygon platforms and Zlobober for helping us prepare this round.

Good luck!

UPD1:
Score distribution.
div2 : 500-1000-1500-2250-2750
div1 : 500-1000-1500-2250-2500
We strongly recommend you to read all the problems. We try our best to prepare different problems and some problems that hard for us can be easy for you.

UPD2:
Editorial

UPD3:
Congratulations to the winners!

div1:
1. KAN
2. Petr
3. enot.1.10
4. tonyjjw
5. HYEA

div2:
1. Amdi
2. loser21
3. Aliquando
4. hqpwca
5. Lone_Wolf_LZ

Thank you for participating.

•
• +289
•

By Um_nik, history, 3 years ago, ,

More precisely: How to generate large inputs?