Добрый всем день! Этот раунд будет немного особенным, потому что он составлен из задач школьного этапа всероссийской олимпиады школьников по информатике в городе Саратов. Задачи для вас придумывали и готовили Александр fcspartakm Фролов, Иван BledDest Андросов и я, Владимир vovuh Петров. Удачи всем!
UPD: Спасибо Дарье nooinenoojno Степановой и Данилу sad101010 Смирнову за тестирование!
UPD2: Мы откроем решения для просмотра и начнем фазу взломов чуть позже, потому что школьный этап олимпиады еще не закончился. Мы откроем все примерно через два часа. Пожалуйста, не обсуждайте решения задач в течение следующих двух часов.
UPD3: Теперь вы можете обсуждать задачи.
UPD4: Разбор опубликован!
<almost-copy-pasted-part>
Привет! В Sep/21/2019 10:05 (Moscow time) начнётся Codeforces Round 587 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач (или 8), которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты — так же как и вы буду расстроен, если у многих попадают решения после окончания контеста.
Вам будет предложено 6 или 7 (или 8) задач и 2 часа на их решение.
Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Михаилу awoo Пикляеву, Максиму Neon Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда.
Удачи!
Также хочу сказать, что участники, намеренно отправляющие неверные решения и взламывающие их после окончания соревнования (пример), не будут показаны в таблице лидеров по взломам.
</almost-copy-pasted-part>
Is it rated for all problem XD
Enough with that already. Instead of being sarcastic, why not prepare a round yourself? :)
Because cf only allows to prepare contests for experts and higher
Numb DESTROYS kocko with FACTS and LOGIC.
For you I am sorry_marymarine
Please read upstairs first
funny
Rip. My problem D in ECR 73 got hacked only because I didn't use fast printer. Sad the test cases didn't catch that.
Excited for my first contest :)
Too early
But this is suitable for Chinese people XDDDD
Я, конечно, дико извиняюсь, но как ваша Div3B задача в плане претестов? Ммм?
I hope the problems are sorted by difficulty:)
How and when can I hack others solutions? Morning I was searching for that option in educational codeforces. Didn't get it. So someone give detailed description of how to see and hack others code please.
You can hack others after the contest and it lasts 12 hours
Yeah, I should go for hacks and then what?
if you can hack someone you will be given 100 points
In Div. 3 and Educational Rounds you don't get any points for hacking.
I missread it as "Thanks to Smirnoff for tasting!".
So if you rating is more than 1600 then you will be unofficial.
Otherwise, you must be a trusted participant to be in the official table. However, even if you are not a trusted participant and have ratting less than 1600 then the round will be rated for you.
I did not get it. Can a participant not be in the official table but his/her rating changes?
Or there is an official table separated from CF?
Basically when you switch from unofficial to official standings, in addition to removing non-div3 participants, it will remove all non-trusted participants. However non-trusted participants will still be used for rating calculations. So to simply answer your question — Yes, it will be rated for them but they will only be visible under unofficial standings
I hope I will start with Expert on CodeForces.
Another Candidate master , making an alt account , waiting for people to reply "Wow you did it" after the contest.
hoping to gain rating!
round is rated right?
Finally Div-3... Want more contest of Div-3.. In fact one in every week....
Бахните потом div2 по муниципальному
wonderful
Where is Zoro ? :D :D hahaha
Another contest as i have lessons (not computer) in the school... That's terrible...
Damn I just woke up
USA all nighter gang
A similar problem. Similar to problem E.But I am still unable to solve E2
https://math.stackexchange.com/questions/188812/n-th-digit-in-the-sequence-of-natural-numbers
Maybe it is a famous problem
Why is sum of area of intersection = area of original rectangle not working in C :((
you will also need to subtract area of the intersection of the intersections as that will be counted twice.
Auto comment: topic has been updated by vovuh (previous revision, new revision, compare).
In D, I have taken the difference of every element with the maximum element of the array. Then took the gcd of all the values which is the minimum number of swords each person will take. Then the answer will be the number of persons and swords each person will take.
Why I got the WA in test case 5?
I did the same. But remember to filter out the '0' values while finding the gcd.
That doesn't matter, since $$$\gcd(0, k) = k$$$.
I got the same firstly.
Expecting test smth like:
41 1 5 9try it.
I got output 20 1 Is it correct..?
No. You can do it with 5 people, 4 swords each.
I got it...Thanks
using x, y, z — notations from D;
x = max element of the array;
z = gcd(z, x — a[i]), i = 1..n;
y += (x — a[i]) / z, i = 1..n;
This is not true number of swords is right in your case bt the number if people is sum of the difference of each element with maximum divided by the number of sword
Dat feel when you start from C...
Totally agree, I skipped C without thinking once I saw these rectangles in the problem and start solving (D) xD
No hacking phase ?
How to solve F?
Odd, is there no system tests? Usually the standings say "System testing" but now it just says "Final standings".
Hacking phase will start soon, you have to wait till it's over.
Какие из задач были на школьном этапе? Не верится в то, что на нем была E.
Все эти задачи были на школьном этапе. Мы не включили в Div. 3 только самую простую задачу из набора.
Эх, нам бы такой школьный этап в Смоленске! Будем, как обычно, решать пять баянистых задач, после чего их вручную проверят тестами с бумажки (что делает ограничения абсолютно бесполезными в половине случаев, но никого это не волнует).
Поверьте, в Саратове все тоже не так и гладко, как кажется на первый взгляд :)
А как вам задача: Дана строка длины n (1 <= n <= 10), нужно найти любую её подстроку, являющийся палиндромом.
Не смейтесь, это 3-я (!) задача, из 5, школьного этапа!)
Кстати, 5-я реально интересная, но первые 4 решаются за 3-5 минут каждая от силы.
8 задач на 2 часа?
Школьный этап длится также 5 часов :)
Лол, я хоть и не решал, но было интересно на задачи смотреть. А у нас в Питере в школьном этапе вообще нет ни намёка ни на ДП, ни на какие-то техники — первые 4 задачи зелёного уровня на Codeforces и 5-я задача голубого. А потом такой скачок сложности на регионе)
How to solve E?
You can try to solve 1177B - Digits Sequence (Hard Edition), as they are quite similar.
Hint: Try to calculate number of digits for 123456789101112.... by breaking them down into 1-9,10-99,100-999,1000-9999,...
My thoughts were on the same track but couldn't come up. I'll try this one.
For E1.
k is small. We can process the number of digits of i as d[i], and process the perfix sum of d[i] as sum[i]. Then for each k, we can use binary search to find i which contains k-th digits.
For E2.
Link my solution, another comment, here.
Hope it can help you.
problem E1 wrong test 1??? :(
Is F was lazy propagation
It can be done using RMQ and dp
I solved it with DP + binary search (Just a lower bound).
Not able to understand D at all. To much words and entities.
Come on, guys, stop discussing problems, please. The elimination stage in Saratov is still not over.
It was good contest. Thank you for all. btw, How long do we have to wait to be able to submit code?
Read the blog update please
Thanks.
Wouldn't it be more logical to start Div. 3 two hours before the end of the elimination stage, so that everyone would finish at the same time?
Yes, this is more logical. I didn't knew when the elimination stage starts and ends and thought that all is ok.
Since the comments under the announcement are probably the only place where problem discussion may take place, I think it may be reasonable to hide it until the end of the elimination stage (if it is possible).
Late for 1 minute. T_T
Wait to submit my E2's code and hope that I will succeed.
So lucky that it passed.
How to solve C? I tried so hard and got WA on test 11 :( It's really disappointing. After so much hard work couldn't get the AC.
I also got WA on test 11 for my first submissions. For me it was because I had calculated the area of overlap between the two black papers, but didn't check that this overlap was within the white paper.
Deleted
You need to find areas of intersections. Between first and second, first and third, and between all of them. Then if S(1, 2)+S(1, 3)-S(1, 2, 3) < S(1) -> Yes, else -> No
You can find area of intersections using intersections of projections. Notice that rectangles intersect when both x, y projections intersect.
Here is my submission 61021591
By the way, which tool did you use to draw the second picture, it looks cool!
SAI
When hacks will be available?
why this output is wrong in problem B test 3
69 1 4 2 5 6 3
vovuh
Okay, if you need an explanation, here it is:
Your permutation is $$$[1, 4, 2, 5, 6, 3]$$$. So durabilities of cans in order you will knock them down are $$$[5, 4, 4, 4, 5, 5]$$$.
So the answer by the formula is $$$(5 * 0 + 1) + (4 * 1 + 1) + (4 * 2 + 1) + (4 * 3 + 1) + (5 * 4 + 1)$$$ $$$+ (5 * 5 + 1) = 1 + 5 + 9 + 13 + 21 + 26 = 75$$$. $$$75 > 69$$$ so firstly you're printed wrong answer and secondly it's greater than author's answer.
You need to print the order of indices. So firstly you need to print the index of can which you'll knock down first, then one you will knock down second, and so on.
How to solve E2 ?
I did it using binary search. for each i we are writing numbers from 1 to i. So first I did a binary search on i such that when I write from 1 to i+1, the number of digits exceed k. Now we have to find the number j between 1 and i+1 such that writing till jth number makes the number of digits greater than k. again binary search on this. Once we get j we can easily get our answer. you can refer to my code here
Write down each block in a column and consider all the blocks that the last number has the same number of digits as the Big-block.
The number of Big-blocks is about 9, so we can find k in which Big-block easily.
Then the right block can be found by using binary search. I preprocessed
the longest length of block in each Big-blockandthe sum of digits of all Big-blocks.Now this problem 1216E2 - Numerical Sequence (hard version) was translated to 1177B - Digits Sequence (Hard Edition).
Here is my solution 61007196 and wish it can help you more.
when can i solve it again
Подскажите, пожалуйста, почему для B данный ответ не является верным?:
Правильная ли логика? :
Логика правильная, но в ответе не совпадают элементы с их позициями.
For C, can someone explain how the answer is "NO" for TC 11:
50 100 100000 99000
13 4654 999999 1000000
0 0 1000000 45654
Dunno why you ask. White rectangle is almost inside first black rectangle except a little part near point (0;0) and the 2nd rectangle covers this part.
Possibly you should notice that it's 999999 that is not 99999
How to solve problem F?
I think it can be done using dp and segment tree with lazy propagation but am a little bit confused.
what should the dp state be and how to use segment tree efficiently with dp?
Think of the problem like this — there are $$$n$$$ offers for intervals $$$[l_i, r_i]$$$ and the $$$i$$$-th offer has cost $$$c_i$$$ (this problem is only a special case). We want to cover all indices $$$1$$$ to $$$n$$$ and choose the cheapest such set of intervals.
Now here's the dp state: let $$$dp[i]$$$ denote the minimum cost to cover indices $$$1$$$ to $$$i$$$ with intervals that have their right point $$$\le i$$$. The answer is $$$dp[n]$$$. The base is $$$dp[0] = 0$$$. How do you transition?
To find $$$dp[i]$$$, you must cover indices $$$1, \cdots, i - 1, i$$$. Since in $$$dp[i]$$$ we're looking only at intervals that end $$$\le i$$$, obviously, we must choose at least one interval that ends at index $$$i$$$ to cover it. Also, we choose exactly one such interval, because if we chose more than one, we can pick the longest and that won't affect the answer. Which interval should we choose? Let's iterate on all possible choices for that — let's pick an interval that ends at $$$i$$$ (call it $$$[l, i]$$$) and say it has cost $$$c$$$. Once we have picked this interval, we just have to ensure that indices $$$1, \cdots, l - 1$$$ are covered because this interval covers the indices after $$$l - 1$$$. What is the minimum cost of this subproblem? It's not $$$dp[l - 1]$$$, because there could be a cheaper configuration with intervals that end after $$$l - 1$$$ but before $$$i$$$. To cover those possibilities, we take the minimum of $$$dp[l - 1], dp[l], \cdots, dp[i - 1]$$$ (call it $$$m$$$). So the optimal cost of doing this is $$$m + c$$$. And $$$dp[i]$$$ is the minimum of this expression over all intervals that end at $$$i$$$.
We can store at each index a list of intervals that end at that index, and to support finding $$$m$$$ quickly, we can maintain a segment tree that stores $$$dp$$$ values of each index and allows us to find minimum in a range of indices.
Thank you for the explanation.
In addition, since all intervals have identical lengths (except those near the bounds, but this is not really a problem), you can maintain a sliding window minimum to solve the problem in $$$O(n)$$$.
Edit: a 21-liner getting AC — 61020296
Can any one tell why my solution got failed on test1 61010239
your answer is 2 3 1 , but it's wrong , the correct answers are 1 3 2 or 3 1 2 .
deleted :)
Did you get not "Do you get"
Thanks ! I corrected it :)
You really want contribution :D
:|
I wrote a segment tree to solve problem F, and I also know that it can be solved with something like the sliding-window. But I found many solved it without using any data structures example. I'm just wondering how that works.
Can someone please help me with that?
How to approach E1?
Process the number of digits of i and get the prefix sum, then use a binary search to find i which takes up the k-th posithon. Finaly the answer is the k-sum[i-1]-th digit of i.
Here is the commit which is my solution for E2. If you are interested in E2, Link it.
Is E2 Digit DP?
I solved it with binary search and some mathematical calculations.
If you are interested in my solution, hope the commit-544591 can bring you some of the inspiration
RIP my problem E :<
What's the hack for C?
one of them =)) 0 0 3 3 5 5 6 6 0 0 4 4
your solution is WA with follow case 2 6 8 8 1 2 3 3 1 3 10 10 sorry, I will hack your solution :(
Hi. Could you please tell me where the mistake is in my code?
Submitted a solution for problem D with complexity n*log(10^14) + sqrt( 10^14 ) This gave a TLE in java in test case 16 during contest Same code I rewrote in c++ after contest. It passed all pretests.
Time limits too strict for Java
you can solved it with complexity n*logn time
O(n) is easy to! you just get the maximum number and find the GCD of all (maximum — a[i]) and output sum(maximum — a[i]) / GCD and GCD
Actually gcd works at O(log(n)) time
yeah my fault :( thanks for recommending
It was interesting that my exact the same solution for A was TLE in PyPy3 but accepted in Python 3. Any idea?
Try to avoid using
+=with strings in Python, when you add chars multiple times. There are some optimizations thrown in here and there, but it sometimes happens that this method's performance degrades to $$$O(n^2)$$$, since each time you append a couple of chars this way, a brand new copy of the whole string may be created.Instead, you can put all strings into an array, and then write something like
s = ''.join(a), which is definitely faster.Update: now your code passes in 140 ms — 61033581
Good to know! Thank you so much!
Same solution, just change in indentation and variable names, was expecting same handle too! :(
sol1: 60988370 sol2: 60998975
MikeMirzayanov sir, please look into the matter.
Hi MikeMirzayanov, I had used unintentionally public online compiler(ideone.com) in middle of contest for solving Question D. Here is link to my solution on ideone which I had used in middle of round unintentionally. But there is message from system saying that my submission is exactly same with some other guy. Here is his solution which is exactly same as mine. I think he has taken the solution from there only because I don't know that guy. It is my mistake to use online public compiler which I will take in account for further codeforces round.
i think my solution 60995513 for the problem 1216F and solution 60994761 of tuan52 just a coincidence, Because each problem can have different ways, the same idea is inevitable. tuan52 and I use queues so we can have the same idea, can't say we copy each other's code
The same idea causes similar solutions but not exactly the same code with only the changes in indentation and variable names. Don't you think your solutions are somehow too similar?
Sorry if I'm wrong.
i don't know why, but I'm sure he and I don't know each other
This is regarding the notification I received having similar code to some other codeforces user. For problem B, the code to keep track of indices is available here https://www.geeksforgeeks.org/keep-track-of-previous-indexes-after-sorting-a-vector-in-c-stl/ and the rest logic is highly vulnerable to probability of being same.
Also I did use ideone on public setting unintentionally http://ideone.com/KvSYMv but thought this is highly unlikely to be copied since almost 100+ submissions are done every minute there.
Anyhow,the system may realize, I have clear early submission & please remove the warning on my profile.
I received a talk from System saying that my solution 60971083 for the problem 1216A significantly coincides with solutions Arianfk/60969857. It's just a coincidence. I am surprised that the two solutions are almost the same. I wrote the code myself without reference to any third party code. 1216A is a simple problem that can be solved with only a few lines of code, and I think it is true that the similar solutions may occur.
This is regarding the following system message I received.
Attention!
Your solution 60996009 for the problem 1216C significantly coincides with solutions meet29/60996009, gagan_6730/60997664. Such a coincidence is a clear rules violation...
Upon investigating (if it can be called that), I found that it's the exact same solution. The only thing is that my submission was made earlier. I could think of no reason how my code could have been leaked as I never use any online IDE, just editors, and compilers on my machine. But, later, I recalled that I had received a new sign-in mail while the contest was running. I had thought at the time that it was probably a delayed mail for my own sign-in (OS and browser were the same) so I didn't think twice about it. Now, that is the only thing that makes sense to me. I don't know for sure if that is what happened i.e. my account was compromised, but that is the only logical explanation to me. The IP did turn out to be different.
The timeline of events was as follows — I submitted, then I received the mail about a new sign-in, and then the copied solution was submitted.
I don't know if this would constitute as an unintentional leak, but if it would, I take responsibility for any penalties. Regardless, I have taken the necessary steps to secure my account so that such an instance does not repeat (if this is what had happened). Will surely be more careful from now on. Lesson learned, the hard way.
Clarification of my flagged plagiarism submission:
Your solution 60992562 for the problem 1216C significantly coincides with solutions anonymous-420/60989907, CandyZack/60992562.
I have used a part of the code from stackoverflow, the link is below. https://stackoverflow.com/questions/27152904/calculate-overlapped-area-between-two-rectangles
Because both the submission uses the same code form external site, I urge you to remove the plagiarism on my submission.