Автор awoo, история, 2 недели назад,

Привет, Codeforces!

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.

Удачи в раунде! Успешных решений!

Также от наших друзей и партнёров из Harbour.Space есть сообщение для вас:

Привет, Codeforces!

Полным ходом идет подготовка ко второму буткемпу по программированию «Hello Muscat 2023», продолжении серии буткемпов «Hello», организованном Harbour.Space University в сотрудничестве с PhazeRo, Gutech, UK Oman Digital Club, Leagues of Code, Gutech CS Club и Codeforces!

Довольно впечатляюще, не так ли? Пришло время глубже погрузиться в мир соревновательного программирования с 8-дневным интенсивом Hello Muscat 2023. Он будет проходить в Маскате, Оман, и онлайн с 8 по 16 марта 2023 года, доступны оба формата участия.

Наш тренерский состав сочетает в себе талант и опыт, в нем участвуют чемпионы мира ICPC, победители и финалисты, а также легендарные имена из области соревновательного программирования: Михаил Мирзаянов MikeMirzayanov, Егор Дубовик 244mhq, Артем Плоткин Rox, Максим Обозный MaksymOboznyi и Николай Будин budalnik.

Буткемп будет разделен на три дивизиона:

• Дивизион A. станет зеркалом Петрозаводского лагеря программирования. Подходит для команд, которые уже прошли квалификацию на Финал ICPC или стремятся к этому.
• Дивизион B. Разработан, чтобы помочь командам подготовиться к следующему сезону региональных соревнований ICPC. Подходит в качестве введения для команд и студентов, которые только начинают свой путь в мир ICPC и соревнований по программированию в целом.
• Дивизион C. Предназначен для новичков в мире соревновательного программирования.

Типы участия: очное и онлайн

_Мы считаем, что участие в нашем буткемпе должно быть доступно для всех команд, где бы они ни находились, и именно поэтому мы сделали очную и онлайн-формы участия. Скидка 20% на раннее бронирование предоставляется университетам и участникам, которые зарегистрируются и оплатят до 31 января 2023 года.

• Очное:

Цена: 1500 € — 1200 €

Что включено: обучение, контесты, доступ к записям лекций, проживание в течение 9 ночей в 4-звездочном отеле Mysk, завтрак и обед, трансфер из гостиницы к месту проведения буткемпа каждый день, развлечения и приветственный подарок.

• Онлайн

Цена: 100 € — 80 €

Что включено: обучение, контесты и доступ к записям лекций.

Узнать больше о Hello Muscat 2023→

Удачи в раунде,

Harbour.Space University Team

• +222

 » 2 недели назад, # |   +72 Welcome to slow-rating-update round #142!
•  » » 2 недели назад, # ^ |   0 True. These rounds and div3 rounds take a lot of time. maybe because of hacking phase.
•  » » 2 недели назад, # ^ |   0 Welcome to slow-rating-update round #142!
•  » » 2 недели назад, # ^ |   +29 Me after solving ABCD:
•  » » 2 недели назад, # ^ | ← Rev. 2 →   -29 HI!:)
•  » » 2 недели назад, # ^ |   +2 I'm not aware of this: I don't see this contest taken into account on rating because it's not yet processed?
 » 2 недели назад, # |   0 Anybody noticed that quite hell unusual time of 26th Feb contest??!!
•  » » 2 недели назад, # ^ |   0 Yes, it's unbelievable.
•  » » 2 недели назад, # ^ | ← Rev. 2 →   0 Yeah,12 at night
 » 2 недели назад, # |   0 OMG red round!!!
 » 2 недели назад, # |   0 Hope for the best and prepare for the rest.(★ᴗ★)
 » 2 недели назад, # | ← Rev. 2 →   +8 Hope to get BLUE today!
•  » » 2 недели назад, # ^ |   +11 Uchiha Madara, you have to be LGM
•  » » 2 недели назад, # ^ |   0 me too but the rating update is a bit slow
 » 2 недели назад, # |   0 I feel like Educational Rounds are more Mathematical than usual rounds, is this the case?
 » 2 недели назад, # |   +11
•  » » 2 недели назад, # ^ |   +2 sure
 » 2 недели назад, # |   +3 Good luck! Wish every participant have higher ratings!
 » 2 недели назад, # | ← Rev. 2 →   -22 no
 » 2 недели назад, # |   -33
•  » » 2 недели назад, # ^ |   -12 hahah
 » 2 недели назад, # |   -62 Classic Mathforces.None of A,B and C had anything to do with DSA
•  » » 2 недели назад, # ^ |   +20 A was greedy, B was a math problem, C use binary search. 1 out of the first 3 problems of a div 2 round being math problems doesn't imply that a contest is "Mathforces" dumbass. Also, atleast don't be green and talk shit about a contest not having enough DSA problems.
•  » » » 2 недели назад, # ^ |   -37 Mind your language, this is not reddit/twitter. As for rating, I don't take these contest seriously nowadays. I at one point was Blue unlike someone who has never crossed 1500 xD
•  » » » » 2 недели назад, # ^ | ← Rev. 2 →   +4 "Mind your language"- What you say matters as much as how you say it, so that's pretty rich coming from a guy who spouts shit like there's no tomorrow. Also, I don't want to get into petty comparisons, but I have given like 7 contests till now, so I'm pretty sure my peak will be way above yours :)Edit: The part about "someone who has never crossed 1500" didn't age well
•  » » » » » 2 недели назад, # ^ |   -10 Bro called me a dumbass for sharing my take on the contest and then preaching me.And then Bro says he doesnt do pity comparisons but advices me to get out of green and then give my analysis on the contest.Hypocrisy at its finest!
•  » » 2 недели назад, # ^ |   +4 Considering your past rating you shouldn't have had any trouble doing A, B, or C... idk man skill issue
•  » » » 2 недели назад, # ^ |   0 It's not about whether I am able to solve or not, its about the quality of questions. I was able to solve A and B but still complaining because there was no satisfaction solving those problems
•  » » » » 2 недели назад, # ^ | ← Rev. 2 →   +5 of course you didn't have any satisfaction solving them, they aren't supposed to be hard for anyone above 1k rating
•  » » » » » 2 недели назад, # ^ |   0 idk B was kinda annoying for me, C was good tho
 » 2 недели назад, # |   0 what is "educational" about the problems in this round?
 » 2 недели назад, # |   0 Does anyone know which test case was giving a lot of wrong answers in problem C?
•  » » 2 недели назад, # ^ |   0 mine were 51 2 3 5 4and 33 2 1
 » 2 недели назад, # | ← Rev. 2 →   +10 Короче, Меченый, я тебе высрал div2 и в благородство играть не буду: посчитаешь n-е число A000311 — и мы в расчете. Заодно посмотрим, как быстро у тебя пукан после раунда загорится. А по твоей теме постараюсь узнать. Хрен его знает, на кой ляд тебе эти числа Эйлера 2 рода сдались, но я в чужие дела не лезу, хочешь отглиномесить, значит, есть за что....
 » 2 недели назад, # |   0 how to solve c?
 » 2 недели назад, # |   -28 Problem C is the literal definition of million corner cases and i love it lol
•  » » 2 недели назад, # ^ |   +4 Think about binary search approach
•  » » 2 недели назад, # ^ | ← Rev. 2 →   +32 Huh? I have 0 corner cases.(now someone will definitely hack me xd)
•  » » » 2 недели назад, # ^ |   +1 well, my first approach is to find middle positions not numbers, and when i realised that, i also realised the sample test cases has outsmarted me ._.
•  » » 2 недели назад, # ^ |   0 190436527 No corner cases whatsoever.
 » 2 недели назад, # |   +27 Nice problem D, it took a while before I noticed the name of the problem :) great hint
 » 2 недели назад, # |   0 Hints for question D Hint 1It's a Tree problem Hint 2Try to make a tree such that we can do a dfs for each premutation can get maximum length My solution[submission:190390614]
•  » » 2 недели назад, # ^ |   +3 It can be easily solved via hashes. Great example 190367922
 » 2 недели назад, # |   0 I quite liked problem C. I am pretty proud of an elegant solution I came up with inspired by some monotonic stack problems I was solving the other day.
•  » » 2 недели назад, # ^ |   0 Can you share the link to the problem which you are talking about?
•  » » 2 недели назад, # ^ |   0 can you share the approach to solve it, i completely didn't get the idea to appraoch this
 » 2 недели назад, # |   0 how to solve 1st ?My approach was to count the number of frequency and take their sum, and ans should be max to max n what is wrong in this?
•  » » 2 недели назад, # ^ | ← Rev. 2 →   0 My solution is to count number of 1-s in array and print n — (count_1 / 2).
•  » » 2 недели назад, # ^ |   +5 Only double 1-s pair in the array can decrease operation times, so all you need to do is just count the pair's amount.
•  » » 2 недели назад, # ^ |   +5 You can kill monsters of health 1 in pairs and remaining you can kill individually.
 » 2 недели назад, # |   +2 After finishing it agrees with me that the problem D is easier than the problem C, lol
 » 2 недели назад, # |   +1 I was stuck with problem C. My code outputs correctly for samples and inputs I give. Perhaps I can't find the edge cases. Here is my code https://codeforces.com/contest/1792/submission/190399259 .
•  » » 2 недели назад, # ^ |   0 Counterexample: 8 2 3 1 7 8 4 5 6 Output should be 2. Pick (2, 7), then pick (1, 8). Your code seems to output 3.
•  » » » 2 недели назад, # ^ |   0 Thanks, man. I didn't account if the numbers were not continuous.
 » 2 недели назад, # |   0 Can anyone give hint how to solve third problem?
 » 2 недели назад, # | ← Rev. 2 →   -19 leave it there is an easy way to solve D then my way
 » 2 недели назад, # |   -10 A nice perfectly balanced contest. Kudos to the authors.
 » 2 недели назад, # | ← Rev. 4 →   +55 OMGGG solved E on 01.59.54 les goo
 » 2 недели назад, # |   0 I tried to solve problem C with a monotonic stack but no luck.
 » 2 недели назад, # |   0 how to solve 2nd problem my approach was if we can have a > 0 then one joke from b and one joke from c and alternating it till either b or c runs out . so it's min of (b , c) + min jokes in total . now these jokes will balance it and bring it back to a . now if d > 0 i can take the min of d , a extra jokes . if( b or c ) are not 0 . add one more joke .
•  » » 2 недели назад, # ^ | ← Rev. 3 →   +6 If $a = 0$, output $min(1, a + b + c + d)$.Else the answer is $a + min(b, c) * 2 + min(a + 1, b + c + d - min(b, c) * 2)$
•  » » » 2 недели назад, # ^ |   0 Can u explain how min(a+1,b+c+d-min(b,c)*2) come up .Beacause I am not able to figure it out
•  » » » » 2 недели назад, # ^ | ← Rev. 2 →   0 Take all $a$ Taking $1$ $b$ then $1$ $c$ until $b = 0$ or $c = 0$. Now both of them will have $a$ points and at least one of them cannot get anymore points. You can take at most $a + 1$ from $b + c + d$.
•  » » » » 2 недели назад, # ^ |   0 both alice and bob will have a mood of "a" initially . now since we alternate between the other 2 jokes until one runs out, the mood for both will increase and decrease and end up with "a" again .now finally if a is smaller than the remaining jokes you can have a+1 extra jokes else if a is much bigger than the remaining jokes it's just that remaining .
•  » » 2 недели назад, # ^ |   0 Dude if ur approach was right then why the heck did u NOT solve it during the contest.
•  » » » 2 недели назад, # ^ |   0 screwed up with the implementation
 » 2 недели назад, # | ← Rev. 2 →   0 D was nice combination of DP and trie.. loved the question
•  » » 2 недели назад, # ^ |   0 How is DP being involved? Do you store the answers so that you do not insert a permutation again?
•  » » » 2 недели назад, # ^ |   0 no, You create dp[i][j] = Indices of all the permutations, which has '1' on i'th index and 2 on j'th index . Then, for each permutation, u can loop. this will give you ( 5 * 10^4 * 8! ) roughly... Also, u need to put break statement if you already found the ans of length 'm' . You can follow my solution here. ALAS, I was just 2 minutes late from finishing my final solution :( ... If you need understanding my solution, feel free to ping me.
•  » » » » 2 недели назад, # ^ |   0 Unfortunately your solution got TLE at 31
•  » » » » » 2 недели назад, # ^ |   0 yeah, it got TLE, I am resolving the errors. Sorry. I will update once done. Thanks :)
 » 2 недели назад, # |   0 i freaking could not implement trie, i chocked and even forgot dynamic allocation !!!
•  » » 2 недели назад, # ^ |   +20 If you are talking about D, straightforward polynomial hashing (without the mod) would do.
•  » » » 2 недели назад, # ^ |   0 you mean rolling hash right? I could not think of this in contest, wasted an hour googling dynamic allocation and still could not do because of the stress of the contest.
•  » » » 2 недели назад, # ^ |   0 Can you explain what polynomial hashing is? or post a link please. I'm having a hard time implementing D as well
•  » » » » 2 недели назад, # ^ |   0 polynomial hashing is basically encoding an array/string into a number. So for example the permutation $5, 3, 1, 4, 2$, you just encode it into the number $53142$. This way, you can easily compare array in $O(1)$, in order to binary search/use map
•  » » 2 недели назад, # ^ |   0 If you use map with vector it also works
•  » » » 2 недели назад, # ^ |   0 Can you explain how that would work, I saw many submissions with maps but I can't seem to comprehend them? Im not able to understand how the map solutions are working.
•  » » » » 2 недели назад, # ^ |   0 Map remembers a value by their key, a key can be almost anything, even vector, so when you are itterating over an array and you are looking at what prefix should the other array have to get beauty of A with the array we are looking at, you can remember that prefix as a vector and use that vector as a key in map, and remember value 1 in map at that key. after doing that for all arrays, you are now looking for an answer for an array lets say C, you itterate over its prefixes, push them in vector, and for every prefix vector you check if you have written 1 in the map at the place of this vector( so you use this prefix vector as a key) if you have then you can get the beauty of the lenght of the prefix vector
•  » » 2 недели назад, # ^ |   0 If you use bitset it also works(of course you need to do some prework!)
 » 2 недели назад, # | ← Rev. 3 →   0 I think I had an interesting approach for C, curious if anyone else had the same idea: Push all elements in the permutation into a queue. Initialize variable 'min' as 1, 'ans' as 0. For i = 1 : n: While queue.front() == min or queue.front() == selected, queue.pop(), min++ if queue.front() == min Selected.insert(i, n-i-1), ans++; Done! Return answer.
 » 2 недели назад, # |   +20 Damn. beethoven97 hacked LGM turmax's solution
 » 2 недели назад, # |   +3 For me C > E > D. I Spent more than 40 min on C and am still not able to solve it. What's the solution?
•  » » 2 недели назад, # ^ |   0 Think in terms of binary search. Can we solve the problem with $i$ operations? Now think what should the last operation be? What should the second to last operation be, and so on so forth ...
•  » » 2 недели назад, # ^ |   0 My reasoning was that if we select some elements, we will always select 1, n, 2, n-1, etc... The order we select them should not matter because some optimal ordering should exist anyways. So I created a queue and popped off elements while it was sorted. Then, whenever it was unsorted, I removed elements i and n-1-i from the array and continued to pop while it was sorted. The number of times you remove i and n-1-i is the answer.Submission: 190357765
•  » » 2 недели назад, # ^ |   0 You can see that you can not use operation on numbers that are close to each other and ordered for example 4,5,6. 4,5,7 and 6,5,4 will not go. So if array is like this 4,8,7,5,3,2,1,6 you can do operation on every other number except these 3 numbers = 4,5,6, and answer will be max(min(numbers)-1, n-max(numbers)) = max(4-1, 8-6) = 3.
•  » » 2 недели назад, # ^ |   0 Just do n/2,n/2+1;n/2-1,n/2+2;... if n%2==0 or do n/2,n/2+2;... if n%2==1 and skip the first operations if they are already in place.
•  » » 2 недели назад, # ^ |   +17 You have to find the longest MIDDLE subarray. 5 1 2 5 3 4 The longest you can find is 2 3 4.
•  » » » 2 недели назад, # ^ |   +3 yeah that's what i did too, O(n) is great
 » 2 недели назад, # |   0 Amazing system testing.So fast.
 » 2 недели назад, # |   0 Would C Problem be solved by 2 Pointers ? if not, then what?
•  » » 2 недели назад, # ^ |   +3 Yes, 2 pointers is fine my submission.
•  » » 2 недели назад, # ^ | ← Rev. 10 →   0 Yes
 » 2 недели назад, # |   0 Can someone give stress test for 2nd testcase on E? 190401625
 » 2 недели назад, # | ← Rev. 3 →   +1 A: Use first spell for 1-health monsters and second spell for others.B: First tell all type-1 jokes, then tell type-2 and type-3 jokes alternately, until one type of jokes run out. Then tell all remaining jokes until someone leaves.C: Take n=6 as example. First let ans=3=n/2, and check if the order of {3,4} is correct (which means, 3 appear earlier than 4 in the initial permutation), here 3,4 are "central" elements of 1-6. If it's not, we need ans=3 operations. Otherwise, we need to do ans--, and check the order of {2,3,4,5}. Do this repeatly until we fail at any check or we've checked the whole permutation. If n id odd, let k=(n-1)/2, start at ans=k and checking {k,k+1,k+2}.D: We need to check the longest common prefix of ai and aj^(-1) (where aj^(-1) is the inverse of aj), we could store all aj^(-1) in a trie and find for all ai.E: Didn't solved. Maybe we can let set s={d: m1*m2%d==0 && 1<=d && d<=n} and do loop for(d1:s) for(d2:s && d2>=d1) but I don't know if this approach will get TLE (for cases like n=1e9, m1=m2=735134400).
•  » » 2 недели назад, # ^ |   0 Stored all aj in a trie and searched for aj^-1, didn't realize the solution during contest. :(
•  » » 2 недели назад, # ^ |   0 D: Sort the permutations and For every prefix of every permutation, binary search permutations that match this prefix and use segment tree to update range (l <= i <= r) a[i] = max(a[i], x). 190359788
•  » » » 2 недели назад, # ^ |   0 there is much more simple solution with trie :)190383705
 » 2 недели назад, # |   +3 Any hints for E?
•  » » 2 недели назад, # ^ |   -34 two pointers
•  » » » 2 недели назад, # ^ |   0 In defense of this hint, my submission passed system testing with a two pointer-like approach: https://codeforces.com/contest/1792/submission/190397103. Although upon further reflection, the analysis I had of its time complexity was not correct, so if anyone can come up with a proof of correctness (or a hack), that would be cool!The main idea was to process the divisors in ascending order. Let the current divisor be $a$. We will maintain a pointer to the minimum divisor, $b$ such that $a / b <= n$. Then we just search from $b$ until the last divisor <= $n$. It feels like there might be an argument that the average number of elements we check is not too high, but I can't find it. The dp solution seems much more straightforward to understand, so apologies for the misdirection.
•  » » 2 недели назад, # ^ |   0 Don't know for sure that this is the intended solution.First, find all the divisors by brute force as the maximum number of divisors for (large) n cannot exceed cube root n. And for every divisor x below 1e9, remove the divisors of x until x*1e9 iteratively and update the answer.
•  » » 2 недели назад, # ^ |   +63 Generate all divisors of $m$ (there's about $10^5$ of them in the worst case). For every divisor, instead of the minimum row where it appears, let's search for the maximum column (it's easy to see that these two are equivalent). So, for every divisor, we need to find its maximum divisor which is not greater than $n$.This can be done with the following dynamic: $dp[d]$ is maximum divisor of $d$ not exceeding $n$. If $d \le n$, then $dp[d] = d$, otherwise iterate on the prime divisor $p$ in the factorization of $d$ and find the maximum of $dp[d/p]$.
•  » » » 2 недели назад, # ^ |   0 Could you mention the time complexity of this approach? It's not immediately clear this solution can fit into time limit?
•  » » » » 2 недели назад, # ^ | ← Rev. 3 →   +15 Something like $O(D \log D \log m)$, where $D$ is the number of divisors of $m$. There are $D$ states in the dynamic programming, each state has up to $\log m$ transitions (each transition corresponds to dividing by a prime from the factorization of $m$), and an extra logarithm because everything is stored in a map.upd: Plus $\sqrt{m_1} + \sqrt{m_2}$ to factorize $m$.
•  » » » » » 2 недели назад, # ^ |   +20 More accurately, $D \le 105\,000$, "$\log{m}$ transitions" is actually $\le 15$.And don't use maps for $dp$, use vectors.
•  » » » » » » 2 недели назад, # ^ |   0 How to not use maps? The factors of m could be large right?
•  » » » 2 недели назад, # ^ |   0 I generated all divisors of $m$ . For each divisor $a$ , I brutely searched minimal row number within the range $[\lceil \frac a n \rceil,min(n, \sqrt a)]$ among divisors of $m$ .This naive solution seems to run very fast.Is it reasonable to let this solution pass? I mean, this solution is unbelievably too simple, meanwhile hard to know exact time complexity.
•  » » » » 2 недели назад, # ^ |   0 My best guess is that for each divisor $a$, there's a big chance that you have to go through like $50$ divisors on average (maybe much less I don't really know) before finding an answer. You see, for highly composite numbers, aka numbers that has a lot of divisors, its divisors are also expected to have a lot of divisors, thus it is likely for the algorithm to encounter a divisor of $a$ in very few loops. For number that has less divisors, I think that there simply isn't enough divisors to make a simple $O(n^2)$ getting TLE
•  » » » 2 недели назад, # ^ | ← Rev. 2 →   0 Why dp[d] = std::max(dp[d], dp[d / p]), I don't understand this, please explain it to me.
•  » » » » 2 недели назад, # ^ |   0 I think dp[d] must equal std::max(dp[d], dp[all_of_divisors(d)])
•  » » » » » 2 недели назад, # ^ |   +8 If you do dp[d] in order then dp[d/p1/p2] would've already been considered during the transition of dp[d/p1]
•  » » » » » » 2 недели назад, # ^ |   +3 Oh, thank you so much
 » 2 недели назад, # |   0 D could have been a really nice binary search + trie task if bounds were N<=1e5, NxM <= 1e5
•  » » 2 недели назад, # ^ |   0 Hmm bs, i think only Trie + dfs
•  » » 2 недели назад, # ^ |   0 Why binary search tho? You can just DFS down the trie, and the answer would simply be where the DFS end.
 » 2 недели назад, # |   0 I feel bad when I heard that $O(n^2)$ solution can pass F2.I feel worse when I really pass it after the contest. HereI guess the author think D&C + fft is too slow, but it is not that slow, and is it reasonable to let $n^2$ solutions pass?
•  » » 2 недели назад, # ^ |   0 The problem F of last contest also be passed by some O(n^2) solutions.
•  » » 2 недели назад, # ^ | ← Rev. 2 →   +22 Unfortunately, looks like really fast templates for modular arithmetics do the trick. I haven't come up with the D&C+FFT solution, the model one has slower asymptotics than D&C+FFT. So, basically, I could try one of the following two things: let only solutions with very optimized FFT and modular arithmetics pass; let solutions with more "normal" implementations of FFT and modular arithmetics pass, but risk that someone with a very strong modular template will squeeze $O(n^2)$ in I still think that 2nd is better choice. Maybe my mistake was even trying to distinguish $O(n^2)$ and $O(n \sqrt{n \log n})$. I am sorry for that, but I hope not a lot of participants were affected by the issue.
•  » » » 2 недели назад, # ^ | ← Rev. 2 →   0 The formula is like $f_{i} = \sum{f_{j}\times f_{i-j}}$, in my memory it can be solve by D&C and fft(since $f_{i}=\sum{f_{j}\times g_{i-j}}$ for fixed $g$ can be solved) , but maybe I remember it wrong(I feel sorry), and I didn't figure it out during the contest.However, OEIS A000311 shows that $ans = exp(f(x)) = 2f(x) - x + 1$, thus we can solve it by Polynomial Newtonian iteration($O(nlogn)$ maybe?).
•  » » » 2 недели назад, # ^ |   +10 I squeezed in $O(n^2)$ by precomputing for biggest n and putting it into the source code and running the $n^2$ normally for small $n$. I didn't use any very optimized modular arithmetic. 190408679 (there seems to be no test with a number in range of [3.5e4,4e4), so the runtime is misleading but testing the worstcase on custom invocation gives 4500 ms.
•  » » 2 недели назад, # ^ |   0 In fact we can directly get a formula using lagrange inversion. the final result (plus 2) is the $x^{n-1}$ coefficient of $2(n-1)!(\frac{x}{2x+1-e^x})^n$
 » 2 недели назад, # |   +1 Did any1 use strings for D?
•  » » 2 недели назад, # ^ |   0 I concatenated values in array and stored them in hashmap, but I did it because golang doesn't support custom key types in hashmap.
•  » » 2 недели назад, # ^ |   0 Yup! I did.
 » 2 недели назад, # |   0 https://codeforces.com/contest/1792/submission/190405242Could anyone help me understand why my code gives incorrect output in this question?
 » 2 недели назад, # | ← Rev. 2 →   0 Could anyone help me understand why my code for D gives incorrect output here: https://codeforces.com/contest/1792/submission/190405242
•  » » 2 недели назад, # ^ |   +12 your answer would have been fine if rj = pqj
•  » » » 2 недели назад, # ^ |   0 Thanks for helping. What makes this hurt more is that I would have got last 5 second AC instead of WA, had I not done that silly mistake xD.
•  » » » » 2 недели назад, # ^ |   +9 It happens 😹 😹
•  » » » 2 недели назад, # ^ | ← Rev. 3 →   +1 Wait a minute, but wont p(q(j)) and q(p(j)) be like the inverse of each other, ie. they will produce each other?For example, wouldn't the product of p = 3142 and q = 2413 be 1234 whether you take r = p.q or r = q.p?
•  » » » » 2 недели назад, # ^ |   +2 No take this for example 2 4 1 3 2 1 4 3
•  » » » » » 2 недели назад, # ^ | ← Rev. 2 →   +1 In the first sample test case, the optimal p for i = 1 such that k for ai * p is maximised will be [3 1 4 2] right? But none of the given arrays have a prefix 3, So how is the answer 1 and not 0?I'm extremely sorry if I'm asking dumb questions rn, I'm a bit sleep deprived.
•  » » » » » » 2 недели назад, # ^ |   0 You are getting confused 💀, take a vector of pair store the values of "p" in that vector along with index ({value,index}), sort it and then take the prefix of indexes , what you are doing is you are still finding pqj 💀 💀
•  » » » » » » » 2 недели назад, # ^ |   +1 I must sleep. Urgently.
•  » » » » » » » » 2 недели назад, # ^ |   +3 Good night 🛌
 » 2 недели назад, # |   0 The One Piece is real!!!
 » 2 недели назад, # |   +1 Is E solved by observing numbers of divisors is relatively little(milion or so cause max 20 diferent primes in numbers) and then searching through primes?
 » 2 недели назад, # |   0 Trie method for problem D https://codeforces.com/contest/1792/submission/190408398
 » 2 недели назад, # |   0 What's wrong with my solution for problem C? 190408656
•  » » 2 недели назад, # ^ |   +8 Test Case 1 5 4 1 5 3 2 your output3 expected output2, as you can first select 2 and 4, and in the next select 1 and 5
•  » » » 2 недели назад, # ^ |   0 Thank You
 » 2 недели назад, # |   0 In C what I did for every index I find the fine permutation till that then I will find the left portions towards left and right of the this range 3 1 2 4 5 here fine permutation of index 4 will be 3 4 and then in final permutation 1 2 should come on left of it and 5 in right so greedily we pick 2 and 5 first then 1 and 5 My submission https://codeforces.com/contest/1792/submission/190407907
•  » » 2 недели назад, # ^ |   +8 Google punctuation mate, it'll change your life.
 » 2 недели назад, # |   +6 Why so many hacks of B? Is there any edge case?
•  » » 2 недели назад, # ^ |   +20 I think people are simulating it, which is too slow. Most of the hacks are TLEs.
•  » » 2 недели назад, # ^ |   0 I think it's becaues of the $1e18$ upper limit of $a1,a2,a3,a4$, which causes the TLE
•  » » » 2 недели назад, # ^ |   +5 You scared the heck out of me when I read 1e18 because I used ints in my program, but thankfully I rechecked the constraints and saw that they were 1e8.
•  » » » » 2 недели назад, # ^ |   +5 oops, I guess I misread it xd, anyway it will still TLE regardless
 » 2 недели назад, # |   0 Am I the only one who solve D with trie!
 » 2 недели назад, # | ← Rev. 2 →   +4 Am I the only one who solve problem D with trie and later see that it has an easy solution?
•  » » 2 недели назад, # ^ |   -8 I used a trie too, I found it to be somewhat intuitive. What's the easier way?
•  » » » 2 недели назад, # ^ |   0 maybe bitset?
•  » » 2 недели назад, # ^ |   +1 You are not alone bro.
•  » » 2 недели назад, # ^ |   +2 yeah I firstly thought of trie but then realised that a map would just suffice because of the low constraints.
 » 2 недели назад, # | ← Rev. 2 →   0 Can someone give a failing TC for this submission of Problem B?190391460Thanks.Upd: Found the TC.
•  » » 2 недели назад, # ^ |   0 if a==0 then answer at max can be 1 only.you can check this https://youtu.be/TOotS4TDzTI
 » 2 недели назад, # | ← Rev. 2 →   +53 F1 can be cheesed since $n$ is small and the answer is required modulo a fixed number, You can pre-compute the answers in $O(n ^ 3)$ and copy the array into your code.My solution 190420429
 » 2 недели назад, # | ← Rev. 2 →   +6 Yesterday I was practicing hashing, but I tried to don't think biased and made a solution with custom sorting and binary search in D :) My solutionI sorted all permutations, first by the order of key 1, then by the order of key 2 and so on. with a binary search I found lower and upper bound of each number in the permutation order, and updating the range of the search to it, until range equals 0
 » 2 недели назад, # |   +8 D was really standard...even using simple map for counting will pass for me C>D
 » 2 недели назад, # |   +4 I passed E in 15 minutes after the match，it didn't seem like a difficult problem，what a pity
 » 2 недели назад, # |   0 I understood that problem D can be solved by trie, and I was having some difficulty so I looked at some submissions. I see that many people have implemented trie (or something similar) using map. Can anyone explain the logic behind the implementation?
•  » » 2 недели назад, # ^ |   +1 I haven't implemented using trie but the intuition is somewhat similar to using a map. you can check the solution here — https://youtu.be/TOotS4TDzTI
 » 2 недели назад, # |   0 any hints for D
 » 2 недели назад, # |   0 190389330 Who could help me about the question C?I use two pointers but TLE
 » 2 недели назад, # |   +3 C can also be solved using DP: 190339025
•  » » 2 недели назад, # ^ |   0 what's the meaning of vector d and statues shifting funcion
•  » » » 2 недели назад, # ^ |   0 $d_i$ means the length of Longest Continious Subsequence ($...,i-2,i-1,i$) (End with number $i$)
•  » » 2 недели назад, # ^ |   0 Oh this $O(n)$ is better than std's $O(n\log n)$ :)
 » 2 недели назад, # | ← Rev. 2 →   +1 Hi guys if you are still stuck on the problems or want a editorial on it you might wanna check this out: https://youtu.be/TOotS4TDzTIhappy coding!
 » 2 недели назад, # | ← Rev. 2 →   0 B seemed quiet simple but at the end I did it out of intuition, eager to see how to properly solve it. I found problem C really interesting too!! dying to see how to solve it, thanks for the round, it was fun!!Edit: Any hints for C?
 » 2 недели назад, # |   0 Bad F due to oeis.org/A006351.We can search exsamples+2 to get this
•  » » 2 недели назад, # ^ | ← Rev. 2 →   -8 how is that related to the problem, ur solution to the problem (F1) doesn't use the formula mentioned in the link, how could someone possibly use it ?also i dont think someone possibly would search first two samples + 2 in oeis and if so, it displays 316 results found, i dont see any reason calling it "Bad" because of such a reasoning.
•  » » » 2 недели назад, # ^ |   0 i dont think someone possibly would search first two samples + 2 in oeis Several participants did search the answers for $n$ between $1$ and $4$, found the formula, and had their solutions accepted. Moreover, one could find these values with simple combinatorial considerations.
•  » » » 2 недели назад, # ^ | ← Rev. 2 →   0 look at this: a(1) = 1; a(n) = a(n-1) + Sum_{k=1..n-1} binomial(n-1,k) * a(k) * a(n-k). — Ilya Gutkovskiy, Aug 28 2020use this recursive, we can solve F1 and then the recursive is a convolution, while module is 998244353, which means it is easy to brainstorm NTT. And let me tell you why I searched answer+2. the problem said that at least one edge should be painted as red/blue, that means when n>=2, there are two illegal answer(all red or all blue) being removed, while n=1, one illegal answer(no edge) will be removed, so let's search 1,2,8,52(see samples) in oeis.
 » 2 недели назад, # |   0 Did anyone try to solve D using polynomial hashing and got AC? My solution keeps getting TLE in test case 6. I'm trying to maintain HashSet over all possible subsequences keeping their own position intact. After that, for each i I'm calculating q putting numbers one by one, and calculating the hash. 190454887
•  » » 2 недели назад, # ^ |   0 Please look at my sending, the system tests have passed completely
 » 2 недели назад, # |   0 hope to get green
•  » » 2 недели назад, # ^ |   0 Good luck!
 » 2 недели назад, # | ← Rev. 2 →   0 About E.Divisors Does this problem have too strict time limit?This is my solution https://codeforces.com/contest/1792/submission/190443658 and it has been hacked for 3 times, I think this problem may need to have more loose time limit like 4 seconods.
•  » » 2 недели назад, # ^ |   +3 There are some better solutions that don't iterate over divisors of every single divisor of m. See this. Also your code is T^2 (T is the number of divisors of m), which is even worse...
•  » » » 2 недели назад, # ^ |   0 thanks，But I think number of divisors of m will not exceeded 10^4.
•  » » » » 2 недели назад, # ^ |   0 Number of divisors can go upto 10^6.
•  » » » » » 2 недели назад, # ^ |   0 thanks so much，i even donot know this before
•  » » » » » 2 недели назад, # ^ |   0 Nah, there's at most $1e5$ divisor. Upper Bound for number of divisors
•  » » » » 2 недели назад, # ^ |   0 Number 614889782588491410 has 32768 divisors. But anyway ((10^4) ^ 2) * 10 = 1e9, which isn't good (there are 10 testcases)
•  » » » 2 недели назад, # ^ |   +8 I will study better solution soon，thanks
•  » » 2 недели назад, # ^ | ← Rev. 2 →   0 The question is, you only need to make a few changes to your code to pass all testdata.I raised my question here , but still no one answered. vector s3; for (const auto &x1 : s1) for (const auto &x2 : s2) s3.push_back(x1 * x2); sort(s3.begin(), s3.end()); s3.erase(std::unique(s3.begin(), s3.end()), s3.end()); int ans1 = 0, ans2 = 0; for (const auto &x : s3) { for (auto pos = std::lower_bound(s3.begin(), s3.end(), (x + n - 1) / n); pos != s3.end(); ++pos) if (*pos > n or *pos * *pos > x) break; elif (x % (*pos) == 0) { ans1++, ans2 ^= *pos; break; } } 
•  » » » 2 недели назад, # ^ |   0 We knew about such solution and it passes. We suspect that either the number of divisors is small (so $divs(m)^2$ is fine) or divisors are "packed" close, so it's near enough. Add here that divisors, you actually need to find their own divisors, are in the segment $(n, n^2]$. So if $n$ is big, many divisors $\le n$. If $n$ is small, many divisors $> n^2$.Anyway, we decided that it's okay if some participants gamble and get AC.P.S.: Even so, you need to write it accurately enough.
•  » » » » 2 недели назад, # ^ | ← Rev. 2 →   0 I'm not saying that a naive solution needs no skill. I'm saying that, such solution needs obviously less skill than people always expect for E.If you attribute my not_pass to my cowardice or bad strategy, that's right.
•  » » » » 2 недели назад, # ^ |   0 In addition, the naive solution is not only "near enough", but far more.I found all factors during the contest. Now I added two for-loops. Guess what, it costs 156 ms only.156 msIf you say that this solution requires some advanced mathematical knowledge, which you had already used to prove the time complexity, so this solution can be an alternative. I would blame me for my lack of knowledge.But you said otherwise. Emm... whatever, it was history.
•  » » » » 2 недели назад, # ^ |   0 thanks，i will write it more detailed soon
•  » » » 2 недели назад, # ^ |   +5 OK，i will try it soon，thanks so much
 » 2 недели назад, # |   +3 There will be only 6 hrs before next round begin. Maybe the rating update of the next round will be earlier than this round.
 » 2 недели назад, # |   0 I am sensing Problem B is a broken copied problem. I don't know source but its just my hunch
 » 2 недели назад, # | ← Rev. 2 →   0 .
•  » » 2 недели назад, # ^ |   0 wait.System Testing is running.After system testing everything will be fine.
 » 2 недели назад, # |   0 Too slow system testing.
 » 2 недели назад, # |   +9 When will the Editorial be published ?
 » 2 недели назад, # |   0 when will ratings update?
 » 2 недели назад, # |   0 Why am I always
 » 2 недели назад, # |   +4 This is to address the concerned authorities about my submission 190353992, which got skipped because the system considered it similar to another submission by BoosterImpulse , submission id 190386013.I think the major reason why these 2 codes appear similar, is because of the use of a template of MOD INT (MINT), which I have used many times in my code and is clearly written before the contest and you can clearly see my code is completely different from the other person's code, my code is a normal implementation of two pointers. You can also check the timings of the submission and other persons' submissions. Please look into this matter as soon as possible cause I will become an expert if my solutions are been judged fairly. awoo BledDest Neon MikeMirzayanov adedalic
•  » » 2 недели назад, # ^ |   0 Yes I too am pretty confused as to why the solutions are plagiarised.
 » 2 недели назад, # | ← Rev. 2 →   0 .
•  » » 2 недели назад, # ^ |   0 Have you ever read the rules?
 » 2 недели назад, # |   +8 Rating updated :D
 » 2 недели назад, # |   0 When will the editorial be published?
 » 2 недели назад, # |   +79 System said that I cheated but I did not.wsyear/190368291, LXH-cat/190370101 we used a similar template of modint and checked oeis to find a formula:a(0)=0, a(1)=a(2)=1; for n >= 2, a(n+1) = (n+2)*a(n) + 2*Sum_{k=2..n-1} binomial(n, k)*a(k)*a(n-k+1).With the same formula, our codes are similar.The code that I used modint before this contest.
•  » » 2 недели назад, # ^ |   +58
 » 2 недели назад, # |   0 When the editorial will be updated?
 » 2 недели назад, # |   0 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
 » 2 недели назад, # |   0 Hi my submission 190325251 is said to coincide with submission 190323813. I believe the logic to this problem is very straight forward and the solve() template we both used is very standard. Any of my previous submission uses a similar template + style and I believe this is just a mistake from the automated plagiarism checking system. Please update I dont want to be flagged for cheating :(
 » 2 недели назад, # |   0 IMO the problems were great. I enjoyed thinking about and solving them. Also I got caught on the special case for B (a1 == 0) haha.
 » 2 недели назад, # |   0 Through this comment, I want to address the cheating charges levied on me and Numinous , for having a coinciding solution to problem C in Educational Round 142. The submissions are 190386013 and 190353992. The reason for getting plagiarised was having a similar template, going through solve function for both speaks out the difference clearly. I hereby in my humble opinion ask MikeMirzayanov Neon BledDest adedalic vovuh awoo to provide us justice and the ratings we deserve . Thank You for your time and effort .