Hello Codeforces!
On Feb/16/2023 17:35 (Moscow time) Educational Codeforces Round 143 (Rated for Div. 2) will start.
Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.
This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest, you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.
You will be given 6 or 7 problems and 2 hours to solve them.
The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.
Good luck to all the participants!
Our friends at Harbour.Space also have a message for you:
Hello Codeforces!
We look forward to seeing Mike Mirzayanov and Nikolay Kalinin again at our Barcelona campus when they teach Advanced Algorithms and Data Structures.
In this course, students focus on key and in-depth algorithms and data structures that form a modern computer specialist’s toolkit.
We are always excited to see Codeforces participants as our students at Harbour.Space! Once again we are giving a special discount for the single course participation in Barcelona, Spain (travel costs and accommodation are not included).
50% of the spots have been filled already, hurry up not to miss your opportunity to get selected!
At Harbour.Space University, we continue providing work-study opportunities; in this case, we offer motivated Data Scientists the opportunity to work and study in Barcelona in partnership with Noventiq, the leading global solutions and services provider in digital transformation and cybersecurity.
We are looking to distribute scholarships for intensive study programmes at the highest level for eligible candidates that will join our journey.
Candidates will be working on the following tasks:
- Invent and implement approaches to solving problems of computer vision and machine learning, form requirements together with the team;
- Plan experiments, train models, evaluate their quality and embed them in pipelines;
- Work with data, the formation of technical requirements for markup;
- Register the results of training runs of models and track the dynamics of their performance;
- Write algorithms for pre and post-processing of images and videos, the logic of scenarios for processing media data;
- Conduct research in the field of Computer Vision: classification, detection, segmentation;
- Engage in the optimization of neural networks: distillation, quantization, pruning;
- Prepare models for production.
- Carry out the development of custom algorithms and modules for our video analytics platform
All successful applicants will be eligible for a 100% Tuition Fee Scholarship (22.900 €/year) provided by Noventiq company for the Data Science programme.
CANDIDATE’S COMMITMENT
Study Commitment: 3 hours/day You will complete 15 modules (each three weeks long) in one year. The daily class workload is 3 hours, plus homework to complete in your own time.
Work Commitment: 6 hours/day Immerse yourself in the professional world during your apprenticeship. You’ll learn from the best and get to apply your newly acquired knowledge in the field from day one.
University requirements
- Bachelor's degree in the field of Mathematics, Statistics, Data Science, Computer Science or similar
- English proficiency
Work requirements
- Excellent knowledge and experience in using Python, as well as TensorFlow/PyTorch;
- Experience in implementing Deep Learning models for commercial projects;
- Experience in solving real problems in the field of Computer Vision
- Experience with Linux OS, Git, Docker;
- Understand the principles of operation of current popular architectures of neural networks;
- Possession of the culture of conducting experiments, you know about reproducibility and logging, you can objectively assess the quality of the model;
- Spanish language proficiency;
UPD: Editorial is out
Like it! Educational rounds are always nice and educational!
Lets Hurt the Problems(➢ᴗ➢)
Humans are a strange species... We look for problems to solve them.
I wish good luck everyone and post meme to make you a bit happier)
Hope to become Pupil in this Round
Same :)
In education round, we will have a great education!!!
Wish interesting new problems.
Hope to become specialist in this round :)
As an inactive account, hope this round is educational.
Missing the picture of Harbour.Space University!
I need an extension that predicts the rate of change of the rate during the round
carrot
thx bro
C was an insightful problem for me. I thought at first I would need some complicated range query data structure but then I remembered being amazed that 1791F - Range Update Point Query could be solved with just a std::set. So I drew inspiration from that problem and decided to simplify my ideas and came up with a neat priority queue solution.
C is doable with just 1 sort + array iteration.
can you elaborate little more how we can do C
Taster 1 only drinks tea 1. But we can add the capacity of taster 1 to teas 2...n, and pretend that taster 1 drinks all teas. This leaves the same amount of teas remaining after taster 1 drinks. At the end, we must remember to subtract (N — 1) * (capacity of taster 1) from the answer for taster 1.
Similarly, we can add the capacity of taster 2 to teas 3...n, and pretend that taster 2 also drinks all teas. Doing this for all tasters, all tasters drink all teas, and now the order of the teas doesn’t matter.
We can then sort all modified tea amounts, and the solution is not so far from here.
Pretty cool, thanks for sharing! An alternative solution that I implemented uses binary search on prefix sums to find the rightmost drinker that can be satisfied and uses the $$$+1$$$ on left and $$$-1$$$ on right boundary trick. Solution
Segment tree beats in problem C 💘💘💘
LOL No just basic binary search
LOL Yes just segment tree beats
Isn't it $$$O(n log^3 n)$$$ ? I thought It could not accept because of large $$$n$$$ constraint
It's $$$O(nlogn)$$$
Can u please elaborate your functions?? Like what does segment_max_equal does?
It assigns $$$max(A_i, 0)$$$ to each $$$A_i$$$ in range $$$l \leq i \leq r$$$ (in this case all of $$$A_i$$$ 's)
The logic behind his solution is that for taster $$$i$$$ you can decrease $$$b_i$$$ from all of [0, i] remaining drinks and then make negative drinks zero. after that, difference of old sum [0, i] and new sum [0, i] would be amount of drink taster $$$i$$$ drank in the process.
Oh, nice! I got it now, thank you!
Hey, I know you didn't write the code in question but I just cant seem to understand how he sets the max(Ai, 0) for every range in O(logN) time?
I understand the first function set.segment_add(), it can be implemented with lazy propagation, but the second one, st.segment_max_equal(), I can't understand at all.
Actually I don't know how
max_equal
operation works and I just use it as a black box. but if you are intended to get how it works I guess this post could be helpful.Here is accepted code of this approach: 194087474 (segment tree template is not mine and I took it from wery0 submissions. you can look at his original submission for the problem too)
If u have code it up C problem using Segment Tree, then Can u please share the link of your submission
I used range update and point query which could've been done with difference arrays easily but I coded out a lazy tree. submission
So many submissions on D ;(
How to Solve D?
I think the idea is each group needs to be colored either BRB or RBR inorder to extract the maximum 2 edges from each group and we cannot extract more than that from each group. Then we need exactly half of the group to have BRB and half to have RBR inorder to have n/2 vertices of each colors . For each group we can calculate the number of ways to color BRB so that we get max 2 edges and same for RBR
I could not figure out how to implement the part where we select exactly n/2 groups to have BRB and n/2 to have RBR in the given constraints
its simple permutation and cobination qestion : just calculate nC(n/2): n!/((n/2)!*(n/2)!) i.e permutation of n objects out of which (n/2) are alike of 1st kind and (n/2) are alike of 2nd kind.
For each triangle find # of ways to choose two edges to get the max value, multiply those numbers and finally multiply (n / 3 choose n / 6).
Hmm.. I thought that n/3 choose n/6 is over than max of long long int. So I had the problem to multiply n/3 choose n/6 at max value of edge. How can I solve this problem?
that's why in the qestion it is mentioned to use % with that number 998.... whatever it was.
got confused in such a simple thing in contest ;(((
happens to the best of us bro.
Some observations:
Basically, if $$$f(\Delta)$$$ is equal to the number of copies of the minimum-weight edge in the triangle $$$\Delta$$$, then the required answer is $$${n/3 \choose n/6} \prod f(\Delta_i)$$$.
My submission: 193883975. I first computed $$${n/3 \choose n/6}$$$ (by accumulating a factorial vector) and then checked each triangle one by one, sorting the three edges and counting how many copies of the minimum edge there is.
I have a Doubt .. what about cases with same color .. RRR [ This will give 0 Result I know] .. But in calculation .... we are taking only .. [Half --> RBB | Other-Half --> BBR ]
can't understand what about RRR or BBB ... why are we not taking those cases ..
Each triangle can contribute at most one edge weight to the answer. Then RRR or BBB is impossible since in this case we can't maximize the answer. (if we change a RRB to RRR, where can we get the lost weight back?)
If you have a $$$RRR$$$, then you must have a $$$BBB$$$ or $$$BBR$$$ somewhere.
If you have $$$BBB$$$, then you can convert $$$(RRR,BBB)$$$ into $$$(RRB, BBR)$$$.
If you have $$$BBR$$$, then you can convert $$$(RRR,BBR)$$$ into $$$(RRB,RRB)$$$.
In either of the cases, the answer becomes "better".
What's combinatorics behind D? How do you calculate how many different combinations you can have from the 3 types of triangles after counting their amount?
solved using only binary search and range updation where we perform update queries first and in the end calculate the ans
Dont understand. I think you meant to reply to someone asking help about C.
anyone else solved C using binary search + difference array?
I have solved it using Binary search + dif array. The basic idea behind was that I calculated for every tea how many testers will be able to test the tea, for this I just calculated the prefix array of tea, each tester can have at max and then simply iterated the array by finding upper bound for each element in that prefix array.
This is my submission 193883206
me
To some people E may be standard and obvious, but the thought process is fun, so I think it's a cool problem.
The problem would become equivalent to this:
we have an array in each operation you can decrease an element by one. Whats the minimum number of operations needed to make the array increasing/decreasing the array?
Am I right?
How do you solve this?
Not really, it's to make the array strictly increasing first and then strictly decrease (except 0).
by sorting the array I mean making it increasing.
having the number of operations needed for each prefix and suffix the answer would be sum of these two plus the value of the Ith element
btw whats the solution
For each i calculate the min # of operations to make
a[1..i]
increasing. This can be done with a monotonic stack:For each i, find the biggest j < i such that $$$a_j - j \le a_i - i$$$, then $$$a_{j+1,\dots,i}$$$ should be set to $$$\dots, a_i - 2, a_i - 1, a_i$$$, let that cost be x, then $$$pre_i = pre_j + x$$$.
Then calculate the similar thing for suffix, the answer is $$$\min(pre_i + suf_i + a_i)$$$
yes, my problem is that I dont know how to calculate pre[i] and suf[i].
Sorry, just added that part.
thanks for the solution
I thing the problem is like.
we have an array in each operation you can decrease an element by one. Whats the minimum number of operations to make it strcitly increasing then stricty decreasing?
I just don't know how to do that.
Maybe it's standard
yes right. me too
Can you give some hints to solve E ?
Try to think what the array looks like before applying the final explosion.
I don't think, the difficulty of understanding it is comparable with the whole solution)
For me D felt much easier to solve and took few minutes to think. Though i finally found an implementation flaw which was getting me tle in c and got accepted in the end with 5 mins remaining :)
I miss D by 1 min :(. Due to PC for case 2 in which two values of edges are the same.
Can someone please look at my Segment tree solution for problem C? And tell what's the problem with rangeupdate?
https://codeforces.me/contest/1795/submission/193906545
I think my template screwed up my really good rank.
How did you plan to use a segment tree with constraints <= 1e9?
It's giving the wrong answer at pretest 1.
Pretest 1 is the sample.Having wrong answer on pretest 1 indicates that your program failed to pass the sample.
Well, it is possible with "implicit key" (I don't actually know, how it is called).
The idea: you create the node, when you first need it. Every query creates up to $$$O(\log{n})$$$ nodes. So the size of tree is $$$O(q \log{n})$$$ and the total time is $$$O(q \log{n} \log{q})$$$. However, there can be problem with time limit.
I iterated over each tea and checked till which person would the tea last until it's completed using binary search on prefix sum of persons capacities, all these persons in between will drink tea with there full capacities and last person will drink remaining, so i just stored and updated multiples of their capacities in segment tree and maintained an additional array that stores remaining tea that was drank by last person.
Hopefully it wont get hacked
Problem C and 923B - Producing Snow are same.
Yes, it is. I copied my solution from 923B, slightly modified and submitted to this problem during the contest. Submission
How would you remember that's i done before that , if you able to remember then then how to manage to find that problem name
I solved 923B yesterday morning before the contest during my work on reviewing all of the solved problems during 5 years if I can solve them (or just to catch main idea) faster or not, is there any progress or degradation. So, I just was lucky to read and solve this problem at the same day.
Most of div2C problems do not require segment trees.
I used segment tree and passed, although it's really dirty compared with others' solutions. You may check my code here: 193914285
Did anyone else find D to be much easier than C?
by idea no, by implementation yes
the idea for D came to me almost instantly, however I had no idea how to optimize C lol
to be honest D idea easy but you need more themes, and knowledge about MODs, factorials, when in C you need prefix sums and binary search
Yeah need to look those up. I could only come up to a O(n2) solution for C with prefix sums
I thought D looked easier than C, but I only had 8 minutes to read it :(
What would be the expected rating of E?
About 2300-2500 I think.
A: Check adjacent elements in the string u=s+reverse(t), any possible pair of towers is a pair of prefix and its corresponding suffix of u. If there's <=1 pair of adjacent same letters, we can cut the string from that position, otherwise there will be adjacent same letters in any pair of prefix and suffix.
B: Check if there's a range [l1, r1] with l1==k, and a range [l2, r2] with r2==k (range [k, k] will satisfy both conditions).
C: For each sort of tea, use binary search to find how many tasters it can serve. They will form a subsegment of [1, n], and for each segment [l, r], we do diff[l]++, diff[r+1]-- and the prefix sum of diff will be the amount of tea each taster can drink. Also we need to calculate the difference of a[i] and b_sum[r]-b_sum[l-1] (where r is the maximum r that b_sum[r]-b_sum[l-1]<=a[i]), and subtract it from ans[r].
D: It's always better to choose n/6 triangles to color it by RRB, and other n/6 triangles colored BBR. And for each triangle with weight w1, w2, w3, we check how many values of {w1+w2, w1+w3, w2+w3} is equal to the maximum of them, let this number be cnt[i], then the answer is C(n/3,n/6)*product(cnt[i]). (IMO D is easier than C)
E: We need to choose an index k, and let h[1...k] become increasing (strictly-increasing for non-zero elements), and h[k...n] become decreasing (strictly-decreasing for non-zero elements). Let b[i]=h[i]+i, c[i]=h[i]-i. Then for j>=k, we need to decrease b[j] to max(j, min(i=k...j)(b[i])), and for j<=k, we need to decrease c[j] to max(-j, min(i=j...k)(c[i])), and we can calculate ans[k] from prefix-sum of c[j] and suffix-sum of b[j]. We can iterate k from 1 to n and update prefix-sums, then iterate from n to 1 and update suffix-sums.
Let's see how to update suffix-sums of b[j] for k=n...1. Process for c[j] is similar.
First, let's ignore the condition that h[j]>=0 (which means b[j]>=j). We use dp to update suffix-sums. Let dp[n+1]=0 initially, and dp[k] is the sum of suffix-min in range [k, n]. Suppose that we know value for k+1...n, and we need to calculate dp[k]. To transit from dp[k+1] to dp[k] means that we use b[k] to update all suffix-min in range [k+1, n]. Let pos[k] be the minimum value that pos>k and b[pos]<b[k] (pos[k]=n+1 if such value doesn't exist), we can see b[k] will update all suffix-min in range [k, pos[k]-1] to b[k], and suffix-min in range [pos[k], n] will not be affected. Therefore, dp[k]=(pos[k]-k)*b[k]+dp[pos[k]]. All values can be pre-calculated by monotone stack in O(n).
Then we consider the condition that b[j]>=j. Let min[k]=min(i=k...n)b[i]. In fact, if pos[k]<min[k], we still can let dp[k]=(pos[k]-k)*b[k]+dp[pos[k]], but otherwise we do dp[k]=(min[k]-k)*b[k]+sum(i=min[k]...n)(i).
Makkapakka orz
C's statement was difficult to understand
Screencast with commentary
Hi guys! you can check the video editorials for todays contest here
problem C: https://youtu.be/zHyyBxM7aiQ
problem D: https://youtu.be/EOmEXRpml6k
Great work bro try to be regular Upload editorial for all contents
yeah bro, I have been uploading all editorials regularly :)
good contest TBH, BUT actually why would you make B much easier that A, you are missing the point for problem A, at least for me :)
Can someone explain why my solution 193899252 in contest for D gave wrong answer? It is something related to modulus
you're supposed to mention the link to your submission as well so that people could see it.
Yes. $$$\frac{X}{Y} \mod M \ne \frac{X \mod M}{Y \mod M}$$$.
E.g.: $$$X = M + 1$$$, $$$Y = 2$$$;
$$$\frac{X}{Y} \mod M = \frac{M + 1}{2}$$$, but $$$\frac{X \mod M}{Y \mod M} = \frac{1}{2} = 0$$$
You should use modular inverse to calculate answer
Really Bullshit Contest! Problems B and C are sharing the same clasic idea — range addiction queries ! (alghout the limitation varies)
Also problem D is mush easy to be problem D div2, if you've passed 9th grade, you may simply solve it! You may guess what I'm saying, UNRATE PLZ!
can anyone please tell me the time complexity of tourist's C CODE
$$$n$$$ inserts on a multiset and at most $$$n$$$ deletions : $$$nlog(n)$$$.
I also implemented with same idea.
Suppose our multiset S contain let say m elements and we are processing index i , so we can consider all the elements which are smaller than b[i] and erase them from the set and keep the elements greater than it. Deleting the smaller elements wont allow them to participate in further iterations and thus causing atmost n deletions.
Now all the elements greater than it are decremented in the same amount delta, so we don't need to perform decrement operation in that range, what we can do is keeping a variable delta for tracking the decrements
Now when we process the next index i + 1, we are essentially comparing an element x in set by considering x — delta with b[i+1].
Smaller elements such that x <= b[i+1] + delta are removed from the set as they eventually become 0 and positive elements remain with the effective delta being delta = delta + b[i].
TC: nlog(n)
can anyone tell what should have been the approach in the second question my approach was if k lies in the interval of atleast one segment print yes else no please help me where am i wrong ?
The issue is that it must be possible for $$$k$$$ to be in the highest number of intervals, with no ties allowed. For example, if there is only one interval, with range $$$[k - 1, k + 1]$$$, then regardless of whether you keep or remove it, the number of intervals with $$$k$$$ will always be equal to the number of intervals with $$$k - 1$$$ and also the number of intervals with $$$k + 1$$$.
What you need to do is find some interval that includes $$$k$$$ but not $$$k - 1$$$ and also find some interval that includes $$$k$$$ but not $$$k + 1$$$. If you can find both (note that the interval $$$[k,k]$$$ already satisfies both), then the answer is YES. Otherwise, the answer is NO.
When will be the next icpc registration start, Or any other major Google compitition dates to register please let me know
Google competitions -> https://codingcompetitions.withgoogle.com
ICPC depends on regions, but it usually starts in Autumn, as far as I know.
Why Google coding competitions registration are delayed
As I know, project managers of competitions were laid off.
https://codeforces.me/contest/1795/submission/193901690
https://codeforces.me/contest/1795/submission/193902178
I found these two cheating
where to find a complete solution of a contest problem?
Can Anyone enlighten me with why my submission giving TLE.i just couldn't figure it.i think my solution time complexity is O(n^2) and it should be able to pass in 2 seconds for given n.Correct me if i'm wrong. https://codeforces.me/contest/1795/submission/193882619
O(n^2) is not fast enough. With n being 2*10^5 n^2 is 4*10^10 which is too much. You need an O(nlogn) solution here, you can read about it in other comments.
Thank you so much for the reply. I was thinking blindly till now.
Your time complexity is 4 * (10 ^ 10) in the worst possible scenario. As far as i know C++ can process no more than 10 ^ 9 operations in 1 sec(in the best scenario).
I made video Solutions for A-E.
Great work bro
Deleted
Care to explain how did you get your hands on someone else's code?
Lol you should be really ashamed ! you are the worst cheater in history !
The trick you were trying to pull off by changing the contents of your comment, all the revisions are publicly available if you don't know. Just accept that you have cheated and come clean.
Approximate rating of C?
1500 i guess
1600
3300 AC is too much for 1600
Is there any groups for post contest discussion Where we can discuss our approach to the problem like discord server or telegram or meet Or we can have a new one
I have discord sever for that.
Common discord group- https://discord.gg/P5TEZB4zAr
(Beginners) The new coders- https://discord.gg/4DH3PWUX3t
(Intermediate) Pro coders- https://discord.gg/H8TeFjvq6z
(The Pro coders channel is most active)
Is this contest rated for 2100+
No, it's rated only for div2.
But there's no (*) in common standings for 2100+ participants and they are included in common standings
yeah it's just broken for edu rounds
it's still not rated for them, you can check other educational rounds.
Hi guys. Any rating predictions in D?
1600 or 1700.
Thanks:)
how to solve F?
binary search the answer, then do the tree dp, let dp[x] be the minimum score of a subtree of node x you can get, where the score of a subtree rooted at x is:
if dp[x]<=0 that means that node x isnt yet painted black and that we have a white path starting at x in the subtree of x which is of length -1*dp[x]
if dp[x]>0 that means that node x is painted black and that it contains currently a chip and that the chip needs dp[x] more steps which will go upwards from x
Can anyone help me to review my code for Problem C, I got TLE on test 2 and I have no idea about it. I use the binary search and difference array, I think it is O(nlogn). But got TLE. https://codeforces.me/contest/1795/submission/193929768
make vectors global as this 193938114
Thanks, it works! But do you know why this will work, and my one will cause the TLE?
oh, I misread the n/N. Creating a vector of size N is O(N), and you create it for each testcase. So you will be TLE.
Your code complexity is $$$O(T * MAXN)$$$. $$$MAXN$$$ in this case is $$${10}^5$$$. If T is large (>= $$${10}^4$$$) you code will TLE
Whyy can't we do the nCr for prob D using FOR LOOPS! I've been stuck on Case 6 the entire time just because I didn't use a template...
I can't believe I wrote this for A:
Sometimes it seems I just get stuck with some wrong observation for over an hour...
Submission.
When will the ratings be updated?
Problems were very interesting, especially E was very beautiful problem. Thank to authors for such nice contest!! :)
When will the ratings be updated?
It usually takes a super long time to update your rating in EDU/div3/div4 rounds.
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Can you help me see what's wrong with my code? So the problem is E,stk is the number of blood counts that differ by 1 from the number in a row. I would appreciate it.194084249
Take a look at Ticket 16736 from CF Stress for a counter example.
Thank you very much
Hello i wish some of the codeforces managers review my comment. i've worked really hard on this contest but still got skipped because i've submitted the same codes for the first two problems (A and B) on my second account and i have proofs that i owne both of the accounts, and i can show the proofs for any of the managers.
the second account name : frb_husen2 account link : https://codeforces.me/profile/frb_husen2
Have you ever read the Terms of agreement before you register yourself
Here it is read again
The registration confirms that you: