Привет, Codeforces!
В 03.12.2023 17:35 (Московское время) состоится Educational Codeforces Round 159 (Rated for Div. 2).
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Иван BledDest Андросов, Максим Neon Мещеряков и Роман Roms Глазов. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Удачи в раунде! Успешных решений!
UPD: Разбор опубликован
1st comment :>
Hope this round to be fun :P
.
Hope to get back to expert after this round! GL everyone :)
Me, too. Hope I re-get blue after this round.
hello
Solve more 2problems
.
me too man
Me, too.
Hope that it'll be an amazing contest!
What's the rating distribution for problems
No score distribution for icpc style rounds
Good luck everyone and have fun ^_^
Educational Rounds are Mathforces af. Gonna skip this one
aight bro u can stop yapping now
your last attempted contest was 9 months ago...
I will try to give Div3 today
much appreciated
....
I need to have Dinner during contest time. So, had to skip this one too.
hahaha
You are so funny bro! :))
Inshaallah, In this round I will be Green.
Hoping to become a pupil after this round
i bet u can't. u know u have to be in top 150 to get 300point
Решения будут доступны потом, чтобы посмотреть, как решать надо было?
После раунда можно смотреть решения любого участника
hope to get back to pupil after this round
Я тоже
What is ACMP?
After 127 contests and I'm still a NEWBIE gonna set a world record :(
Bro how ?
Those Who Do Not Learn from MISTAKES Are Doomed To Repeat It.
YOU NOT GIVING UP GIVES ALL OF US HOPE!!
hope this round proof good for you
Not really, was able to solve the first 2 questions easily but wasn't able to implement the 3rd question properly but still i am gonna keep coding :) Hope you too get +ve deltasssss
got a great +ve delatasssssssssssss loads of them
Bro your heat map is insane!!how the heck are you so consistent even in college?
ohh
Yo! I was referring to the heatmap of AbhayAnilark it is just purely crazy for someone to be so consistent.
oh! thanx a lot man for the appreciating word
D >> C
But E < D imo, so always be sure to read at least one more problem than the one you're stuck on.
Speedforces
Can anyone show me the formula to solve the problem B please? For me problem C is easier :D
you can do binary search instead of coming up a formula directly :D
I can't see the idea to do binary search. Can you help me?
well you got to do is find the greedy function check(x) which checks if x is valid solution and then do classic binary search whicch find the smallest x such that check(x) is true.i am not so sure because i came up with a formula during the contest
you can binary search the minimum amount of days that Monocarp cannot rest, let's say $$$mid$$$ days, then Monocarp can earn $$$mid*l+\min(2*mid,c)*t$$$ points, where $$$c=\lfloor (n+6)/7 \rfloor$$$ is the number of tasks unlocked within $$$n$$$ days.
I think it should be c = [(mid+6)/7] (correct me if I'm wrong)
It has to be with $$$n$$$, because maximum number of tasks that you can do is always the same and equals to $$$⌊(n+6)/7⌋$$$.
there are 3 thing you can do in a day
we have ((day -1) / 7 + 1) tasks unlocked.
so we will do 3. for tasks/2 days
then do 2. if tasks is odd
then 1. for remaining point
that's exactly what i did start with the day type 3 and then to 2 and then to 1
this is my submission, i used math not binary search.
https://codeforces.me/contest/1902/submission/235665532
Problem D is difficult to implement.
Problem F is first known as "[SCOI2016] 幸运数字", a problem from 7 years ago
For F, why using xor basis gives me WA on test 54?
https://codeforces.me/contest/1902/submission/235578100
Your code gives WA on
because in your dfs function, you say if you are the root node, don't initialize xor basis.
Thanks a lot.
I might have just clutched problem D
D >> E,F
Can't we use Hashing in E?
In your code, i guess TLE is because of the log(n) for map. You may try other fast hash.
I think, better I learn tries , isn't it :(
D > F? Really? Idts.
4 submissions on B :)
Also E < D.
If anyone solved E using string hashing, drop the solution here
here Submission
Can't that be hacked?
https://codeforces.me/contest/1902/submission/235606529
Hack welcomed :)
TBH the TL is too tight
I submitted it again, got TLE.
My Hashing Submission Hacks are Welcome :)
You can brute force it asymptotically Submission
:( +1 penalty in C because the constraint 'x is a positive integer' got updated after I opened the link. Also, no idea why directly solving the inequality in B gives WA but a binary search approach passes.
When solving the inequality, did you consider the case where the number of unlocked tasks is odd?
Doesn't floor() take care of parity issues?
Opposite actually, because you need one more day to complete the leftover task. I did calculations, not bisearch.
Cluthed D with 2 mins left !!
me getting +3 on B but 0 on C didn't include a '()' if you see my submission :(
Why E with such tight constraints on ML with trie, was it not intended? Saw many hashing solutions passing instead, made me sad ;(
My trie solution passed and it was implemented using pointers.
wdym? I got AC with trie.
https://codeforces.me/contest/1902/submission/235578938
Same implemented with pointers as well, but couldn't optimise memory in my case, also your code seems to run close to 256 mb as well.
I mean you can calculate memory consumption. Trie in worst case have 1e6+1 vertex. (1e6 is length sum)
size of 1 vertex = 8*27 bytes
8*27*(1e6) + 1e6 (vector of strings) ~= 212000 kb
Why do you add vertexes in update?
https://codeforces.me/contest/1902/submission/235610927 — got AC
oh nice didn't think of breaking it off while checking, thanks a lot!!
My normal submission costs only ~140MB. 235583633
I got MLE(:/) with Trie too using PyPy3. After I converted the code to C++ after the contest, it passed magically :). But now that you say even in C++ trie won't always pass based on the implementation, I have a few things to learn.
You can brute force it asymptotically Submission
Failed D just because I forgot to check whether
set.lower_bound(l)was equal toset.end(). Submitted the moment submissions opened and got AC. Good thing it was "out of competition".Looking into my time spent to solve each problem, the most difficult one from A to E was problem B.
First time solved F during contest and finished debugging E 1 sec after contest was over.
I fucking missed $$$D$$$ just by a few seconds , bro!!!
Whats the idea behind E?
I built a trie of all strings where each node further keeps track of the number of strings in the subtrie, as well as the total length of the strings in the subtrie while excluding the common prefix that the node represents.
Then for each string, I read the characters in reverse-order and traverse the trie, with each step denoting a collapse step, while carefully accumulating the contributions to the desired sum of the other branches (concatenation cases) by utilizing the stored values.
My submission: 235592382 I used a 2D array for the trie, which was probably a terrible idea (almost broke the memory limit), but the logic should be sound. I can elaborate on the details further if you want.
I think problem D should give more time, I am sure I use a right O(nlogn) algorithm and implement it in python， however it's always show "tle". 2000ms is too short for D!
it is simple to solve D in < 500ms if you use cpp
pypy isn't always faster than python. you can sometimes switch from pypy to regular python and won't tle
Damn, you passed tests even without fast IO. I had to use cpp
Please why is my submission for F WA on test 9
My thought is divide and conquer with XOR-basis with $$$q\log^2A$$$ complexity
code for F
thanks very much!!
Take a look at Ticket 17179 from CF Stress for a counter example.
nvm figured it out
Am I the only fool who spent 1 hour and a half to figure out the solution for C while solved E in merely 15 minutes...
I'm the fool who couldn't solve E in 1 hour 40 minutes yet solved C in the first 11 minutes.
In problem D, does the reversed commands range represent the same path, but mirrored around some line parallel to y = x?
Nope. Well, it might always be mirrored around some line, but that line definitely isn't necessarily parallel to y = x. For example, if you keep going up, then reversing does nothing, and your mirror line is a vertical line, and similarly, going right only yields a horizontal mirror line.
I think it should be mirrored around some dot, but I don't think that's somehow necessary for solution
Hmmm... Is it the line from the start of path to its end? If so, we can always just find it and mirror given point to check if it is within given range.
Nope, that's not it either. For example, if you move in a square wave, e.g., URDRURDRURDR..., the mirror line is a vertical line in the middle, which doesn't contain the start or the end.
If there is some geometry-based solution to solve this problem, it would likely be much harder than simply precomputing the forward and reverse paths separately (which is likely the intended approach), so I wouldn't recommend thinking too hard about these geometric properties.
Nope
I might be wrong with that thinking, but my base idea is that after flipping, the prefix and suffix of points remains unchanged. If so, we can somehow transform given point and check if it is within prefix, suffix, and given range.
You're on the right track. Let $$$p_i$$$ be the point we're on before executing the $$$i^{th}$$$ command. Now to reverse a segment $$$[l, r]$$$ of the path, shift the origin to $$$p_{r+1}$$$ and mirror all the points on this segment around $$$x=-y$$$, (the transform is $$$(x,y)\to(-x,-y)$$$). Then, shift the origin to $$$p_l$$$. If we treat the points as vectors, then the point before the $$$i^{th}$$$ command after mirroring (assuming $$$i$$$ is in the segment) is $$$p'_i = -(p_i - p_{r+1}) + p_l = p_l+p_{r+1}-p_i$$$
Why does this work? If the last command in the segment was
R, then the second last point would be to the left of the ending point, so mirroring about the ending point will make the second point of the new segment to the right, which is what we want. Similarly this can be shown for any position and command on the segment. Finally we need to start at the original segment's starting point, so we shift our new points to have $$$p_l$$$ as the origin.But isn't it O(r-l) for every query?
I thought we need to transform the point in query so that it would be possible to check it on straight path stored in set.
I made it $$$O(\log n)$$$ per query by using a map that counted the number of times I visited each point. For a query
x y l r: - If I visitx ybefore the $$$l^{th}$$$ command or after the $$$r^{th}$$$ command, then I visit that point after reversing the subarray - Between the $$$l^{th}$$$ and the $$$r^{th}$$$ command, I check if I visit the point $$$(x_l + x_{r+1} - x, y_l + y_{r+1} - y)$$$.To do this I sorted all the queries by
l, and then updated counts ofx youtside each segment and the transformed point inside the segment by using something similar to a sweep line method.Yes, you are right. Simple set of points without visit time is not enough.
But two simple sets are enough :) One to track from beginning and one to track from the end. I'll check this idea.
upd: seems like even two sets without proper command times are not enough
Damn, it's so sad I couldn't solve C in time, it was really easy
Will Hashing Not Work in E, I was getting WA on test-5 :(
How to solve D without Mo's ?
Pre-calculate times when you visit each position when moving forwards and backwards, plus some prefix sums to calculate the x and y offsets, then you're done!
Basically this, I have been heavily commenting my solution during the contest 235604170
After reversing, suppose :
x = s1 + s2 + s3...sl-1 + sr + sr-1 + sr-2.. s(r-z+1)
=> x = prefix_horizontal[l-1] + prefix_horizontal[r]-prefix_horizontal[r-z]
=> prefix_horizontal[r-z] = prefix_horizontal[l-1] + prefix_horizontal[r] — x
Similarly, prefix_vertical[r-z] = prefix_vertical[l-1] + prefix_vertical[r] — y
hence there's an index l-1<=z<=r such that,
prefix_horizontal[r-z] = prefix_horizontal[l-1] + prefix_horizontal[r] — x
prefix_vertical[r-z] = prefix_vertical[l-1] + prefix_vertical[r] — y
How do you check in D whether you reach the point during the reversed section? I just guessed.
If you are choosing it inside the reversed part a[l,...,r]. Then it is choosing a[1..l-1] and a prefix from reversed(a[l...r]) which is suffix from a[l...r]
My screencast of solving A-F
I'm planning to discuss my solutions (~2 hrs from contest end time)
Can anyone tell what is causing runtime error in my solution? 235592760
gcd should not be equal to 0 initlize it with A[1] — A[0]
It can be initialized to 0. 0 is identity for gcd. gcd(0,x) = x.
thanks for correcting me
If n = 1, then You are returning without reading the array.So, there will be misinput.
Thank you<3
abs() dont accept long long in c++ are there any workaround other than to manually calculate it? I got WA in Problem C because of this.
https://www.geeksforgeeks.org/abs-labs-llabs-functions-cc/
guys i want your help in identifying problem in my code, https://codeforces.me/contest/1902/submission/235602795 this is my solution for C, i first calculate the gcd of consecutive elements and then select a(n+1) by binary search,
i am getting runtime error on test case 2 with exit code 3 particularly on
16
9 -10 -7 4 -8 10 -5 -1 -9 8 3 -2 2 5 0 -6
the thing is when i run my code on my computer i get the correct answer, i have tried almost everything but can't figure out the problem
read this comment
that abs() one? i don't think thats an issue, i tried with llabs it still gives runtime error, i think there's some fault in the judge
the comment above it
Oh yeah that one, thanks man :)
When $$$n == 1$$$, your function returns without actually reading the array value, so the program would mistakenly treat this array value as the array length for the next test case.
thanks a lot man, completely missed that part :)
Can anyone tell why this code gives TLE?
https://codeforces.me/contest/1902/submission/235611299
For B. Getting Points, although a mathematical formula exists, you can use Binary Search for ease of implementation.
The total tasks created will always be $$$(n + 6)/7$$$.
Suppose you take $$$r$$$ rest days. Notice that it's always optimal to take the first $$$r$$$ days off (so that you never run out of tasks). Since there are $$$(n - r)$$$ working days, and each day you can do at most 2 tasks, the points gained is $$$min(n + 6/7, 2*(n - r))$$$. The points gained via lessons is of course $$$(n - r)*l$$$.
Submission
Can anyone share a typical case where C can fail?
This educational round was really educative, enjoyed it a lot :)
Problem D was cool. Enjoyed solving it. Overall a great educational round.
Don't understand why to use binary search in B.
you don't have to use BS. But fixing the days makes the math easier to not mess up. It introduces new errors that may be caused by binary search, though. In my opinion, its about preference.
Hope to become Master tomorrow, first time solved all problems in a contest.
I solved today F in O(n log^3 n) and O(n log^2 n), but the solutions are running in almost the same execution time.
Upd: My O(n log^2 n) solution dropped from 3200 ms to 700 ms after I used vector::reserve in N vectors of size at most 20
Congratss, orz
https://codeforces.me/contest/1902/submission/235605516 could someone tell me, why am i getting TLE here? It should work in O(nlogn) which should easily pass for 1e6, right?
Bad problemset. Couldn't solve one
really cannot believe you are blaming contest for your bad level you have never solved a single problem in any of your contests and you are still nagging
I misread problem C and ended up giving up :< I hope I wont be kicked off Expert
Solved E for the first time in a Div.2 contest. Used Trie Here is the code
I don't get it. Why would anyone downvote that comment.
Can anybody give me some problems that are similar to B, please? I feel uneasy when I encounter such a problem.
just solve randomly rather than looking for problems similar to some particular problem
What knowledge do D & E require?
D is based on prefix sum and E is based on Hashing/Tries
D is just binary search and prefix sum
Interesting can you explain how we can use binary search?
I am too lazy to explain but here is my code
Could someone give an example on how my code failed ?! I can't imagine the test case .
[submission:Hacked C Solution ]
Don't use unordered_set , because it is achieve by hash ,someone will construct data to make tons of hash cross , then you will get TLE
Would it pass if gave the unordered_set big initial size ? Or it's necessary to use map<int, bool>?
You need to use a custom hash for unordered_set (I'm not sure how hackable it is though). You can use normal set it's only logn
You need map but not unordered_map,unordered_xxx is useless
read ths blog. For example, I have a custom_hash in my library in case I want to use unordered_map/unordered_set. https://codeforces.me/blog/entry/62393
Thank you, who hacked my code sent the mentioned blog after hacking phase :)
I feel that isn't it impolite to write hash cross code to someone else
My Nlog^2N solution for D
Submission link: https://codeforces.me/contest/1902/submission/235635773
Segment tree library used: https://youtu.be/K-86mKNAsmU?si=bI_IBJVNU50Mjysf
Can anyone give me some tips for the hell C? I'm totally confused by it
GCD is the key to success
Probably you are right.But I wonder who all the elements turn to in the end?
the current biggest or the newest element which is bigger than the current biggest
i'm wrong
Can anyone please explain how to do C? How to apply GCD there ?
recall that all the numbers are unique.. also, as x is +ve you cannot decrease any number by adding x to it.
now, we need to reach a common number that can be achieved by adding x multiple(or zero) times to all the numbers. Also, assume that a is sorted initially, so we are willing to achieve:
a[0]+C1.x, a[1]+C2*x, .... , a[n-1]+Cn*x which makes a[0]+C1.x = a[1]+C2*x = ..... = a[n-1]+Cn*x
so what you can see here is that we need to maximize x, also, greedily we can see that best choice for that final number as of now would be a[n-1], so we see that for any i, a[n-1]-a[i] will be some Ci*x, so take gcd of all such terms and find x.
then the probem remains to find optimal the An (try it yourself, if you cant I can help there).
Hi akshat,
Initially how i thought was, the best option to make array equal is making the array elements equal to the max element present in array.
So what i did is found the max in array, for ex : a[] = [1 -19 17 -3 -15], max = 17; as the difference among (max — a[i]) should be multiple of x, so i thought x will be in range x -->[1,16], For which ever x is possible i have collected minimum answer(traversed whole array to check x is possible or not, which ever x is possible collected max-a[i]/x)may be here i can use GCD to find x right ?.
I think u are also saying to make array equal to max right ?
Yes the idea is same as mine. You can look at my code for any clarifications :)
You're adding same x to all elements, if difference between them is not multiple of x they'll never become equal.
Why does my nlogn solution timeout for D? submission — 235579778
Update — So many other nlogn solution also getting TimeLimitExceeded , any explanation?
maybe this line
Thanks FiniteMoves, it was such a stupid mistake, no need to even do that. Accepted solution -235677472
What's wrong with my solution 235568240 for C ? Please help me where it is leading to TLE
unordered_map leads to O(n^2)
Why O(n^2)?
https://codeforces.me/blog/entry/62393
deyumnnn I knew this thing I thought I used map even till now, aaahhhh :((((
My rating change of +50 yesterday is now -35 because of this :(((
But thanks for sharing this blog ibrm, learnt a lot !!!
By the way, for your check perfect square function you can instead just use __builtin_popcount which returns the number of bits and check if that is equal to one.
huh ?? That's wrong ...
1000 = 8 is not a perfect square 1001 = 9 is a perfect square
We can just check if a number is a power of 2 from no of set bits = 1
oh I'm dumb. I thought it checked powers of 2 not perfect squares because I was just working on another problem and that was in my head.
GOT FST ON D . Why they not include such big/Edge test in Pretest.
Why so late Editorial?
it's not unusual for an edu round
Ohh didn't knew that
Thanks mate
When do editorials usually come for edu round
wait till night
F can be done in O(n*lognlogA + q*logAlogA) with centroid decomposition. while decomposing the tree, just solve all the queries whose path includes the current centroid. We can do this by rooting the current subtree in the current centroid and calculate the xor base for every path from a centroid to a node in the current subtree(O(nlognlogA) in total) and then we can answer a query in O(logAlogA) by just merging 2 xor bases.
hey, can you explain your decomposition part a bit?
Lets say that you are currently solving your problem for a set of nodes S and a set of queries Q. When solving for S and Q, if you find a centroid C in the tree that is consisted of nodes in S, then every query from Q will either contain C, or not contain C. Those who contain C we will solve by precalculating xor bases for every path C->X, where X is in S, and then to answer a query (X,Y,K) we can merge the 2 paths that we precalculated C->X and C->Y and get the answer to our query. Now we decompose the tree into new trees, every query in Q that didnt contain C will now belong completely to some of the new trees. So that means that now we have new subproblems (S1,Q1),(S2,Q2).... which we can solve recursively.
Cool, Thanks! btw do you have any similar problems?
Sorry, i dont have.
my $$$O((n + q) \cdot log_2n \cdot (log_2a_i)^2)$$$ solution on problem F using binary lifting and xor-basis passed during the contest but got TLE on test case 90 on system tests. and an optimized one passed with time complexity $$$O((n \cdot log_2n + q) \cdot (log_2a_i)^2)$$$ after the contest. Is there any solution with better time complexity, like for example $$$O((n + q) \cdot log_2n \cdot log_2a_i)$$$?
UPD: stefanbalaz2 just posted one 2 minutes ago. ty and what a coincidence.
I have other solution too, using LCA binary lift. submission
Idea: For each node from root you can mantain the height where a new number is added to the xor-basis and the number added, when you are building the base in a child, you need to try do add only numbers added in the parent, thus at most 20 numbers will be added and at most 20 operations will be needed to know if a number will be added or not. for queries, I need to get the height of lca and add all numbers from basis of the nodes u and v up to the height.
oh, I got it, thank you, and your solution is easier to code for me.
Hi, can anyone tell me how to hack "String hashing" solutions, just give a link to an article.
unrated？
When will rating be updated?
235603985 This submission was done in contest and gave AC a the time. I woke up this morning with a TLE. 235708991 This submission is exactly the same and still gives AC.
Can someone explain? It passed all hacks and the code is the same. Just one gives TLE and the other doesn't.
@awoo@BledDest Thank you very much for the contest. Could we please get the editorials and ratings change — many thanks!
Most contests are rated within minutes of system checks completion. This one had hacking session finished over 15 hours back and still not rated.
why this contest do not affect to rating's ?
Oh my stupid me... In problem C, I assumed we must choose A[n+1] > 0, then got confused why it wouldn't work :(
Same I wasted 1 hour and 5 submissions on this.
after how much time does the rating changes come for educational rounds?
I'm sorry but when rating changes ????
Can you guys tell me if my ratings could go up? 1902C - Insert and Equalize
Click here to see my blogs
In problem E, I used string hash and chose modulus 131, got AC during the contest but got WA on test 24 after contest. I tried 135, WA again on test 98. Finally I chose modulus 29123 and got AC. Could anyone tell me how to avoid such situation ?
Always use double hashing
I used double hashing. Double hashing can be wrong if choosing unlucky modulus.
131, 137 is common module for hashing so tester use some test case where your code will get WA . So use those prime module that is not common. Obviously not use 135 as a module cz that not a prime.
Thanks. I think I refer to some code template which is not so good.
here is my wrong submission 235733205 and right submission 235733378
I understand now, 131 is not mod number, it is base number and should be prime.
Base not necessary is a prime, I use base number randomed in range $$$[0, MOD)$$$
That is a good choice.
ratings please..
When will the ratings change
ratings?
Go everyone "WHERE IS RATING!!!"
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
If you want to decrease my rating, do it quick :(
Any ideas why is the contest showing up as unrated for me?
Where are ratings???
MikeMirzayanov
awoo
BledDest
No rating update?
I have got a message that unfortunately my solution 235585909 for problem C coincides with another solution. I don't know how did it happen. I used IDEONE. Maybe that could be the reason.
problem F https://www.luogu.com.cn/problem/solution/P3292
Regarding the mail -> Your solution 235540146 for the problem 1902A significantly coincides with solutions agrahariprajjawal5/235540146, iit2022164/235540396. Such a coincidence is a clear rules violation.
This has happened because of the use of a common source published before the competition. It happened because of the same template I and the other fellow user use. The template is taken from some internet source which I don't exactly remember. Unfortunately, the code inside the solve function also matched which is a mere coincidence. It's not strange that such small piece of code get matched. So, this is a mere coincidence and please revoke the submissions of mine done during the contest. I agree on providing more clarification regarding this.
guys after the rating recalculations this contest was marked unrated for me while I'm still a newbie and haven't gone to 2100 to make it unrated why?