Hello Codeforces!
On Jan/29/2021 17:35 (Moscow time) Educational Codeforces Round 103 (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 Roman Roms Glazov, 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!
Congratulations to the winners:
Rank | Competitor | Problems Solved | Penalty |
---|---|---|---|
1 | sometimesnaive | 6 | 176 |
2 | SSRS_ | 6 | 184 |
3 | MagicalFlower | 6 | 251 |
4 | hank55663 | 6 | 255 |
5 | Strigon-12 | 6 | 276 |
Congratulations to the best hackers:
Rank | Competitor | Hack Count |
---|---|---|
1 | stdmultiset | 133:-79 |
2 | Tsovak | 98:-10 |
3 | dapingguo8 | 68:-6 |
4 | MohamedAboOkail | 65:-3 |
5 | peti1234 | 60:-1 |
And finally people who were the first to solve each problem:
Problem | Competitor | Penalty |
---|---|---|
A | Warawreh | 0:01 |
B | MysteryGuy2 | 0:04 |
C | WZYYN | 0:10 |
D | peti1234 | 0:09 |
E | CoderAnshu | 0:06 |
F | - | - |
G | iaNTU | 0:57 |
UPD: Editorial is out
Please please please don't make it as hard as today's contest :/
Please don't do that, don't give me hope :)
As a ......
Do you want to get more contribution?say "as a"?
i think u mean negative
He couldn't complete his sentence. Perhaps some big stone fell on him while he was typing. Sad.
Your ideas are ...
And a small pebble fell on the "." key?
Let the comments with "as a" begin
I am new to Competitive programming, codeforces made me fall in love with it! Thanks to you all amazing people!
yes same
i tried everything to find my interests and nothing felt like i enjoy doing them
as i started CP on codeforces 2 months back i feel like this is all i want to do for the next large amount of my time :) really thankful to the best internet community
Same brother, initially I thought to first finish all Data Structures and Algorithms and then start CP, but doing it simultaneously is much better and helps retain concepts easily. Every new coder should start doing CP. (PS: Only if you don't mind your ratings dropping and you trust yourself enough, that one day, you'll make it.)
so Madara Uchiha saved you, huh.
I killed him!
I killed OrochiMaru, Itachi
As a participant of today's contest kindly make the problems easier...
I hope it will be a good round
I will die if there will be adhoc problems in this contest too.
educational=(4problems or more)*adhoc XD
That's a pretty bad equation, not gonna lie.
what is adhoc?
adhoc problems usually ask you to construct or to build something. Usually those problems can be solved without knowledge of algorithms. For example, you can check problem F from codeforces Round 640 div4. This is an example of ad-hoc problem.
The problems on which you die thinking which algorithm to use while contest and then after looking at the editorial think .. "wait ... thats it ?"
My current rating is 401 will I be rated in this contest?
cout << "YES\n";
Bro I am new to codeforces, please tell me based on my rating which all contest can I participate and be rated ?( Like div 1,2,3)
Div 2,3,Educational,Div1+Div2(combined rounds).
Thanks bro
I am a newbie, it really made me happy that I could solve few problems. Looking forward to upcoming contests!
those who dont want jobs out of it will loose hope soon
Well not getting a job when you are working hard is depressing but you have to believe in yourself, it can do miracles
well, recently a newbie girl I know received an offer from FAANG.
I am neither a newbie nor a girl, darkness awaits me.
I'm in high school and do CP. And there are many others who don't want a job out of it. Problem-solving using DSA is fun!
well i am 2 nd year electrical engineer i do it to keep my brain sharp but our job is decided by such factors we tend to target on this site it all connects.and if u cant get anything out of it u will decay soon thats what i meant
Depends on how you define 'anything'. For many people, there are more things in life apart from getting a job.
I hope i will become expert today..
hope i remain specialist today:)
hope i will become master one day:)
hope
Hope to become specialist today
Are you planning to cheat?
no i am not like you
Hope the tasks aren't too hard, hope everyone can get a rating which can satisfy you :)
There should be a third button IMO XD
There was but it got deprecated: HackForces. Now it's only present on Topcoder with name TopHacker.
Doesn't look like it.
I meant for usual div 2 rounds. Usually educational rounds have more hacks because of longer and separate hacking phase.
MathForces!
Oh just saw you already said it thanks a lot! Can we be friends?
And a forth: MathForces...
I hope i can solve first 2 problems quickly :)
come on!
Writing educational contests is really good way to develop. Thank you for this contest and good luck to everyone!
hoping it to be a hard contest (and not containing math only ;-;)
(
This feels deep. You have my upvote sir
Hello LostCow!!!
This is the most relatable meme I've seen on codeforces. Especially after yesterday's contest and today's.
Waiting for the contest which would take me to specialist :)
It will be a wonderful contest. Best wishes!
Hoping for a good contest!!
Giving a contest after long time today ! Fingers Crossed..
Best of luck to all :)
A and B kinda sucked ngl
before contest i was confident that i will be successfull in protecting my specialist badge. after contest i am confident i will be successfull in getting demotion to pupil
Yeah, but I thought C and D made up for it!
Fu**ing B costed me 7 WA because of floats.
That is why you should always work in integers if possible, if you are comparing $$$\frac{a}{b}\ge{\frac{c}{d}}$$$, compare $$${ad\ge{bc}}$$$ instead. Watch some people like Errichto and you will pick up these things, it helps a lot.
B — balanced
I wasted literary 1 hour on problem C because I forgot typing else... GG I will always be silver...
How to solve C?
I solved C considering three cases:
If we are at index 0, we only have one option, i.e. to start a cycle from here.
If we are at the last index, we only have one option, i.e. to end the current cycle.
If we are at an index in the middle: We check if b[index+1] == a[index+1].
Number_of_vertices[index] - 1 - (b[index+1] - a[index+1])
.b[index+1] - a[index+1]
.Number_of_vertices[index] - 1
.Link to code: https://codeforces.me/contest/1476/submission/105933562
I did same still got WA on test case 3, Can you help? The code is easy enough to understand.
Here's my code see if that helps.
Firsty, I think that you have messed up the implementation in the if-else condition.
1 - a[i+1] + c[i] - b[i+1]
which should actually bec[i] - 1 - b[i+1] + a[i+1]
.Link to the submission: https://codeforces.me/contest/1476/submission/105949955
Hope it helps!
You can use some dp to store maximum length cycle including all vertices of a[i] as ans[i].
See my solution:https://codeforces.me/contest/1476/submission/105907608
It can be solved by dp; firstly, let
dp[i]
denote the longest length ati
th chain, "the longest length" means the longest length you can get before the cycle is formed, so we can getdp[i]=max(dp[i-1]+c[i]-1-abs(a[i+1]-b[i+1])+2,abs(a[i+1]-b[i+1]))
, then we update the answer bydp[i-1]+c[i]+1
. one thing to be noticed is that whena[i+1]=b[i+1]
,dp[i]
should set to0
.Was I the only one who went into C and D thinking that they are graph problems, but both of them turned out to be dp ones? :P
I thought so, but after seeing that the length of the chain can be 1e9, I knew it wasn't a graph problem.
Yes, C isn't greedy.
There might be a greedy algorithm to it, but I solved it by trying all possibilities using dp
I solved it using greedy.
Could you tell me your approach?
You can refer to this comment: https://codeforces.me/blog/entry/87282?#comment-755104
How to solve D?
Note that the structure of the graph only depends on the parity of time elapsed. Therefore, we can use $$$(node, parity)$$$ as stage and use DSU to maintain the reach-ability between stages and the sizes of connected components.
Make a left_c and a right_c array which represents the maximum number of cities city i can traverse that lie strictly on it's left and it's right respectively.
Then, notice that if there lies a path b/w city i and city i-2, then city i can traverse all those different cities that city i-2 can because at time t and time t+2, all paths are exactly the same. If there just exists a path b/w city city i, and city i-1, then increment one to the left_c array for the city i. And, do similar things for right_c.
Answer for the i_th city is left_c[i]+right_c[i]+1
You can check my submission
What means "b/w city"?
between city*
My idea was the same. You can check my implementation with regex (with eval-groups inside) — 105956225.
How to solve A? I'm new here...
take range of get the smallest number x with x*n >= k
or if n > k : x*n >= ceil(n/k)*k
How to think for such solutions?
"disclaim: It took long time for me :("
-the first observation is that the smallest value for n positions is : 1n,2n,3n,4n, ...
say you have n = 3 and k = 11 => 1,6,9,12 , 15,... you can get 11 by replacing 4 by three 4,4,4,3.
-so you can get any lower values of x*n by replacing on or more x by lower value
you should take into account n > k
Comment section is filled with amazing people! It's motivating :)
watch the stream, it's very helpful
nope.
Lets consider two cases:
n >= k
. ifn
is divisible byk
, you simply set everything to 1. otherwise, you set some of the numbers to 1, some others to 2, so that in effect you have added "enough 1s to maken
divisible byk
.n < k
. There is no point in making the sum any bigger thank
and by pigeon hole principal, at least one of the numbers will beceil(k / n)
. As(ceil(k / n) * n) >= k
, it suffices to subtract some amount from some of the numbers to make the sum equal tok
.Omg -141 delta for me
Question D is far more simpler to me compared to question B and C :/
I had a terrible day too!
At least some previous contests had interesting problems I could not solve and I got negative delta, but this one was Painfully pointless to me :(
my contest in 1 photo :
the division with 1 huh? Yes it took me some time as well. But no worries mate I lost 1 hour on C not because I could not find the solution but just because I forgot a simple 'else' statement. Look at my submissions on C if you don't believe. Like what separates the successful from the unsuccessful I believe is just the ability of removing the blindness effect that I don't even know what casts it upon us. It's like we are in a MOBA arena and we have a passive ability of getting blinded for 1 hour randomly. We can be blind friends together hit me up if you ever want us to do a Virtual Contest together and then laugh at our blindness.
Not really. First I tried binary search and now i am wondering what was wrong on that solution, after i found some interative solution but i used the wrong formula :) .
Ah sorry I just realized you stuck on B and not A. My bad. Anw I solved B without binary search I would be very interested to see how it is solved with binary search.
first you have to observe that the solution is to add some number just to p0. Now ,let x be the solution and you can find it with binary search. For each x, check if can be a solution. If not, have to increase x, otherwise ,decrease it. The article in EDU about binary search is very nice, I ve learned a lot from that one.
Oh this is smart but it requires more complexity than the linear solution. Still very smart nevertheless. 105884577
I just read you solution. It is linear as well. Oh I can see where it got hard maybe when you where trying to calculate how much to add. I just did a max there since the maximum is what you need. Damn I could rank up so much in this round had I been a little more careful.
my binary search solution : CODE
Yes so it is O(nlogn). It just instead of doing the division and checking for the modulo that I was doing you do the BS to find the correct value.
Bro how did multiplying by 100LL instead of 100 get the answer in B ?
because your variables are int, and 100*1e9 = 1e11 and this value for int is overflow
If all variables and array are taken as long long. Will it still overflow ?
nope, should work fine.
Don't you think the copying during contests is increasing day by day?Also there are many smurfs account in the contest. Affects rating of a lot of people
Who is copying?
AkashRamjyothi1 see his solutions
105874881 : A
105895241 : B
105915359 : C
105929955 : D
while(true)
{ int abc = 0;
He is using these lines to save his code.
awoo, MikeMirzayanov please look into it
In order to check if a program is a copy of another one, can't the program be subjected to run on a set of deliberately faulty test cases during system testing? Programs whose behaviors, that is, the errors/exceptions they throw, the current values of all present variables, and the variable names in use, are the same for all test cases can then be weeded out...
You are asked to rearrange the patterns in such a way that the first pattern the j-th string matches is p[mtj].
This is ambiguous. I thought it meant the rearranged patterns index mtj, causing me to write completely wrong code.
Same here
E was really nice. for each string s, for all the patterns that matches it, I put a directed edge from the first pattern it should match (mt for that string) to every other pattern that matches it and the answer is YES if the graph formed is a DAG?
I thought the same but dismissed it quickly because how is that not TLE? Each string can match to potentially all $$$m$$$ patterns. So $$$O(m^2)$$$ sized graph (or DAG) right there? The only explanation I can think of is that maybe because of the contraint that each pattern is distinct this bound can be tightened? Do you have the proof?
EDIT: Oh got it. smh. Each string can only match to atmost 16 patterns (because of distinctness constraint) so size of graph is bounded $$$O(m)$$$.
According to the question, all patterns are distinct. For a string s, given its maximum length is 4, we can have at most 2^4 + 1 patterns that match it (for all binary numbers from 0 to 2^4, if $$$ith$$$ bit is 1 then keep s[i] as it is, else replace it with '_').
A string can match with at most 2^k patterns. Let's take an example string "abc". Which patterns can it be matched with? "abc", "a_c", "ab_", "a__", "_bc", "__c", "_b_", "___" So, for each position of a string, we can either keep the original letter as it is, or replace it with '_'. so, for this reason a string can match with at most 2^k patterns.
Yes, and the answer is the topological sort of the DAG.
Can someone please tell me why is my code failing, I did a 2 way kadane-ish dp and printed their sum. WA_CODE
The dp seems to be off by one, since the indices go up to $$$n$$$ (as there are $$$n + 1$$$ cities).
I think problem B needed more tests, although figured out how to get 99 on test 1 it doesn't seem like it for the other tests.
The most educational things I learnt from A and B is that don't forget to use ceiling when comparing
The hardest part of E was understanding it. Nice problem set though, thank you!
I still didn't understand the problem. Can you explain it?
Let the initial arrangement of patterns be $$$P$$$. Your goal is to find an arrangement of patterns $$$P'$$$. $$$P'$$$ is such that, for each string $$$s_j$$$, the first pattern in $$$P'$$$ that matches with $$$s_j$$$ is $$$P[mt_j]$$$.
That how it should be written in the statement!
As for me, it was absolutely unclear that s[j] matches P[mt[j]], and P remains the same. Maybe I misread something, but it seems there is no contradiction if you understand that part of statement differently
Reading it again, I feel it was somewhat clear what they meant. In my hurry to read it, I misunderstood and wasted 45 minutes on solving a different problem. Perhaps the problem statement should have held your hand a bit to be completely clear (like I did in my statement). I can't complain too much though, it's my fault I didn't read it closely enough.
At least that other understanding doesn't pass samples. That was the point at which I figured out that something is wrong: coding is done, I fail first sample, OK let's actually look at the samples now...
Yeah I wouldn't understand if there were no sample testcases.
In Q2 multiplying by 100LL instead of 100 got me AC. Any reasons why ?
Integer overflow
Any article or reference on the same ?
Costed me 6 WA.
$$$p_i$$$ can be up to $$$10^9$$$ so $$$p_i\times 100$$$ can be up to $$$10^{11}$$$. Max int is usually $$$2^{31}-1$$$, which is slightly above $$$2\times 10^9$$$.
Can you please tell me why I got an overflow even after taking the entire array as long long https://codeforces.me/contest/1476/submission/105897736
On changing 100 to 100LL I got AC.... Can't understand why!! Thanks In advance
you are getting overflow on your tmp variable
UPD: got AC here
YES GOT IT!!
imagining C graph cases gave me a headache but I liked this contest you have my upvote
How to solve G?
Mo's algorithm
Take a look of this problem and its solution.
https://codeforces.me/contest/700/problem/D
How can we see its solution?? Its editorial isn't available.
Well, you can find some solution of the contestants in the comments.
only $$$O(\sqrt n)$$$ different values in the cnt array, so then apply Mo's algorithm to it and use a list to maintain different values in cnt, and then for each query take out all values and brute force
total complexity is $$$O(m\sqrt n\log n+n^{5/3})$$$.
But i am unable to handle the updates. Please elaborate.
I'm assuming you know how to handle the problem without updates (using Mo's).
To handle updates, split the queries (type 1+2) into blocks. Now, within each block, run Mo's. When you start processing a block, make sure that all the updates in the preceding blocks have been applied. To account for the updates in this block for a query of type 1, you can naively iterate from the start of this block applying all applicable type 2 queries. Since you broke it down into sqrt(m) blocks initially, it is guaranteed that you'll only iterate block_size times at max even when doing updates naively for each type 1 query.
You might need to fiddle a bit to find the appropriate block size though.
You mean for every block run Mo's naively?? Then for every block it should be $$$O(N*sqrt(N))$$$. Please correct me if I am wrong.
Google "Mo's algorithm with update"
In C what does this mean that "First chain is skipped", does this mean we cannot take any node from first chain? I had initially set the ans to c[0]. That was the only reason I was not able to solve C and costed me wrong ans :)). First chain skipped means I thought I cannot connect any node to previous ones, otherwise I can taken some nodes from first chain.
your last nodes can be in first chain.It means your cycle can't go above it.
Can Anybody Please give Me some counter test case i.e., Fail My Code
Question Link
Solution Link
I tried Everything but not able to find any counter case, Also did Stress testing, Still Not able to find it.
try to use multiplication instead of division in check, that can be a problem.
Yes got accepted after doing this, Thank-you so much brother
How to solve E?
Take a look at this comment
If there are multiple $$$p_i$$$s match the same $$$s_j$$$, then the specified constraint is basically implying the specified pattern exists before all other $$$p_i$$$s. Thus, we can keep track on the indices of patterns and build a dependency graph based on the constraints. For any specific $$$s_j$$$, there would be at most $$$2^k$$$ distinct patterns matching it. Thus, at most $$$2^k$$$ edges would be added to our dependency graph. Hence, the problem is reduced to check if a given directed graph with $$$n$$$ vertices and at most $$$m\times 2^k$$$ edges is acyclic, and if so, report any topological order. This can be solved by topological sort.
There are a few trivial cases to notice, like the specified pattern not matching the given string or different occurrences of the same string being matched by different patterns, you may refer to my submission 105914103 for implementation details.
I was unable to sove even Problem A, can some one say the intuition to problem A. I tried binary search for problem B, but it did not pass 3rd test case
Try 1 2 1 1 1000000000
Increase the Max value.
Consider all array elements to be 1. We need to increase these numbers until the sum is divisable by k. So, first step is to find the next multiple of k bigger or equal to n. Second step is to find the max array element if the sum equals the number found in first step.
I learned this the hard way — 99% of the time you don't need this big code for problem A. You probably need to take a deep breath and think at more fundamental level what the question is really asking.
And my solution got hacked. To all the losers making hacking attempts, go fuck yourselves.
It would probably have failed system tests anyways so I don't think it matters.
Here's a tip for you
$$$\lceil \frac x y \rceil = \lfloor \frac {x + y - 1} y \rfloor$$$
simple dp for C . a is vector of heights , b and c are vector of endpoints connecting to previous. we have to recompute this dp between all the inclusive indices of where b[i+1]!=c[i+1]
dp[i]=abs(b[i+1]-c[i+1])+1 +max(a[i+1],dp[i+1]-1-abs(b[i+2]-c[i+2])+a[i+1]+1-abs(b[i+2]-c[i+2]));
simple code.
Were F and G intended to be that much hard??
I'm really surprised nobody solved F. I've been rechecking and stressing my solution for hours, and I'm still sure it is correct, but it's strange that nobody got this problem.
How to solve it? Is it dp(i, j) — farthest covered positon to the right if we have processed i first positions and j is the farthest to the left uncovered position, with segment tree? Or it is wrong?
$$$dp_i$$$ — the maximum prefix we can fully cover with $$$i$$$ first lanterns.
Let's look at how can we solve it in $$$O(n^2)$$$ with this kind of dynamic programming. First of all, let's write it forward. Which transitions from $$$dp_i$$$ do we have?
It is obviously $$$O(n^2)$$$, how can we optimize it? Let's write this dynamic programming backward. The second transition is changed to backward dp easily, what about the first one? Suppose we want to turn some lantern $$$i$$$ to the left. Let's iterate on the prefix $$$j$$$ that we will "connect" to it; for this prefix, $$$dp_j$$$ should be at least $$$i - p_i - 1$$$, and we update $$$dp_i$$$ with the maximum of $$$i - 1$$$ (since it is covered by lantern $$$i$$$) and the result of max query on $$$[j + 1, i - 1]$$$.
In fact, we need only one such prefix — the one with the minimum $$$j$$$ among those which have $$$dp_j >= i - p_i - 1$$$. So, we build a minimum segment tree where each pair $$$(i, dp_i)$$$ is interpreted as the value of $$$i$$$ in position $$$dp_i$$$, and with min query on the suffix from $$$i - p_i - 1$$$ we find this optimal prefix, from which we should update (and to update, we can use any DS that allows max queries on segment — in my solution, it's another segment tree).
Source code
I was able to upsolve using what I think is a different DP, with $$$O(n \log n)$$$ distinct transitions, so both solutions are probably correct. Yours is definitely a much easier idea to implement.
I reached my idea by supposing for some $$$i$$$ that every lantern in $$$[0, i]$$$ has had its direction chosen and lantern $$$i$$$ is the first unilluminated lantern. Then, there must be some lantern $$$j > i$$$ which is turned left to illuminate lantern $$$i$$$, after which the set of lit lanterns is a prefix, and every un-set illuminated lantern would thus be wasted unless turned right, which lets me greedily illuminate every lantern less than some value $$$k$$$. If $$$k = n$$$, that is a success; if $$$k = j$$$ then $$$k$$$ is facing left; otherwise $$$k$$$ may as well face right.
It then turns out that there are at most $$$1 + 3 \log_2 (n-i)$$$ meaningfully distinct choices for $$$j$$$, and these are "easy enough" to iterate over: If $$$j$$$ is not the farthest-right-reaching lamp in the $$$[i+1, k)$$$ interval, no other value of $$$j \in [i+1, k)$$$ can possibly get a better value of $$$k$$$. But $$$k$$$ is at least 2 times farther from $$$i$$$ than the previous usable value of $$$j$$$ was! So the worst-case progression looks something like $$$j_0$$$, then $$$j_1$$$ (furthest reach in $$$[i+1, k_1)$$$), then $$$j_2 < k_1$$$, and then $$$j_3 \geq k_1 > i + 2 * (j_0 - i)$$$.
Submission link: 105953208
I had the same idea after the contest. You can simplify the code by doing some observations:
With those observations, I managed to get my code size at a little below 100 lines.
Submission: 106013279
Fs in the chat for question F
can someone say y my solution failed? i am confident logic is somewat rite. solution logic: cross multiplying the equality a*100<=k*sum and checking if condition false, add differnce to overall sum
We have the same mistake
it should be
(a[i]*100LL-k*s + k - 1) / k
don't ask me why :(
can someone tourist vovuh BledDest Roms Neon ecnerwala jiangly Benq boboniu Petr Radewoosh maroonrk Monogon neal explain y?
dude don't do this
Hey, I understand that you want to make a point, but don't you think tagging is unnecessary? I believe noone likes to be tagged just to be asked to debug someone else's code.
You should add (difference/k) to the overall sum and ans.
try this you will understand why.
1
2 100
1 2
The authors should put a good sample cases, it's educational round not destroying round
bad people in math (like me) will not figure out the division when
k = 1
How can the answer of this case of problem C be 4?
3
3 3 3
-1 2 3
-1 2 3
Can anyone please explain what I am missing?
How many tests will problem A have? There're 1000+ hacks...
I think the authors should manually look at the hacks and form some set of new testcases which cover all the corner cases, otherwise system test will continue for eternity.
Finally a time for me to be on the "+11" side of a widespread hacking event :D
I am deeply sorry for the people who got hacked though, I've been hacked multiple times before and I know exactly how that feels.
brilliant contest! Thank you
In problem E, "You are asked to rearrange the patterns in such a way that the first pattern the j-th string matches is p[mtj]." doesn't clearly state that index mtj is referred for initial arrangement.It should have been stated clearly.
C was harder than D
Problems were good, I liked how ABC needed more thinking than coding and more thinking speed than typing speed.
It was an interesting contest even tho problem D was a standard one LOL.
thank u guys for 'A's weak pretests... :'((((((((((((((
As a...... As a novice at code/algorithm, I like codeforces! It's amazing and I like the feel to try my best to solve the problem... also I can't solve D which made me sad
It was hard and my solution on GNU C++17 64 bits FAILED BUT SAME SOL. ON C++17 PASSED...LOL
My standard screencast, with the standard tradition of misreading at least one problem
Nice pretests for A, as an tradition of Educational Rounds.
Felt you
is there any extra points for hacking in educational rounds ?
thanks for great contest (i have 51 hacking successful =)) )
Just one thing: was it really necessary to have a two-letter variable like $$$mt_{j}$$$? First I saw that there is an $$$m$$$ variable, so I immediately interpreted $$$mt_{j}$$$ as $$$m\cdot t_{j}$$$, and that didn't help at all. I mean, I would understand $$$match_{j}$$$, but $$$mt_{j}$$$?..
And they also didn't specify which p they are talking about, the changed one or original.
I thought p[mtj] is a pattern after permutation :(.
I have to congratulate the setter of problem G. My solution looks like something well known, but I've never did something like that before. Really nice one, I definitely learned new stuff today. Thank you!
What's your solution?
I used Mo's algorithm. I didn't know about the trick to handle updates. A brief explanation of my solution:
Keep track some stuff:
$$$cnt[x]=$$$ how many times number x appears in the range.
$$$tot[x]=$$$ how many numbers occurs x times in the range.
$$$vals=$$$ vector of distinct numbers in array cnt.
It's really easy to update $$$cnt$$$ and $$$tot$$$ when you add/remove an element. For $$$vals$$$, simply push all the values to the vector while moving Mo's pointers, and after that remove values the ones that are irrelevant (those for which tot[x]=0). Also, avoid pushing an element to $$$vals$$$ twice. It's easy to see that after doing that, $$$|vals|<=\sqrt{n}$$$, because all elements are distinct and their sum is $$$<=n$$$.
Using the fact that $$$|vals|$$$ is small, you can answer the query with two pointers over the array $$$vals$$$.
What is the complexity of this implementation? I can't understand the amortized analysis of the update part
when you use Mo's algorithm with updates, you have you use size of blocks $$$S=n^{2/3}$$$. In fact, i read somewhere that it's optimal to use $$$S=(2*n^2)^{1/3}$$$.
Time complexity for addittion/removal of elements and push/rollback of updates is $$$O(S*(n+q))$$$ amortized.
Time complexity for iterating elements and removing values form $$$vals$$$ is $$$O(S*(n+q))$$$ amortized, because each operation pushes at most one element to the vector.
Time complexity for answering queries after removing irrelevant elements from $$$vals$$$ is $$$O(q*sqrt(n)*log(sqrt(n)))$$$ because you need to sort the vector of unique values before using two pointers method.
So, total time complexity is $$$O((n+q)*(S+sqrt(n)*log(sqrt(n))))$$$. Please notice that this analysis uses the fact that $$$S \approx n^{2/3}$$$ (not $$$sqrt(n)$$$). In practice, the solution works a lot faster (my code runs in 1500 ms).
For those interested in the details about complexity of Mo's algorithm with updates, there is a really nice blog, written by Fype, that explains everything :)
Thank you for the explanation.
Great contest. Problems are interesting and educational. I enjoyed solving them.
I don't know why, but I feel like at least 1 of my 4 problems will fail system testing :(
The penalty for each incorrect submission until the submission with a full solution is 10 minutes can someone explain what this 10 minutes penalty mean? and if we submit the correct solution after certain incorrect submissions there will be no penalty right?
No. Penalty means that if you submit a correct solution, you get the time for that solution plus the penalty. That is 10 minutes per submission, buf the first submission is for free.
Will it system test later,or just announce the final standings after the hacking time?
Can someone please tell me what error is there in my logic for this. I check for all elements in reverse order if the increase coeeff <= k and if its not I increase p0 by a sufficient amount. Link to soln: https://codeforces.me/contest/1476/submission/105888794
Difference between right and wrong in Question A
double n,k;
cin>>n>>k;
if(k<n)
k=k*ceil(n/k);
ll val=ceil(k/n);
cout<<val<<" "<<ceil(k/n)<<" ";
Input: 1 1000000000
Output: 1000000000 1e9
Both ans are correct but due to different format ans1 will be considered right and ans2 will be considered wrong.
So do typecast your ans
click
Question B :Using greedy approach.The basic idea is to take the maxdifference from all differences bcuz anything less than that will be satisfied by all other differences also either u start from begining or end of loop.
Here is my code which got accepted 105878231
click
hi
I really need help therefore I really couldn't understand what is the problem with the code which outputs that kind of format in test 3 problem b(but in math the number is correct)
submission:105899297
and its not just only mine
another submission of another person:105852796
help please
In C++, when a really large double is divided by a small number, it changes into the scientific notation. To avoid this, explicitly convert the double to a long long int or int as required in the problem.
.
for C problem, my code failed in 4th testcase.I am not able to figure out the testcase,if anyone has any idea about what the testcase could be. Link to the code — https://codeforces.me/contest/1476/submission/105951904 My approach was to calculate number of vertices of every chain that will be added if i take that chain as an intermediate chain, ending chain, starting chain. i stored these values and calculated the maximum answer.
1
7
16 2 12 2 7 18 8
-1 7 1 2 1 2 2
-1 10 2 12 2 3 12
Correct Answer — 38
Your Output — 37
CodeForce is a great programming site!I love it.It brings me a lot of fun.The change of rating again and again makes me feel very exciting!
Why so long for the editorial? Or is it normal? Sorry I am new, but my past contests had editorials almost in an hour
educational rounds usually have slow editorials and idk why
I really do not understand, why my code for A problem had hacked .. why ceill function returns a wrong value While N & K are long Please can someone expert help me to understand what is the problem here !
this is my submission
https://codeforces.me/contest/1476/submission/105923499 }
simply just don't use ceil, use (n+k-1)/k for ceil(1.0*n/k)
But why that happened !
floating numbers are just too dangerous when you need absolutely correct results like codeforces, this ceil problem is very well known
Thank you .. i did not know that before This mistake cost me a lot this round ☹️
I too used Ceil function, it got passed. In Java ceil returns double so have to typecast it into integer before printing the answer 105866315
For the test case
1
1 1000000000
Your code gives 1e+009 as output, because you are doing "cout<<ceil(1.0*k/n)<<"\n";" .
If you type cast into long long or int ("cout<<(long long)ceil(1.0*k/n)<<"\n";") it will give the correct result 1000000000
yes i did get AC , by deleting celil function .... thanks for information https://codeforces.me/contest/1476/submission/105993493
How to solve the other version of the problem E, i.e where the first matching string is the $$$mt_j$$$ th string in the rearranged permutation?
After reading your comment I realized I misunderstood the statement of E during the contest and tried to solve the problem you mentioned XD
You can keep a condition array where if con[i]=x then it means we can assign the ith pattern in the initial array any index from x to n. Initially, all values in con will be 1. Now for each string, mt pair we can update the con array for all patterns which match with the string to max of their initial value and mt. Now after processing all strings, we assign indexes to patterns in decreasing order of their con value from n to 1 if we can assign index to all then ans is yes and we can print the order else it is no.
In that version you don't need the graph/top sort. Instead, go through the strings s_i and enumerate all the patterns that it can match (by adding wildcard slots just like the original version of E). For each of the enumerated patterns check to see if there's a p_i that it is equal to and assign the mt value to that p_i (using some map-like data structure). If the p_i already has a value then only update the value if our new value is larger (that is, if s_i already set it to a value mt_i=2 for example and s_j has value mt_j=3 for it, then the pattern must be in position 3 or later — if it was in position 2 then it would violate s_j's mt_j=3 condition). Note that there might be pattern that don't have any value assigned — that means they don't match any s_i and they can be put anywhere. Make a filler queue and add these in.
After you've gone through all s_i then you need to fill out the answer array. Go from index 1->n and for index i if there's no pattern p_j with value mt_q=i then you can put an entry from filler in. If there is a pattern, then you can put that in and then put the other patterns with mt=i into the filler queue (they can go anywhere behind i and they won't violate any requirements anymore). This will give you an answer array, but you need to actually be a little more careful for some edge cases.
When a p_i has value j and is put in index j, every s_q with mt=j must match this (otherwise the first matching pattern won't be j). To make sure this is the case, you will also have to store a count for each p_i (in addition to the index value) — in the step when you updated values you also update the count when the old value and the new value is the same (this is just the number of s_i that will get triggered by this pattern when it shows up in that given position). Now, in the last step when you fill the answer array by picking a p_i for index j, you have to pick the one with the highest count, and the count has to equal the number of s_i that have mt_i=j.
Unfortunately I solved this version of the problem E. Here is the code which I have tested against many random inputs and then realised that the intended problem is something else.
When rating changes are updated for educational rounds?? I am new here.
https://codeforces.me/problemset/submission/1476/105958353
https://codeforces.me/problemset/submission/1476/105956041
These are my 2 submissions for problem B. 2nd got accepted but first is giving wrong answer on test 5 case 994 (truncated). Can anyone tell me where I have gone wrong?
In the accepted submission int is defined as long long:
#define int long long
Yes I changed that too still wrong answer. When i removed #pragma GCC optimize("Ofast")
pragma GCC target("avx,avx2,fma") these lines it got accepted. Any reason?
when will the ratings be given and why did they roll back the ratings of previous contest,i was about to become a pupil :(
Editorial, please
How this submission is getting accepted and not TLE as clearly their is a for loop that goes till 'n' and 'n' is 10^9 and test cases 't'= 1000. and time limit is 1 sec. Link: https://codeforces.me/contest/1476/submission/105860386 I thought in 1 sec only 10^9 operations can be done
The compiler probably optimizes the for loop.
I tried my level best to hack it.
No, in 1 sec. 10^8 (approx) operations can be performed
the loop was optimized by the compiler. I checked locally with
-Og
and it ran 5 seconds for each test.I have a question regarding the complexity of memset. Can this code pass in 2 sec?
Original Submission: 105929137
memset an array of length $$$n$$$ takes time $$$O(n/w)$$$, which $$$w=64$$$ for codeforces.
You memset 3 arrays with length $$$4\times 10^5$$$ for $$$10^4$$$ times in the worst scenario, and when that happens it takes $$$\dfrac{4\times 10^5\times 10^4\times 3}{64}\approx 2\times 10^8$$$ time, which is able to pass in 2s.
upd. tried a hack with the worst scenario mentioned above. the solution passed in 1.2s.
Thank you so much.
editorials please!!
Hoping this round taught you that you shouldn't prepare contests anymore.
Hoping that downvotes will teach you how to write a good comment
I got a message from system telling me that my solution for C problem is similar to In_Memories_11_08_2020/105891388, not_tehlka/105903063, yinuowang/105910649, sk_loves_Ritika/105921450, rivnam/105928243. In my opinion, the code is not at all copied and the only thing that is same is the fast IO template. Link to the template. Please look into the matter. It is the second time it has happened with me unnecessarily. Please restore my ratings
i also got similar meassage with same accounts mentioned by you...
i think that problem involve only certain conditions in loop thats it.. I AM DAMM SURE THAT I
HAVENT SHARED CODE AND EVEN NOT COPIED ......i request them to please check it out and restore my rating ...
please help even if there is some valid proof of my cheating or sharing i am ready that you delete my account else do not repeat this and restore my rating...
i am so sad
Same problem here, any help would be greatly appreciated :)
As you can see from my submissions for this contest as well as past contests, I have used this fastIO code many times.
same bro even i almost everytime using same template
even ** i do not feel code are same ** i read 2 of them and campared with my code
some responsible person have to say something upon this matter
this is very bad .....i am saying this beacuse i am confident and need help of others to overcome this
@MikeMirzayanov can any anyone please help !!!!!!
today i got a message that my C solution matches to someone ... but i say confidently that i haven't used
any public IDE platform to code and even i did not share code with someone
so why like this with me ??? i am so sad please clearify ...
my request to others please help us to raise this issue ....even i am ready to accept that delete my account if i really do cheating or sharing but don't do like this ... ruined my performance.
I just received a message from the system telling me that my solution for the C problem is similar to In_Memories_11_08_2020/105891388, not_tehlka/105903063, yinuowang/105910649, sk_loves_Ritika/105921450, rivnam/105928243. I had reviewed the solution of all these people only the fast io template is matching. So, Please look into the matter. I think the codeforces plagiarism checker is not working properly. Although my rating is dropping in this contest according to the cf predictor yet I want my rating restored as I don't want any bad spot on my id.
Your solution 105901746 for the problem 1476C significantly coincides with solutions Fubuki_AI/105892973, misra_17/105901746, samcpp/105933007.
This happened because we all are using template of user Um_nik . All our code inside main() is different.
What should i do now?
how this submission accepted ? plz anyone explain time complexity of this submission..Advance Thank you.. https://codeforces.me/contest/1476/submission/105860386
only O(n) for each test
can anyone tell me why i have 51 hacking successful but i have no more bonus ? . Thank you and sorry because of bad english
Because it was an open hacking round.
Hacking solution in this round doesn't contribute towards any bonus or extra rating.
ok thanks !
I received a message from the system: Attention! Your solution 105913814 for the problem 1476D significantly coincides with solutions rk_no/105911811, nestedcode/105913814, MA7887/105919769, MayFlyyh/105931103, MTL_Sakura/105936065.
(I don't know these guys and didn't use idone or any other online compiler.)
The solution to the problem can be implemented in a standard dp approach and that is what I did during the contest. I saw the above mentioned codes and they are implemented in the same fashion. I think these type of codes should be treated differently during plagiarism check. This indicates that we can still improve the current plagiarism checker and stop such cases from happening. Innocent people deserve better. :( MikeMirzayanov awoo Please look into the matter.
The same thing has happened with me. I've written a detailed comment regarding this issue here. https://codeforces.me/blog/entry/8790?#comment-755688
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Only one score to blue qaq. In addition, I've noticed one thing. Although the rating change of this game has come out, the rating change of div1 in the previous game is still frozen. Is it unrated? Or, the rating change will be recalculated at that time? I don't understand too much.
MikeMirzayanov awoo This round should be rated for me QAQ
I turned from Master to Candidate Master in Codeforces Round 698 (Div. 1) and then participated in this round.
Same here, seems like people who droped from Master in Codeforces Round #698 (Div. 1) are unrated in this round.
Why am I not rated?
I participated in EDU Round 103 and got more than 70 places and qualified for the score. Why did I not gain rate??
Same thing happened to me. Also in the last Educational Round 102 I was rated despite being Master before the contest. (I turned from Candidate Master to Master before Educational Round 102.)
Yesterday I have received two unexpected warnings from CodeForces plagiarism checker. The first one says, my solution 105930169 for the problem 1476D - Journey significantly coincides with solutions bleh0.5/105914875. After sometimes I got another warning that my solution to the same problem (1476D) significantly coincides with solutions bleh0.5/105914875, tejas10p/105917332.
There exists a very simple solution to the problem 1476D. So there is a high chance to match the solutions of two different persons. I have explored the submissions of the first 100 people according to the common standings of this round. Among these 100 submissions, I found 7 submissions that are almost similar to my solution. I'm mentioning these submissions here.
My submission:
The two submissions that matched with my submission:
Similar submissions:
105883915 Here only difference with my solution is I used array and he used vector.
105878527 He used vector and wrote the solution in a separate function.
Other similar submissions:
I am requesting MikeMirzayanov to look into these unexpected warnings. It's totally an injustice to me -_-
MikeMirzayanov awoo
rating Rollback -> update rating by this contest ->update rating(#698)
so, for example momohara, not update rating by this contest.
this contest rating changes :
lets add them :) -> roll them back -> add -> roll back
why?!
Exactly, I have never seen this before that they roll back the rating changes for an educational round !