Привет, Codeforces!
В 18.01.2024 17:35 (Московское время) состоится Educational Codeforces Round 161 (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.
Спасибо тестерам раунда shnirelman и Minder за ценные советы и предложения!
Удачи в раунде! Успешных решений!
UPD: Разбор опубликован
Hopefully I reached Expert :)
I wish everyone a good contest!
My 3rd rated contest. Wonder if I could reach True Rating 1700(displayed 1400)
Good Luck and Have Fun everyone!
Hope this round aint Mathforces af. Usually, Edu rounds = Mathforces
What's the difference between an educational round and normal div 2 round?
New: Educational Rounds on Codeforces!
Such a short and clear announcement I hope problems statements be like this too!!!
Hopefully I can get Pupil(not Newbie) :/
You didn't even give the contest
BledDest Round
You Know its Graph Time
you're right
Lets, Hope I can get Expert color.
Hope I can get Expert badge.
Often, how much harder are Educational Rounds compared to normal rounds? I want to know whether to compete or not. This is because my last educational round gave me some serious trauma: Educational Codeforces Round 153 (Rated for Div. 2)
Slightly more difficult than normal div 2 round. Sometimes edu rounds needs good observations skills also.
Alr thanks! I'll participate.
Hopefully I reached Specialist :)
How many problems I need to solve to become a Pupil in this contest?
Educational round is overrated
Educational round means you have to study gcd well :)
As I screwed up in the last div3, I hope to solve 3-4 problems in this round :|
Upd: Solved 3. Did C Overcomplicated :(
bad explanation of first question
[deleted]
and you are also using an alt, so shut up, do not complain of stuff you are personally doing
How did you know he is using an alt ?
i guess someone snitched his alt which made his accusation hypocritical
What happened to "romanian diversion strat"?
Didn't realize E was easier ,should've tried that first.
thats apio2022 perm
Okay I start to implement it
I got 98.8 pts and stuck on it :(
D is a lot easier than E, E has just appeared before
Yeah and I thought D<F<E... E needs constructive skills...
B was a good problem for such a simple concept but i made 2 wrong submissions.
Yes! Problem statements were clear and precise. But I must be blind... :(
I have skill issue
Was C that easy ? is it based on some standard algorithm/ some standard problem ? i was thinking in direction of Floyd Warshall algorithm. but could not come up with solution. I'm seeing around 7000 successful submissions. or it was based on something else like Dijkstra/DFS/BFS ??
i pre-calculate cost of go forward and backward
yeah that's the resolution i think
This problem maybe doesn't require the shortest path algorithm
C was a modified version of prefix sums
It can be shown that in order to go from point x to a point y, going back is never a good choice.
Let's assume wlog that
x < y, you have to reach for sure point x+1 to get closer to y Ifxis closer tox-1thany, you can go to x-1 at cost 1 and than come back to x at cost at least 1. So, at the end, you will stay in pointxwith -2 coins. Then the path fromx-1toyis mandatory, so the final cost will be increased by two. This is the best condition.Damn, the first question reduced my life by a few years. :')
I have skill issue
I think E was way easier than it ought to be. Good contest nevertheless.
I think E was way harder :(
Wasted too much time in problem A :/
can someone please explain problem A? Thanks in advance.
this took me 90 minuts to figure out
loop from 1 to n
if(a[i]==b[i]&&c[i]!=a[i]) then yes and break if(c[i]!=a[i] && c[i]!=b[i]) yes and breakprint no if loop finished without any yes
Same lol!. Usually the first problem is too stressful than other problems
awoo Loved the D and people think LinkedList is overrated.
Still do think its overrated after writing this piece of art which even i can't read now Submission
That's upto how we implement it. https://mirror.codeforces.com/contest/1922/submission/242308688
i know that lol i am bad at coding, point is that linked list is overrated
I think have a better code using a linked list and its usage is underrated in CP submission
Bro just use set
I got drown in caseworking C. Any ideas on avoiding, like, a dozen of caseworks?
you can create a Generic function that decrease the number of those caseworking.
242254308
Wow! That was neat!
I tried to partition the array into several groups, and each group contains two "center" cities where everyone leads to, and then hop between the groups before caseworking the best answer out when they are in the same group.
That was painful. Those with a daring soul may see it here --> 242305848
my first E yaaaaaaaaaaay
Anyone feel like the wording on A was weird?
Took me 20 minutes and out of the contest to understand the concept of "uppercase is lowercase this time".
I do not understand how problemsetters cannot see that such a wording is bad.
what is the approach for B?
Note that the sides of the triangles are powers of two. So, at least two of the sides have to be equal. This observation makes it a lot easier.
how to count the valid triplets?
Use combinatorics, create a map to keep track of frequency, for each frequency in map, you can choose 3 sides of same length NC3 (N = frequency of element and you can choose 2 same sides and 1 from smaller sides, NC2 * CF (cumulative frequency before the current element). Intuition is 2^k + 2^(k + 1) is less than 2^(k + 2) using GP formula you can prove, therefore 3 sides cannot be unique, isosceles and equilateral triangles can be formed
E was basically APIO 2022 P3 with nerfed limits?
How to solve F?
Good contest
I submitted B 14 times ;-;
I can feel your pain :(
Did the authors intend to cut off solutions to D that uses two
std::sets? I got TLE on my first attempt before finally switching to segment trees.No, I used two
std::sets as well and it passed in 700mssame, my passed in 389ms
Same. It was meant for Set. At any point if you remove X elements, you will iterate for 2*X elements and out of which if you remove Y elements, next time you will iterate for 2Y elements. So overall 3*N operations will be carried out.
I see. I guess it was my implementation that was inefficient, then.
How did you solve it by segment trees? Like what was each Node storing, can you please share.
The segment tree was only used to get the global minimum of the remaining health points of each monster (i.e. $$$d_i$$$ minus the total attacks dealt to it). Each node stored the minimum of that value among all indices in its range, as well as the index that caused that minimum value. This allows us to simulate each round and find out which monster died during the round.
I used linked list — 265 ms.
I used 2 vectors and a static linked list. It's supposed to be O(n)...
C was intuitively not too hard.. just too painful to implement.
How to guess the solution of problem E?
Notice that this problem appeared in APIO and copy paste
orz
10^18 says it should be done in O(logn).
I'm pretty sure it can be done in O(n), using the fact that increasing array of length n contains exactly 2^n increasing subsequences. Oh, I meant n being the length of resulting array.
I think considering case of $$$1, 2, 3, 4, 5, 6 ...$$$ is very natural.
Then understanding $$$1, 2, 3, ... , n$$$ gives $$$2^n$$$, should be enough to be able to construct solution
I tried this idea. I noticed, that if I have blocks, which look like: $$$|10 \; 11 \; 12|7 \; 8 \; 9|3 \; 4 \; 5 \; 6|1 \; 2|$$$, and their lengths are $$$a_1, a_2, \dots, a_k$$$, then number of subsequences is $$$(2^{a_1} - 1) + \dots + (2^{a_k} - 1) + 1$$$. Then I can factorize $$$x$$$ in sum of degrees of $$$2$$$. For example, $$$37 = 2^0 + 2^2 + 2^5 = (2^5 - 1) + (2^2 - 1) + 3$$$, so I use $$$a = {5, 2}$$$ and append two decreasing numbers at the end.
This is $$$O(log^2{X})$$$ solution, which is incorrect.
Nice idea. I think after that you should have realized, that building solution using independent blocks would result in very lengthy sequence. And after that realization should have abandoned this approach and returned one step back to $$$1, 2, 3, 4, ...$$$
If we add $$$3$$$ to the end of $$$1, 2, 3, 4$$$ we would get additionally as much sequences as there were sequences in $$$1, 2, 3$$$
So in general adding $$$m$$$ to the $$$1, 2, 3, ..., n$$$ would increase number of sequences by $$$2^m$$$. That is I believe — final idea of solution.
I figured this out but was unable to implement within time :(
I didn't like the round (yes, I am going back to expert again)
is it div3?
A div four F had comparably equal ACs to today's D and lower ACs than E.
maybe because majority of high rated users don't write div4?
You're comparing an outlier with another outlier
Horrible statement for D!
Am I the only one who was struggling with problem B ;-;
Not sure why but I found A relatively harder than B. B was pretty much straightforward as triangle is only possible if sum of two sides is greater than third. Note that 2^0 + 2^1 + .... + 2^n < 2 ^ (n + 1). So you always have to take two same numbers. Reminder can be any number which is less or equal to this.
Yes agree B was trivial once u realise that fact
A was relatively hard, I was confused for like 6 minutes, then I just guessed based on testcases.
F missed the first line sides are 2^a[i] not a[i]
E looks like easyer than D because you can find the solution on the Internet :)
Cheaters cheat what can we do :( I spent all my time on D
OMG! Stuck on B for more than 30 minutes, not until the contest is finished did I notice that the length is $$$2^{a_i}$$$ not $$$a_i$$$ .
Just noticed it by reading your comment :/
Its 2^ai
Sorry, typo, fixed.
the length is $$$2^{a_i}$$$. Stuck on A also because if this
The string doesn't match the template if the given condition doesn't hold for at least one i.Same here, i too thought the same and trying to figure out the sliding window solution!
Problem E coincides with APIO2022 Problem C completely.
In APIO2022 Problem C — Permutation, It requires an array of length less than 90. In today's contest, it just has a limit that the array of length at most 200. Besides, In APIO, it also requires that elements should be distinct. It has been weakened.
I think that E<D.
noo it was the first E i did :(
You copied from the internet, cheater
no it was easy
I feel the same , I saw some submissions to E with 9 lines of code. Even if it didn't appeared in some contest , it would still be an easy problem and clearly not E or (may be even D) level.
I totally agree with you
how did you find that? Had you solved this problem earlier? I searched problem E for almost 20-30 minutes but was unable to find any similar problem.
how do u solve for < 90? I can understand upto 118
It's hard, you can find discussions here
Can someone tell me why my code for D get runtime error? Thank you in advance
My Code
Chinese A-E video problem solving in bilibili 【Codeforces Edu161 (A-E讲解)】 https://www.bilibili.com/video/BV1pw41177jC/?share_source=copy_web&vd_source=3e1f94fdc189dba4d4738f04ef57df8f
Wasted 10 minutes in Problem B before I noticed the power of 2.
Us
Me thinking that D was about decreasing health instead of just checking if damage is enough. :[
ohh yes I was thinking that too, I realised after a while..
I submitted B 5 times and got WA.Because I thinked pow(2,0)=0.:)
Can some high rated coder tell me how to become an expert asap?
You just need to work on yourself. Try solving previous contests in virtual mode or just try solving problems in archive. There you can choose the types of tasks in which you are bad. If you can't solve something, don't look at the solution right away, try to solve by yourself. But if you really can't, check solution and always write your code by yourself. Also there are some useful courses in edu, you can solve them too
Div 2. where E solved by more than 1800 people,
bye-bye my rating 😂
nvm
it's okay ill try again next round. btw can i participate div1 round?
yeah but div1 is harder. Div2 and div1 happens at the same time you can participate in div2 if that is better for your level.
I don't understand why my hack didn't work on problem B Test: 1 4 0 0 0 3 This is withing the constraints of the input given but it shows unsuccessful hacking attempt because expected answer is 1. Shouldn't expected answer be 0 since no triangles can be formed obviously.
can be formed from 0 0 0
definition of degenerate triangle is given in the problem(area must be greater than 0) do you really think a combination of 3 sticks of length 0 is a triangle?)
the length of each side is 2^Ai not Ai
so in case Ai == 0 the length is 1
its shown in first line of statement
Yeah you are right I made a similar mistake during contest, my brain us melting.
bro the length is 2^ai not a[i] GG
Decent contest. A and B is okay. C is somewhat fun but probably should only be limited to a<b (failed rhe caseworking like an idiot, but even then turning from the left-right variation to the other way around doesn't require much effort) Who tf allowed E to exist? Even I, a literal green, knows that it's APIO22's perm at first glance. Stealing problems from chinese OJs or some random unpopular place, while a scummy thing to do, would still only allow a small set of participant to get a major advantage. But stealing from fricking APIO??? What kind of coordinator even allowed that to exist lmao. What's next? Stealing literal IOI problems? Come on man what the hell
......and the fact that anyone who takes CP seriously should know about the existence of oj.uz, which...allows for free copy pasting, is, uhhhh, funny. Stealing from a judge that allows you to see submissions post-AC is already bad, stealing from somewhere that you could ctrl+c ctrl+v for free..... Should've copied instead of debugging C smh
then why you didn't solve E?
Anyone plz tell me how can you solved the Problem C or D, I was solved only A,B. Thankyou
Problem C was only the cost of going to
X -> X+1 -> X+2 -> ... -> Yif $$$X \lt Y$$$, orX -> X-1 -> X-2 -> ... -> Yif $$$X \gt Y$$$. The reason is that if you go back to a closest city you have to retreat anyway, so we only need to calculate the cost of going to the left, or to the right. To do this efficiently we use prefix and suffix sums.Problem D for me was only implementation, I simulated the steps, but instead of iterating all the monster and removing them for $$$N$$$ steps I only save the monsters that are affected by removing the dead monsters. I think this is $$$O(n \log n)$$$?, because in each iteration the monsters affected are reduced. I really don't know and possibly get hacked. For removing monsters I use Linked List.
D is $$$O(n)$$$ if implemented properly because each monster is removed once = n in total, and each removed monster affects two in the next round = 2n. +n rounds = still $$$O(n)$$$.
Something like this. My initial implementation was $$$O(N log N)$$$ improved by reading other solutions.
242304887
what is wrong with my solution!! this problem suck!!
In the combinations function you cast res to int, which can overflow in some testcases
your ll C(ll n, ll k) actually return a int instead of a long long.
Going back to newbie :(
Could someone explain why and tell me the number of increasing subsequences?
UPD: I found out why, thanks
In third testcase you have 12 subsequenses. In forth testcase you have 36 subsequenses.
There are 12 increasing subsequence.
I actually liked E, It took me an hour to come up with a pattern, the pattern was related to bitmask of X. It could have been better if length of array was atmost 120.
Can anyone tell me why my submission on D gets WA?
The problem is the first occurrence of this line:
If the monster on the left is missing/dead, you still need to check the monster on the right. You should combine that if-statement with the next one, instead of skipping the rest of the loop body.
didn't expect that.. Thanks
What does this mean "The penalty for each incorrect submission until the submission with a full solution is 10 minutes"
When you commit the correct solution, you get points like you would have commited it 10 minutes * wrong times later.
assume that you sent problem B after 10min and get wrong answer on test bigger than 1
this 10min will be added to your penalty
your handle A: +(0:03) B: -1(0:10)
your penalty will be 3+10
sorry for being complicated
even if you send 100 wrong submissions, it doesnt count to your penalty until you submit a correct one. Each wrong submission costs 10 penalty points. A submission is not wrong if it is accepted or compilation error or your code fails in the very first test.
i missed up this
On the scoreboard, people are ranked by number of problems solved first (higher is better), and by time second (lower is better).
The time is the submission time of all the solutions added together. For example, if you solve problem A, B and C exactly 10, 20 and 30 minutes after the start of the contest, your total time is 60 minutes. For every incorrect submission, 10 additional minutes are added to your time.
However, and I think this is where the confusion comes from, the penalty time for incorrect submissions only applies to problems that you have solved. If you do not solve the problem, that problem adds 0 minutes to your time, no matter how many failed attempts you made.
This prevents situations like where Contestant 1 solves problem A in 15 minutes. Contestant 2 solves problem A in 10 minutes, and then makes a wrong attempt to solve problem B. Giving contestant 2 a 10 minute penalty would make him rank lower than 1, which seems unfair, since both participants solved the same set of problems (only A) and participant 2 was strictly faster.
Can Anyone please explain the logic behind Problem D ...
Consider the monsters before first day. Each monster gets some damage, foreach monster you can tell how many days it lives.
Output answers until the first day monsters die, then remove all monsters that die that day. Repeat.
If you use the linked list approach, then the intuition is this: you can easily compute whether a monster dies in the current round, by adding the attack scores of its neighbors and comparing it to the monster's defense score. If the monster survives this round, it will also survive subsequent rounds, as long as its neighbors don't change.
So the only monsters that you need to check on round X are the neighbors of the monsters that died on round (X — 1). (Round 1 is a special case: here you have to check all monsters.) If you store the monsters in a double-linked list, then you can efficiently remove dead monsters and calculate a list of their neighbors, which you use in the next round, etc.
This way, you do at most O(N) work across all N rounds.
Anyone knows why my submission for problem D gets wrong answer verdict? I am trying to maintain the previous and next monsters in prv[i] and nxt[i], code here: https://mirror.codeforces.com/contest/1922/submission/242332530
Take a look at Ticket 17261 from CF Stress for a counter example.
b Solution:- https://mirror.codeforces.com/contest/1922/submission/242271062 what is wrong in my code
How to solve F? Does it use some specific optimisation?
Naive O(N^3K) dp was just fine.
dp[l][r][k].
Can't you just bruteforce every possible x in $$$O(N x)$$$?
Oh, I see now. That different x's are optimal, in 3rd test case replace first all 2s with 3 and then entire array to 2.
Why is the ans to 3rd sample testcase in F, 2?
Can someone explain B?
we have to pick three powers a,b,c lets assume a<=b<=c. if a=b means 2^a+2^b=2^(a+1) => 100 + 100 ==> 1000 (2^3 addition in binary) the sum has to be less than longest side to have a valid triangle. which means a+1>c but c>=a so we have to take c such that it is equal to a
if a!=b a=0100 b=1000 sum=1100 this sum is less than 10000 i.e we need c to be b<=c<b+1
so we need to take all the pairs in which either 3 or 2 numbers are equal
Can anyone explain how to approach problem D
You can simulate it pretty much. Think of it like this, if a monster is about to be defeated, then after it's defeated, its adjacent monsters will begin attacking each other, and you don't have to think about it again. You then check if the adjacent monsters will be defeated in the next round. Following this you're able to simulate.
Thanks !!!
can anyone tell me where i'm wrong in my solution for problem D? thank you.
Take a look at Ticket 17263 from CF Stress for a counter example.
thank you, I know where my solution failed and I have solved it.
Can anyone help me point out what is wrong in my 242347538 for problem D?
Take a look at Ticket 17264 from CF Stress for a counter example.
Thanks! Finally solved it.
Very simple contest!!
still trying to solve A
Ask Ruchi she will help
E was surely much easier than D.
This submission seems suspicious, the participant has included code from some other problem to avoid plag checks. His exact same code was available in a youtube video during the contest. MikeMirzayanov please look into this.
Problem E, Possible Issue with Judge,
Verdict: Wrong answer on test 2, test case 29
Test case 29,
30
My output for test case 29,
7
1 100000003 2 100000002 3 100000001 4
Judge: Wrong answer The number of increasing subsequences in the printed array doesn't equal to x (test case 29)
I have myself counted 30 increasing subsequences in my output. Please look into this.
242373040
Ok this is really weird actually, I ran your code locally and on an online compiler for X = 30 and got the output of:
8 100000004 1 100000003 2 100000002 3 100000001 4
But when I ran your code on Custom Invocation on CF, I got the output that you described. Really strange.
Actually follow up on this, it prints out: 8 100000004 1 100000003 2 100000002 3 100000001 4
When compiled with G++17 but it outputs:
7 1 100000003 2 100000002 3 100000001 4
When compiled with G++20
This might be your problem...
The judge is correct. However, your code seems to be printing
instead of the output you mentioned for the 30 case when I run it on C++17. Here the answer is clearly > 30. But the output you mentioned in your comment will have 30 favourable subsequences.
Curiously, I got the output you mentioned when I ran it in C++20, so you may have some kind of compiler specific error in your code.
You access outside the limits of your pos array (I think you meant to put j < pos.size() in the if?).
I don't know why there's an empty line in the beginning :(
Many people compare $$$a_i-a_{i-1}$$$ and $$$a_{i+1}-a_i$$$ in their codes, and some of them assign $$$a_0=-inf$$$ and $$$a_{n+1}=inf$$$ to make coding easier. However, if $$$a_0\ge-1e9$$$ or $$$a_{n+1}\le 2e9$$$, then $$$a_1-a_0$$$ or $$$a_{n+1}-a_n$$$ isn't big enough so they output $$$1000000000-0=1000000000$$$.
I think A problem is bad,because its topic is vague
I feel like this contest has tested the contestant's ability to judge time complexity 感觉这场就考验了选手对时间复杂度的判断能力
Wow, 3 years since I last did competitive programming and I still choke under pressure of a CF contest XD
Problem C.
0 8 12 15 20-->8 4 3 5.8 4 3 5and8 4 3 5.>for one array, and with<for another. Change values of array of differences to1when comparison result istrue:8>4>3>5and8<4<3<51 1 0and0 0 1Prepend and append
1to the arrays (as edge elements had only one neighbor):1 1 1 0and0 0 1 1That becomes:
1 1 1 5and8 4 1 1.0to the arrays and make cumulative sums:0 1 1 1 5and0 8 4 1 1becomes0 1 2 3 8and0 8 12 13 14.i<=>j.(Code:242346587)(Perl).
Why am I getting TLEs in problem D? Please help.
Submission using set only, TLE in TC 15
Submission using idea of doubly linked list and set to handle the remaining elements, TLE in TC 7
Because it is O(n^2)
Think what happens if no one ever dies
When does the system testing start?
Video solutions for A-C, D-E
Really wondering if this solution for F is hackable (in both idea and execution time)? I know it had to be DP but the presented idea seems pretty messy and duct-taped, would actually be open to some revelations, and the complexity seems to be a pretty high-constant-factor $$$O \left( n^3 x \right)$$$.
Finally Expert !!!
Strange, I got TLE for my submission for B despite it being O(nlogn) in worst case.
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Can anyone help me find why this code is giving runtime error in testcase-2
Problem-C
PLease help !!!
Easy video explanantion for problem E
downvote, if you liked editorial
Why do you only takes 3 problems to the problem list?