Привет, Codeforces!
В Apr/10/2020 17:35 (Moscow time) состоится Educational Codeforces Round 85 (Rated for Div. 2).
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Удачи в раунде! Успешных решений!
Так же от наших друзей и партнёров из Harbour.Space есть сообщение для вас:
Привет Codeforces,
Какой это был сумасшедший месяц!
Мы надеемся, что вы и ваши близкие заботитесь друг о друге и успеваете сделать все, на что у вас не было времени в обычном графике.
Мы временно закрыли наш кампус и перевели наши занятия в онлайн.Это не так плохо, как кажется, мы всегда знали, что будущее цифровое, поэтому мы уже готовились к этому моменту. В любом случае, мы вернулись.
Специальный приз для EDU ROUND 85
Эта трансформация открывает двери для некоторых довольно удивительных новых возможностей, которые позволяют нам стать ближе к нашему сообществу, где бы они ни находились.
Вот почему у нас есть специальный приз для следующего Educational Round, место на курсе по вашему выбору из наших программ по компьютерным наукам. Вы сможете учиться у нас онлайн в течение 1, 2 или 3 недель у лучших в области компьютерных технологий (все сборы за наш счет).
Приз будет вручен трем лучшим пользователям, которые подтвердили свое желание участвовать в этом конкурсе. Чтобы участвовать, оставьте нам свой хэндл в форме ниже.
Зачисление на курс, в котором вы будете участвовать, будет зависеть от доступности курса, а также от соответствия необходимым условиям для этого курса.
Мы надеемся, что это даст вам дополнительный стимул для участия в раунде, и мы с нетерпением ждем встречи с некоторыми из вас в ближайшее время!
ПОЛНЫЕ СТИПЕНДИИ ДЛЯ ПРОГРАММЫ БАКАЛАВРА
С другой стороны, мы рады объявить, что предлагаем полные стипендии для самых талантливых старшеклассников, которые хотят учиться в наших программах бакалавриата в области компьютерных наук в нашем университете.
На данный момент у нас есть два типа стипендий:
The Full Scholarship. Для лучших из лучших: все затраты на обучение покрываются университетом.
The Co-Creator Scholarship. Для тех, кто хочет помочь нам изменить образование: все расходы на обучение покрываются университетом, а в дополнение к учебе вы можете помочь команде Harbour.Space в выполнении их миссии и получить ценный практический опыт в этой области, в течение 4 часов в день работая в команде с одними из самых ярких молодых специалистов в городе.
Заполните форму ниже, и мы свяжемся с вами!
С нетерпением ждем встречи с вами и будьте в безопасности!
Всего наилучшего, Harbour.Space University
Поздравляем победителей:
| Место | Участник | Задач решено | Штраф |
|---|---|---|---|
| 1 | EvenImage | 7 | 153 |
| 2 | jiangly | 7 | 195 |
| 3 | amnesiac_dusk | 7 | 244 |
| 4 | risujiroh | 7 | 290 |
| 5 | bmerry | 7 | 310 |
Поздравляем лучших взломщиков:
| Место | Участник | Число взломов |
|---|---|---|
| 1 | greencis | 174:-53 |
| 2 | Java | 94:-8 |
| 3 | hackVerly | 55:-2 |
| 4 | mosemAlanfgar | 55:-10 |
| 5 | TheScrasse | 40 |
И, наконец, поздравляем людей, отправивших первое полное решение по задаче:
| Задача | Участник | Штраф |
|---|---|---|
| A | IQOver20 | 0:02 |
| B | arknave | 0:02 |
| C | Siberian | 0:03 |
| D | sevlll777 | 0:16 |
| E | LJC00118 | 0:19 |
| F | IceWiz | 0:31 |
| G | Cirno_9baka | 0:25 |
UPD: Разбор опубликован
Codeforces the Saviour !!
From Corona :D
lol the meme has more upvotes than the blog
why did you cut out the part where Codeforces suplexes us
Wow!!! The last line of announcement is more likely to be said by a ROCK STAR than a university staff!!! /m/ LoL :))
What if it got wrong during system testing?
Maybe kill codeforces ;D
then you'd better warn Mike ;)
When you hack your own solution
is it allowed? i tried to do so but some error message popped
Your test was incorrect
No. That hacking window didnt open when I tried. I knew case where my solution failed
Exactly how I felt haha
If you hack yourself succesfully, you would get 100 points from hacking while losing point from the task right ?
It's educational round, hacking happens after the contest ended, there are no points here.
oh, ok
Before reload Oh there are No contests after it
After reload Oh What can I do with these contests
Its raining contests.
Hope to be a good week for everyone and high rate <3
vovuh is ready with div3
I hope the problem statements will not be long
why?
Because long statements are more hard to understand, and it feels not right to have language difficulties in a programing contest.
I hope some day people will stop writing stupid comments
I hope to become Expert in this contest!! If I succeed I will be Expert in just 7 months of coding!! I hope i can do it!
All the people who have downvoted my comment, I WILL PROVE THEM WRONG!!
ok
You cant go from specialist to master in one contest lol
ok
I meant expert, I got confused between expert and master lol
Good luck mate, I am going to be an Expert during the quarantine too <3
Hope the best for everyone <3
It's probably been said a 100 times before: Hope is a dangerous thing. Hope can drive a man insane.
Ok , wish the best for everyone *_*
Hope is a good thing, probably the best.
I want the best for everyone and high rate for them , and they downvoted on my comment !!!!!!!!!!!!!!!!!!
Have you considered the thought I want everyone low rating so it boosts my rating higher? :smirk:
Hoping for no queueforces and strong pretests!
Hoping for strong pretests
There's no points for hacking in 12 hour hacking phase right? Although the person's solution you hacked would fall on the leaderboard. Am I right?
Yeah
Yes, killing the ones right in front of you is sufficient.
the penalty for each incorrect submission is 10 minutes ?? What does that mean ? also can we hack even after the contest ? I'm a newbie so please explain :-)
For the people who have the same number of problems solved the one with lesser penalty is higher up on the ranklist, penalty is the sum of the time at which each question is solved and also 10 minutes are added to the penalty for each wrong submission. Also the penalty for incorrect submissions is only added if you solve the question.
After the contest if you feel that a particular solution from a user has passed the system tests but you think that you can provide a valid test case which that solution might fail than you can try that and if that solution fails that particular user will lose the points gained on that question.
Me: Codeforces is the savior from boredom. Meanwhile Codeforces : Sometimes it feels, I am the GOD...
Sacred Games!!!
good luck all))
.
I've never seen a contest with so poor input examples
How do you know tests are poor?
Hi! I'm a newbie.I started doing competitive programming in march'20. Since then I have given almost 10 contests on codeforces but everytime I am able to solve only the first question. How can I improve? Which path to follow?
In your level you can try to solve problem 'b' after the contest. And then when your can solve b problem , you can try 'c' ......
Hardest Div2 C I have ever seen.
See 631 Div2 That was more harder than this one!
I thought it was super hard for a long time before I realized the explosions only hurt the monster in one direction
Yeah, me too, but then it still was hard to implement, IMO.
nah the implimentation was very easy look at my solution https://codeforces.me/contest/1334/submission/76178082
76131257 Boilerplate and input aside, the actual solution has 10 lines.
try reading my code: 76135183 :)
Define $$$f(n) = max(0,n)$$$. If start at $$$i$$$, answer $$$count_i$$$ would be
$$$a_i + f(a_{i+1}-b_i) + f(a_{i+2}-b_{i+1}) + ... + f(a_n - b_{n-1}) + f(a_1 - b_n) + f(a_2-b_1) + ... + f(a_{i-1} -b_{i-2})$$$
Replacing $$$a_i$$$ with $$$(a_i - f(a_i - b_{i-1}) + f(a_i-b_{i-1}))$$$, number of bullets needed would be ($$$(a_0,b_0) \equiv (a_n,b_n)$$$ )
$$$count_i = (a_i - f(a_i - b_{i-1})) + \sum_1^n f(a_i-b_{i-1}) $$$
So, to minimize the number, we compute min of first term (second term is a constant).
What if the question was like "Explosions hurt both the adjacent monsters"? How will we solve it?
Video tutorial for C
for D also
Any hints for C?
Its easy think :: suppose if we start killing from monster i , then cost of killing all monsters will be ai + (a[i+1]-b[i]) +(a[i+2]-b[i+1])+.... etc.;
so to solve it we can maintain an array d[i]= max(0,a[i]-b[i-1]) {dont forget for i==1} , we should also find sum of whole d[i] array as S;
through above info , now we can iterate over our array and check for every position as :
ans= min(ans,S-d[i]+a[i]); in O(N) time;
just above you
What's the logic for E? The fact that I couldn't even factorise D (10^15) stumped me. How to solve it without factorizing it? Or does the method draw the factors online from the queries... Very interesting problem to say the least. Thanks.
You can factorize $$$D$$$ in $$$\mathcal{O}(\sqrt{D})$$$ :)
You can loop upto 3*10^7? I thought you couldn't go beyond O(10^5-6) operations ;(
You can go up to around 3*10^8 operations lmao.
Wow, how did you even reach Candidate Master without knowing this?
The inputs are generally O(10^5) and solutions are either O(n) or O(nlogn), neither of which pushes the boundaries. I don't really have a sense of how many seconds stuff takes, just in relation to what it generally is.
nvm I misread your comment.
Do we have to make graph or is there any other trick because most of people doesn't used much space?
Optimal path is x -> gcd(x, y) -> y. Every path from x to gcd(x, y) by going down is valid, and every path going up from gcd(x, y) to y is valid. Answer can be calculated by multinomial coefficient.
The person in first place made his code obscure, that is a violation of the rules
It says so right here in the rules:
It is forbidden to obfuscate the solution code as well as create obstacles for its reading and understanding. That is, it is forbidden to use any special techniques aimed at making the code difficult to read and understand the principle of its work.
(copied from http://codeforces.me/blog/entry/4088)
Obscured by using an algorithm template? :thinking:
I meant first place in official standings, DreamLolita. Here is one of his submissions 76166237
Oh my bad. Yeah that's definitely obscured code.
OMG! this is C++ beyond my thinking, what this guy has done
got TLE on question A , in aprogram with O(n) time complexity , question A and B were easy but with strong test case
Well if you got tle it means your program wasn't O(n)
program of O(n) but i made one silly mistake , i did this :-
int n; int A[n],B[n]; cin>>n;here some very big random value was taken by compiler as value of n was taken input in third line,but i was using it the value of n in second line too and my program mulfunctionediamxlr8 A with strong test case?
Problem F. Please, explain first testcase. I can't got 20. Sum of all p is 41. Max sum of b in a is 16. Why 20 in answer?
4 1 3 3 7 8 7 9 10 7 11
3 5 0 -2 5 3 6 7 8 2 4
Incredible code by DreamLolita
https://codeforces.me/contest/1334/submission/76152622
https://codeforces.me/contest/1334/submission/76137503
https://codeforces.me/contest/1334/submission/76111293
It's not incredible, it's just obscured.
Each variable/function/class name is replaced with ReplacementFor_ (eg. the struct TREE becomes ReplacementFor_TREE). Numbers are decomposed in HEX+DEC-HEX form (eg. 0 becomes 0x113c+1395-0x16af). String/char are written with ASCII code (eg. "YES" becomes "\x59\x45\x53"). Moreover, every non-essential spacing, line-break or indentation is removed and then random line-breaks are put here and there in unusual places.
He/She has made a simple script that obscures the code before submission so that it's harder to copy/paste but otherwise exactly identical to the original one.
Code obfuscation is not allowed, for good reasons. This kind of code is more or less unhackable.
In the last contest, his codes for A, B, C were of quite different styles. I suppose he did this to reduce suspicions this time.
Yeah, I know) Because of this I decided to read his submissions
Can you please tell just basics..what he has written. I was unable to understand
I don't know, it's unreadable for me
Any hints for D? I used OEIS Sequence but got WA on test 2.
see (https://en.wikipedia.org/wiki/Eulerian_path#Hierholzer's_algorithm)
You can start creating a path like
Then, insert after the n, but before the last 1
and again, like recursive.
The length of the path in every iteration is $$$2*(n-i)$$$ From that you can construct the interval (l,r)
Analyze the cycle for n = 4 and n = 5. Once you do that it's easy to see that the cycle will consist of n blocks, i'th of them will be of size 2 * (n — x) (except for i = n, in that case the block will be just 1) and will look like this : {i,i+1,i,i+2,i,i+3,...}. From that it's easy to restore answer for given l,r.
A general hint for any problem: If you don't know how to solve it, implement backtracking, maybe you notice a pattern.
What's bkt?
maybe his bkt ~ bruteforce
Stands for backtracking (i.e. brute-force), I thought everyone abbreviated it like that :D. I modified my comment.
Wow I was also able to find this but WA on pretest2
What was test case 2 in D?
For C, I took a damage array and at each position I stored the difference(its zero if difference is negative), then I calculated the sum of all the elements in the damage array and also the element where I would start, which is the least possible
a[i]value. I know I count a value twice, I even subtracted that from the final result. What was I doing wrong?Are you sure you always select the optimal start? It's optimal to select the one which has maximum diff[i] — a[i] (or equivalently minimum a[i] — diff[i]).
$$$i$$$ with $$$min(a[i], b[i - 1])$$$ is the optimal start.
Can anyone tell me the complexity of Problem C?
It is $$$O(n)$$$ 76190446
Then why it is showing TLE on my soln
you should have used fast input output.
Can you imagine the feeling of finding the mistake 2 minutes after the contest end?
I feel really great!
Haha, I feel ya fam! Just keep going, we shall bleed red :)
This C is so hard lol while D is braindead.
is there any edge case in problem A?
Problem C:
Idleness limit exceeded on test 3. Note: this is not TLE (time limit), but idleness limit.Does anyone have any clue why these submissions failed with this weird error on G++ x64? I thought this might be because I don't flush the output (
'\n'instead ofendl), but the second one also failed:(Edited for clarity).
same problem occured with me too my solution was of O(N) still got TLE
I edited the comment to be more clear. I don't have TLE, I have ILE, whatever this means. I've never seen this error before.
Try removing those print()s and submit 76193796. It turned to TLE.
Thanks a lot! It works without the debug output (76199653), just like my other submission during the contest. But I'm still surprised it didn't get TLE outright: maybe it's because the solution was unable to read all input before the time limit?
What is hack case in problem A?
1 2 100 50 101 99
answer is yes or no?
Hacked your solution :P
I thought the day the finally come when I solved 3 questions in Div.2 Contest.
Sorry, no hard feelings bro.
No issue would have failed System Testing in end.This is Hard Life after All
Keep coding, you will manage to get it after soon days.
Thanks!
I cannot wait for the editorial.. I solved C question in O(n) time . yet it shows TLE in Case 3. tried everything to remove it. Does it have better solution?? Can't think of any :( If yes, please reply to this:)
use scanf and printf instead of cin and cout. Or use faster input/output. Same thing happened with me also.
Yeah. Tried it one minute after the contest ended... Wasted half an hour on removing TLE, still missed this. Next contest, I will try to do better :)
don't use endl, just use "\n"
http://www.cplusplus.com/reference/ostream/endl/
I think you are facing the same issue as I have mentioned here.
how to solve F and G?
Is there anyone whose same solution for div2C get TLE in python but get accepted in c++ ?
Codeforces reply to my query regarding the same issue: Unfortunately, this is the way things are on most programming contests: it is not guaranteed that each problem can be solved in every language
Sad!!!
Can anyone explain why am I getting TLE on test case 3 for problem C? My solution — https://codeforces.me/contest/1334/submission/76172390
maybe you are using endl instead of \n
I submitted an O(n) solution on Python, it got TLE on test case 3: https://codeforces.me/contest/1334/submission/76161837
I rewrote that solution to C++, it got TLE on test case 3: https://codeforces.me/contest/1334/submission/76185611
I inserted the magic string "struct {(){ios_base::Init i;ios_base::sync_with_stdio(0);cin.tie(0);}}__;", it got accepted :https://codeforces.me/contest/1334/submission/76187533
G: is it finding (s_i-t_i)^2 * (p(s_i)-t_i)^2 summation across all the substrings using fft. Or are there better ideas.
you can use bitset :D
does bitset actually pass? I didn't try it because I thought it would be $$$26n^2/64$$$
i used pragma also.
What is the usage of input l and r in problem D? I am not understanding what should be output :(
For example, the provided test case n = 3, l = 3, r = 6. The lexicographically minimum cycle is 1 -> 2 -> 1 -> 3 -> 2 -> 3 -> 1. How is this converted to an output of 1 3 2 3 ?
You should take subsegment from l to r(inclusive) from sequence of the cycle(1,2,1,3,2,3,1)
Ahhh, lol, it is used this way. Thanks!
76190416 can anyone explain why in problem C , TLE occured in my code. I think the time complexity is O(N)
try fast io .
ios::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
it worked using this line struct {(){ios_base::Init i;ios_base::sync_with_stdio(0);cin.tie(0);}}_
I think there is a mistake in the validator for problem C. In the problem it is stated that $$$1 \leq n \leq 300000$$$, but when I tried to hack, the validator states
Validator 'validator.exe' returns exit code 3 [FAIL Integer parameter [name=n] equals to 1, viola... range [2, 300000] (test case 1, stdin, line 2)]
Why are the bounds different?
+1, WTF? I submitted a solution that failed on $$$n = 1$$$ and spent 12 minutes submitting a fix (because of something unrelated to the test case itself). Now I tried to hack myself and apparently I shouldn't have even bothered, because the test is not allowed?
Unfortunately, this is true. We excluded the tests with $$$n = 1$$$ just before the contest to exclude unnecessary casework, but we forgot to update the statement :(
We are sorry for that.
He's back. 76138708 , 76144561 , 76160631
Going live on YouTube explaining A, B, C: https://youtu.be/FDbd_sYP7hM
Great tutorials man. I like your style! I will watch if you have D-F tutorials :D
A — check that all p[i] >= c[i], p[i] >= p[i-1], c[i] >= c[i-1], and p[i] — p[i-1] >= c[i] — c[i-1].
B — sort the array and check every suffix.
C — The explosion of the last monster killed is always wasted; we can utilize all other explosions. The number of bullets saved by an explosion is equal to min(b[i], a[i+1]). The answer is the sum of a[i], minus the total number of bullets saved, plus the lowest number of bullets saved by any explosion.
D — The sequence is always of the form 1 2 1 3 1 4 ... 1 n (cycle for n — 1, with each element increased by 1 and the last element excluded) 1. Use simple recursion.
E — The shortest path is always from u to gcd(u, v) to v. To find the number of paths from a to b where b is a factor of a, consider the value x = a/b. Each time we make a move, we eliminate a single prime from x. The number of paths is therefore t!/p1!p2!...pn!, where t is the total number of prime factors (counting repetitions) in x, and p1, p2, and so on is the exponents of the individual prime factors. Multiply the answer for (u, gcd(u, v)) and (v, gcd(u, v)).
F — Use dynamic programming. f[i][j] represents the minimum cost if we consider the first i elements of array a, with j elements of array b already placed. Optimize the transitions with BIT, after noticing that each time, we simply add p[i] to an interval and take care of the case where a[i] is equal to an element of b.
G — Define f(x, y) = (x — y)^2(p[x] — y)^2. Observe that if x and y matches, f(x, y) = 0; otherwise, f(x, y) is always positive. Then we just have to compute sums of the values f(x, y) to determine if two strings match. Optimize the process with FFT after reversing one of the strings.
the question d was easy and i found the logic but I didnt have enough time to write code cz i spend so much time on C, I got frustrated as it was actually the first time I got the logic for c level question in div 2.
(For E) The number of paths is therefore t!/p1!p2!...pn!
I didn't know there was a formula for that. I spent a lot of time write dynamic programming for calculating that, which in the end turned out to be wrong anyway.
My dp solution passed :) 76192690
https://en.wikipedia.org/wiki/Multinomial_theorem#Number_of_unique_permutations_of_words
Think about how this problem is fundamentally the same.
My B got hacked even though I did the same :(
https://codeforces.me/contest/1334/submission/76120878 The link for problem B
For problem E, Can you tell the proof of why no. of shortest paths from (a, b), where b is factor of a and x = a/b = p1^a1 * p2 ^ a2 * .... pn ^ an, is :- (a1+a2+.....+an)! / (a1!*a2!*...an!)?
For C, why "plus the lowest number of bullets saved by any explosion"? Is this because the last explosion is wasted and you want to waste least?
Yes. You want to waste the least.
Codeforces should give a note on C problem as it uses fast IO in CPP I had not used until my 6th submission. I am not new in CP as I knew about it but still, they must give a note so that we can check it once in our solution
The problemstatement says there are up to 300000 monsters, each data on one line, each two integers.
Fast IO is a really basic thing.
I think I solved C, but reading TLE with python3 :(
First note that if monsters weren't in the cycle (but in a line) then there is only one solution and you have to shoot the first monster on the left and then the next monster that didn't die from explosion and so on …
Now with the cycle you can notice is that if you shoot a certain monster it breaks the cycle and the solution to the line is just shoot next monster that didn't die. Now which monster to shoot first then?
Naïve approach is to N^2 for each monster, shoot it and walk in a circle. But you can also prove that you don't need to solve again for the next monster you pick. Instead, if you solved for i-th monster, (i+1)-th monster will take sol[i+1] = sol[i] + min(a[i], b[i-1]) — min(a[i-1],b[i-2]), that is you're adding current a[i] (unless it didn't die from b[i-1] before) cause you're starting with it and subtracting a[i-1] cause that one dies off explosion (unless b[i-2] didn't kill it). b[i-1] and b[i-2] serve as upper bounds.
Pretests for problem A are too weak..
Yes..I Agree!
Particularly,Those codes were Hacked Who didn't check "c(i)-c(i-1) <= p(i)-p(i-1)" this condition
In pretest , one testcase is missing and many codes are hacked for that particular testcase. (Those codes were Hacked Who didn't check "c(i)-c(i-1) <= p(i)-p(i-1)" this condition) Testcase : 1 2 4 1 5 3
I'm confused because I failed pretest 2 when I didn't check
c[i]-c[i-1] <= p[i]-p[i-1], and adding that line was the only change to get acYou got wrong answer because you didn't check
if c[i] >c[i-1] then p[i] > p[i-1]but only checked independently that two array should be non decreasing so that's where you got wrong answer not because ofc(i) - c(i-1) <= p(i) - p(i-1)RIP for problem A
Does Educational Codeforces Round has FST after hack?
Yes
I get struck in recent greedy questions, but struck less in the previous ones. Why? I can't get it? Please help me with ideas and tutorials how you approach greedy problems
Today's $$$E$$$ was a bit tricky to prove.
Firstly, let's represent any number $$$x$$$ by a sequence $$$x_i$$$ where
where $$$p_i$$$ are all the $$$n$$$ primes from $$$1$$$ to $$$n$$$.
Now, observe that the weight of the edge from $$$x$$$ to $$$y$$$ will be
where $$$x = y \cdot p_k$$$. (Why ?)
Now, if we want to go from $$$u$$$ to $$$v$$$ in the graph, in each step we can either add $$$1$$$ to some $$$u_i$$$ or subtract $$$1$$$ from some $$$u_i$$$. As we want to find the shortest path, we will reduce $$$u_i$$$ by $$$1$$$ only if $$$u_i \gt v_i$$$ and add $$$1$$$ only if $$$u_i \lt v_i$$$. Also, its optimal to reduce all $$$u_i$$$ which are greater than $$$v_i$$$ before increasing any $$$u_i$$$ which are less than $$$v_i$$$. Both these statements can be proven.
Now, consider all $$$i$$$ having $$$u_i \gt v_i$$$. In what order would you reduce these? I claim that the order in which you reduce these doesn't matter.
We can think of this problem as a game. Given two sequences of $$$n$$$ numbers $$$a_i$$$ and $$$b_i$$$ with $$$a_i \gt b_i$$$ for all $$$i$$$. Initially we have a score of $$$0$$$. In one move, we can can choose some $$$i$$$ having $$$a_i \gt b_i$$$, reduce $$$a_i$$$ by $$$1$$$ and add $$$\prod_{j \neq i}{a_j}$$$ to our score. We continue this until both the sequences are equal. Prove that no matter the order of our moves, the final score is $$$\prod{a_i} - \prod{b_i}$$$
We can prove this by induction, let's assume that for any sequence $$$c_i$$$ having sum of all numbers $$$= k$$$, score is always $$$\prod{c_i} - \prod{b_i}$$$. So, if we have a sequence $$$a_i$$$ having sum $$$= k+1$$$, choosing any number $$$a_j$$$ will reduce the sum by $$$1$$$. Hence, the total score will be:
The base case is trivial, where $$$k = \sum{b_i}$$$ and score is $$$0 = \prod{a_i} - \prod{b_i}$$$
Thus, the number of shortest paths is the number of ways to reduce all $$$u_i \gt v_i$$$ to $$$v_i$$$ multiplied by number of ways to increase all $$$u_i \lt v_i$$$ to $$$v_i$$$.
For your proof block, there is a much simpler proof: if you go from u to w where w divides u and always step by removing a factor, the cost is just the number of factors of D that divide u but not w, regardless of the path.
Wow. Short and beautiful
That's what she said.
Yuki726 you just made my day. :D
Wow! Now, my proof looks stupid :(
I was about to start trying something like your proof, but I decided that I'm too old to enjoy grinding through that sort of maths :-)
I agree, If I am going from u to w and w divides u, then cost will be number of divisors of u — number of divisors of w.
now the cost of going from u to v trhough gcd will be: c1 = cost(u --> gcd) + cost(gcd --> v) = number of divisors of u + number of divisors of v — 2 * number of divisors of gcd
however, there is another possible path: u --> lcm --> v and its cost is: c2 = 2 * number of divisors of lcm — number of divisors of u — number of divisors of v
why is c1 always better than c2? I was not able to prove this, and I submitted a solution based on that c1 is always smaller and it got accepted.
Another proof: In any sequence of primes that got removed, we can swap adjacent primes in the sequence and the total weight of the sequence(path) doesn't change. Hence every sequence has same weight(since we can transform one sequence to other using adjacent swaps).
That's what I'm always saying when I can't figure out any nice way to prove it :)
I wrote solution for C with O(N) time and O(1) memory in Python3 but got TLE on test 3. I tried to optimize input reading and other possible bad performance cases but still have TLE.
I suppose, that it can be some I\O mistake (like input() on empty stdin) but can't even imagine, where such mistake can be in so simple python code.
76161270
Is there someone with similar problem? (Or maybe someone can find mistake in my solution?)
PS. I even try to rewrite this code in C++ (76168690), but result is the same = TLE on test 3. I definitely miss something important, but I can’t understand what exactly
Try to add these three strings in the beginning of main function:
It is so frustrating when you get TLE bcz you use python. Today in Problem (C) it happened with me. I think it can be avoided, like most of the times in first 4 problems, what went wrong this time, constraint seemed fine for pypy but shows TLE.
You can try using Fast IO in python.
https://codeforces.me/blog/entry/47667
I got TLE in C++ because I didn't use
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);at first.I was already doing Fast I/O, maybe because my complexity was O(nLogn). But I guess nlogn is doable in c++ but not in python
I would not call what you are using for fast IO! That is not even close to being fast. Just switching to a faster IO makes your program TLE on tc 7 instead of tc 3 76211878. Also switching the sorted(m)[0] with min(m) results in AC 76212190. If you want a drop in actual fast IO that works in general then check out https://github.com/cheran-senthil/PyRival/blob/master/templates/template_py3.py
Thanks for your help @pajenegod. I definitely learnt something new. Thanks again.
I have found two plagiarism cases in the last contest(Educational Codeforces Round 85 (Rated for Div. 2)).
Here's the submission links: https://codeforces.me/contest/1334/submission/76179771 https://codeforces.me/contest/1334/submission/76175619
They did the same crime at previous round too (Codeforces Round #632 (Div. 2)). https://codeforces.me/contest/1333/submission/75904417 https://codeforces.me/contest/1333/submission/75907575
Ahnaf.Shahriar.Asif just copied the code from Shafin_Ahmed and added some extra lines to avoid plagiarism checkers.So we can call it plagiarismforces. Kids should get some education from it :p .
"Educational" is not in the process of solving problems, is in the hacking phase. Especially,in Problem A.
[submission:https://codeforces.me/contest/1334/submission/76137503]
I cannot understand any of DreamLolita submission. Someone please explain it?
MikeMirzayanov Please review this account DreamLolita and its submissions.
Is he a robot?
I think it's a violation of Codeforces Contest Rules and the participant should be punished:
In C if i declare input arrays as global array it does n't give TLE.else it gives tle. TLE: 76195191 76196229
Because if you declare array locally space will be allocated for each testcase that will consume additional o(n) time.
But mine got accepted even if i use local array .76145135
for every test case, your array size is N, not n
I didn't get what you want to say ?
in the solve function, which is called every test case, it's allocate array with size N, which is 300007
so the total is T*N = 150000 * 300007
if it's only allocate the necessary size, which is n, it's guaranteed the total n in all test cases does not exceed 300000
make it a global with size N is also ok, because only allocate it once, not every test case
is this solution correct ?
Solution to problem G:
Similar to this problem, we define the distance between two strings A and B of length $$$n$$$ as follows:
Then we can see that when $$$A$$$ is $$$s$$$ and $$$B$$$ is a substring of $$$t$$$, $$$B$$$ is an occurrence of $$$A$$$ if and only if $$$\operatorname{dist}(A,B)=0$$$. However, in this problem, we want to know $$$\operatorname{dist}(s, t[j:j+|s|])$$$ for all $$$j$$$-s. To do this, we can expand the formula a little:
Note that the first and last terms only have to do with on $$$j+i$$$ or $$$i$$$, so they can be easily calculated in $$$O(1)$$$ with prefix sums. The three terms in the middle are related to both $$$i$$$ and $$$j+i$$$, but if we reverse string $$$s$$$, it will only depend on $$$-i$$$ and $$$j+i$$$. To solve for all $$$j$$$-s, it turns out to be a typical FFT problem. So the whole task can be solved with 3 polynomial multiplications, which is fast enough to pass the time limit.
Don't forget to set $$$eps$$$ a little larger to avoid precision problems. My submission: 76170703
Complexity: $$$O(n\log n)$$$
I had a slightly simpler (but most likely slower) FFT solution. My actual submission was dangerously close to the time limit, but I've since come up with a slight modification that's faster.
For each letter c from 'a' to 'z' in turn, and for each position where S could be placed, count the number of positions where T contains c and S contains either c or p[c]. Sum these counts over all letters, and you can now tell whether each position is a match. For a given letter c, create a 0/1 array U where U[i]=1 where T[i]=c, and similar a 0/1 array V where V[i]=1 where S[|S|-1-i]=c or p[c]. Then to get the count you just convolve U with V via FFT. It's almost certainly slower than the solutions other people have described because it requires 26 convolutions, but should be fast enough.
Here is a very simple bitset solution for G, that can pass with pragmas:76287369
Can someone please tell me why am I getting TLE on this code for E
You could've pre-calculated inv modulo before queries.
Problem A systests are garbage!!!!
Yeah right! There was 1006 test case overall and none contained the case where the increase in plays is less than the increase in clears. I wonder how did they put the test cases
i got hacked... still i m happy cz i got AC in C
actually pretests did contain this case. I failed pretest 2 when i didn't verify that increase in clears <= increase in plays
Well I got accepted in contest without checking for it there’s no magic going on.
weird, I also failed on pretest 2 because of that
Pretest had something like this
which you passed because of checking
if (p[i] != p[i - 1] && c[i] != c[i - 1]) { b = false; break; }But it fails for this case
Yeah thank you I know that. But this does not justify the available system tests There’s only 4-5 cases to check and they couldn’t do so in 1006 tests. The number of hacked solutions for A speaks for itself.
C is educational, taught us the importance of fast IO
Can someone please check my code for problem C and tell why it is giving TLE, I think what I wrote is clearly O(n) 76183582
UPD : Used fastio and got it accepted after contest :(
I'm really mad with myself :(
I got problem E wrong (WA on Test 22), because I didn't add these two lines to my code. I would have got 101st place as well. :( if (temp > 1) primes.add(temp);
Basically, for D's such as 6 or 15, my prime list is {2} and {3} respectively, instead of {2,3} and {3,5} respectively.
Lmao, I've also had issues with this! I wrote factorization several times, and I knew I had to add "if (temp > 1)" line, but I accidentally wrote "if (temp > 0)" instead, and it took me 20 minutes and 4 attempts to fix it xD
cf predictor is not working for me anyone has the same issue?
I uninstalled it.
Держи в курсе
I like you rating graph.
From the last contest my cf predictor working again..today don't know , what will be happened. Bofore last 3 or 4 contest it was give me wrong prediction too.
Actually it takes some time to refresh . If you do a submission and immediately check cf predictor it still predict till your last submission . Check after 2-3 minutes of submission , it will predict correctly.
Almost 1/6th of the submissions of A have been hacked and its not even been 2 hours yet.
nice.
What is the hack case for C ?
For a unsuccessful hack attempt how much score reduce ? please help anyone..
No reduce, no gain.
Then if i hack other solution , no effect on my score or gain rating + point ?
No, also no gain. But the other one falls down in ranking, because one less solved. So you should hack the ones right in front of you in ranking.
In this contest no fall and no gain . generally its +100 points for successful hack and -50 points for unsuccessful hack.
For Problem C — "Circle of Monsters", is there any solution got accepted in java?. in practice, i tried the same as the top scorer "MiFaFaOvO" in java, but it says "Time limit Exceeded".
https://codeforces.me/contest/1334/submission/76208845 I think it has worst time O(nlogn) where as people have done it in O(n) but that was just lazyness and can be reduced to O(n)
are you using fast IO?
My JAVA Submission for C 76160407
You should always use fast IO in JAVA.
Timecomplexity: O(n)
Some tests for A 4 3 2 1 3 2 4 4 2 5 3 5 6 2 2 2 3 2 3 1 1 2 2 145 1
How do i see div 2 ranking on standings page? It shows div1 participants as well, even if I untick 'show unofficial'
For c problem, if any person has set Max to less than 3*10^17. U can hack c. Many persons asking me,so I shared. I hacked 5 in problem C.
give me a test case only if u interested.
https://codeforces.me/contest/1334/submission/76160649
This is my link to the code for C this is in o(n) still tle in 3rd case any reason for this like if any further optimization required ?
Many codes written in c++ also got TLE due to large input/output. You can use Fast IO to avoid TLE!
screencast of me trying to prove B and E for an hour
nice
Is there any efficient way of doing the hacking? Some people hack like a killer machine (+20, +30). Can you just tell us if there is any faster way of doing that rather than seeing hundreds of codes?
Why when I want to hack a problem a message is shown "Illegal contest ID"?
Спасибо вам за очень хорошие тесты. Я люблю Вас. Если бы вы делали нормальные тесты, у меня бы было не -40, а +40 к рейтингу, а я шёл на рекорд. ЕЩЁ РАЗ ПОВТОРЮ! ПРЕМНОГО ВАМ БЛАГОДАРЕН. Делайте , пожалуйста, не ленитесь, нормальные тесты к задачам
Всегда так удобно обвинять в своих багах авторов, которые не отдебажили за вас ваши решения.
Да, наш прокол — объективно, тесты на задачу не покрыли один (из тех, что лично я заметил) случай, но, пожалуйста, не ленитесь, тестируйте свои решения перед отправкой, чтобы не было мучительно больно за потерянный рейтинг.
Why my solution in C gets tle in test 3 https://codeforces.me/contest/1334/submission/76201302
you should have used fast input output metods.
scanf/printf??
Yes scanf printf will work
Yeah I got AC. But, why?? Like cin cout isn't working but scanf and printf working. Anyway, I am facing problem on finding solution on greedy problems. How do you guys approach? Any tutorial for beginning?
You can start by solving B problems or questions whose rating is between 1200 to 1500 in codeforces and has a tag greedy. From that, you can easily learn about how greedy works.
For B. Middle Class , can anyone tell me what's wrong with my code 76205050 ?
It is a rounding issue because you use float for some reason. Use long long instead.
PS: Edited
whether I output "i" or "cn" it doesn't matter actually they both are same.
could you please give some example where taking float will fail.
float is 32 bit, it "overflows" the exact precision. Maybe double works better here. I am not sure how much bits double uses for the number, but float seems to have not enough.
However, long long does not overflow in this problem since 64 bit.
Its working if we use long long int but not for float(because of rounding issue).
If I hack my own solution, will I be out of the competition?
No
Here are my solutions to this contest in case anybody wants to refer them
Anyone who is able to explain me this code : https://codeforces.me/contest/1334/submission/76166237,
Gets a FREE COOKIE !!
wtf is that man
10+ new testcases are added for problem C. Will they re-judge every solution over them once again?
Yes, after the hacking phase is over.
I have some doubt in C, Just after reading the question I immediately wrote an equation, to kill Ith monster :
I couldn't come up with any base case due to cycle. Can we make further progress in this direction?
you can see my solution i did the exact same thing
can anyone know ... if i hack a solution will that test case be added to system tests for all solutions of that problem????
yup
there is some very unusal things going on here can anyone plz check the codes of https://codeforces.me/profile/DreamLolita this guy.he is from another universe
can anyone plz check the codes of this guy https://codeforces.me/profile/DreamLolita.
is that c++??
For Problem C
If the explosion kills the next monster, it explodes too"
How to solve if it didn't explode too??
You need to shoot all monsters which are not killed otherwise. Every shoot decreases the points by one. Count the shots, you need to output them at the end.
Well, I just realized that I did an HUGE overkill in problem C using a sparse table and binary jumps to calculate the answer fixing each of the positions as the starting one. I definitely should start thinking of easier ways to get accepted submissions :P
Has editorial published?
Editorial won't be published until the hacking phase is over
rank 1 div2 :3 How to hack it?
I think this guy is a bot!! xD
do have a look at his submissions for A,B,C.
I don't know. I had not seen it before :(
Bots can't solve problems (yet).
He has obfuscated his code using a script so that his code would be pretty much unhackable. But that's against the codeforces rules. He did same thing in the last contest(#632) so he was debarred from the final standings.I hope he would be debarred this time too.
What are the hacks for problem B??
solved
problem is with this statement " avg=(i+1)*x; " i and x are of type int so result will overflow. declare i and x as long long or cast RHS to long long as avg=(long long)(i+1)*x;
There's no testcase for B where the test has, 1000 tests and each n value is 10^5. Wasn't it obvious to include that?
Remember, the sum of n cannot exceed 10^5
That means, if you make n=10^5,then t=1 must hold.
oh thanks. Sorry authors!
It's guaranteed that the total sum of n doesn't exceed 105.
As open hacking phase is finished, but still solutions of some users is in queue. Can someone explain what does it mean ?
Also When will the ratings be updated?
All the solutions will be judged again including hacks. Then the final standings are released and after an hour or so you'll get your rating
Fastest System Testing I ever seen...
why is system testing so slow PS: I didn't participate in this contest but I want to stalk my friends's ratings.
The longest system test I have ever seen.
It seems that sth went wrong with the website. All judgements have been paused.
Just be patient, such things take time.
Why is System Testing taking too much time? Are the test cases are more than usual or is there any problem with Codeforces server?
I think it is because that Problem A pretests are too weak. Many different main tests apend to system tests.
I think, this is problem with Codeforces server. For last few hours Codeforces wasn`t avilable three times. Too much online during carantine
Even before servers getting down it took 3 hours to judge submissions done till 57th minutes of the contest.
It's because of A. There were a lot of hacks and it's highly likely that most of the hack cases are different. So like KisekiPurin2019 said, all these test cases get appended to the main test cases. So in all probability, there could be 200-300 main tests for A
when will we get to see the final standings?
Lets guess how much more time it will take to have the full testing. XD
My guess, not today
Will we get final standing today??
Telegram Channel reports: "Due to a power outage, Codeforces and Polygon are unavailable now." Maybe some problems arose as a result of this? Codeforce I believe in you!
Maybe the system testing is affected by the COVID19 and it is in the home quarantine now.
Are their servers broken??...System testing is stuck at 88%...Why is it taking so long??!!
System testing got TLE at 88%
Actually, an hour ago or something, codeforces was down. So that is RTE not TLE xD
seems like the joke has gone above your head XD
Will the system testing continue? Or will the round be unrated?
I don't think so. The round becomes unrated only if something happens during the contest. The contest is completed without any mishappenings.
Please, keep on system testing!
Can someone give strong small tests cases for F? I'm trying to upsolve but can't submit due to system testing.
When system testing gets TLE
The contest was rated but my ratings, didn't update; when will the tutorial be posted?
Seems like codeforces is in some kind of server related trouble. System testing isn't finished yet. Once it finished, you will get your rating.
Unfortunately, the testing of the round is not over yet.
Keep calm guys, hopefully before the next round starts the Edu(85) final result will be published.
Keep calm guys, hopefully before the next round starts the Edu(85) final result will be published.
who know why the rating does not change?it says that rated for div.2!
System testing is somehow stopped due to some server issues. Once the round has been tested completely all the trusted participants will get their new ratings.
haha. This is funny.
Haha
CF, please don’t die, we love you. Just complete system testing.
I am becoming a master this round,wish it can continue.
I was about to become expert.....then i got HACKED!!
Finally become master gyh20,thank you codeforces!
Why codeforces is arranging day long system test in recent time?
I want to practice but it is still testing...!! OMG...
System Testing Sucks ):
All the contestant are in Home Quarantine. Only CF is the true friend at this moment.
12 hours hacking phase + 12 hours system testing
bmerry Can you explain your non-segtree solution to F?
Sure. Let's call an element of a "special" if it gets output by the function. Let's say that $$$a_i = b_j$$$ is special. For any k such that $$$k \lt i$$$ and $$$b_j ≤ a_k \lt b_{j+1}$$$ we need to remove it; this is what
cullcounts. Note that each element which must be removed will be counted exactly once by this. Additionally, any non-special element with negative cost should be removed;negsumis a prefix sum of negative costs to help find these.Now we process $$$a$$$ backwards, maintaining some DP state.
dp[idx]is the minimum cost for the suffix processed so far if the next special element must equalb[idx], ignoring elements of the suffix until the next occurrence ofb[idx](but including the costs fromcull). If $$$a_i$$$ appears in $$$b$$$, say as $$$b_j$$$, then there are two possibilities to update $$$dp_j$$$: either $$$a_i$$$ is special, in which case we continue from the next occurrence of $$$b_{j+1}$$$ in $$$a$$$; or $$$a_i$$$ is not special, in which case we continue from the next occurrence of $$$b_j$$$ in $$$a$$$. Either way we need to adjust for the negative costs in between.Running time is $$$O(m + n\log m)$$$ (log factor from
lower_bound), but I think it could actually be reduced to $$$O(m + n)$$$ since elements of $$$a$$$ are at most $$$n$$$ and hence one could built a looking table to do thelower_boundqueries in O(1).Bhai 100-200 jyaada lele par system testing krwa de....
How much more time will be taken for system testing of this round ! It's stuck at 88% and also editorial is not out yet !
Maybe for over 150 testcase of problem A then CF get TLE at 88% LOL
I love almost everything of Codeforces but their system testing is not up to the mark.It takes too much time to check all the submissions.They should improve their system testing time.
This time server went down, causing some issues.
3 hours ago I saw system test was going 88% and I slept
now the percentage is still remain
what the heck is going on
Codeforces server went down few times and got stuck on 88%
It's judging again now!
Maybe is Um_nik who wants to prove that he is worth as much as 1000 cyans. As shown in the movie : https://www.youtube.com/watch?v=TXju58mzzaU
I have no idea if they can't or they don't want to prepare strong tests for during the contest . A lot of solutions got hacked or got WA (lot more than usual) in A,B,C (mostly A and B) which is just sad . I strongly hope the test data for the next contest will be strong :) but anyway I'd like to thank codeforces for making this situation (quarantine) less boring and more exciting
System testing 100%
Few contest before it rolled back after reaching to 100%. How many of you remember that moment ???
Is the code after ddl counts? It seems the code which submitted after ddl counts in system test?
It counts in system test not towards your contest standing or rating.
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
System tests are finished
Did the whole world going to quarantine, motivated the coders to rise and participate more in coding to prove superiority in the field of quarantine lifestyle?
VERY OFFENSIVE
Codeforces servers right now:
the queue after every Educational round is frustrating, you guys need to figure this out I don't know maybe not allowing people to submit between the end of the round and the system-tests and maybe reduce the hacking phase to 6 hours instead of 12, it is really slow to rejudge all the submissions made during the last 12 hours on hundreds of tests...
Getting aged waiting for rating change O_o
awoo where is the top hackers for this round ?
Unofficial top hackers (without unsuccessful hacks)
greencis 174
Java 94
hackVerly 55
_BadLoser 55
TheScrasse 40
yijan 36
allexceed404 32
dapingguo8 31
vovanstrr 26
harshchhatbar 26
Amir_Reza 25
surung9898 23
rocks03 22
LinkinPony 22
nikolapesic2802 20
Moustafa. 20
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
From implementation(A),greedy(B),creative thinking(C),to graph theory(D),math(E),data structures(F) and string algorighms(G),this really is a perfect contest.Thanks!
From implementation(A),greedy(B) and creative thinking(C),to graph theory(D),math(E),data structures(F) and string algorighms(G),this really is a perfect contest.Thanks!