Hello, Codeforces!
I am really excited to invite you to Codeforces Round 763 (Div. 2) on Dec/28/2021 16:35 (Moscow time)! The start time is unusual, so please pay attention.
All the problems were authored and prepared by me. I would like to give special thanks to everyone who made this round possible:
- KAN for excellent coordination with a lot of valuable advice!
- KAN again for translation of statements!
- tdpencil, Stepavly, Supermagzzz, minhcool, snowysecret, generic_placeholder_name, QuangBuiCPP, thenymphsofdelphi, PurpleCrayon, xuanquang1999, vinfat, hieplpvip, tourist, Lihwy, flamestorm for testing and valuable feedback!
- MikeMirzayanov for great Codeforces and Polygon platforms!
- You, for participating!
The round consists of 5 problems and you have 2 hours to solve them.
Wish you good luck and high ratings!
UPD0: The score distribution 500 — 1000 — 1750 — 2500 — 2750.
UPD1: Congratulation to the winners of the round!
Div. 2
Div. 1 + 2
UPD2: The Editorial is out!
Hope that you guys enjoy the rounds, and thank you again for participating! <3
As the first tester, and the first comment, I would like everyone to deliver contribution by clicking that green up button.
Me: Confused on if to upvote blog or upvote comment
Both
omg tdpencil orz
Scoring Distribution?
UPD: Why downvote?
UPD2: Now it's updated.
Usually the score distribution comes shortly before the beginning of the contest__
So many contests by the end of the year! THANK YOU people!
darkkcyan orz
Finally traditional 5 problem style. Unfortuntately, untraditional time I cannot make
hi
love :3
Back to back contests in the end of the year, thank you Codeforces and all problem setters.
Wow tourist is a tester
Oops wrong announcement Thanks @below
I think you have commented on the wrong announcement.
Hope everyone will get good results in this contest. Good luck ;)
wrong annoucement
Is this contest rated for Div 2 ?
It is written Codeforces Round #763 (Div. 2)...
They will WA until they die !
I wonder how many points for each peoblems Emmmm...5 problems make me scared
Rating Distribution ???
Rated for <2100 and unrated for >=2100
I think he meant points for tasks
sometimes they are written in the announcement
like: 500-1000-1500-2000-2500
Sweet Summer Child
Don't downvote anyone blindly. even if someone have good idea or trick to share they will fear to post that trick or idea in comment or blog because of fear of downvotes. I was very upset to see so many downvotes in TadijaSebez his contest(codeforces round 758(Div.1+Div.2)). maybe the way YouTube removed Dislike count Codeforces would be better place if there will be No downvote button. MikeMirzayanov Thank You for building such amazing place and please take my idea into consideration!
True, but better keep the downvote button and hide the downvote count, where comments are still hidden when they got too many downvotes.
two div 2 contest on 2 days, problemsetters are wonderful
hope i got positive delta tdy
Any interactive questions in the contest?
No, there will not be an interactive problem in the contest.
Changed my handle , red colored 3 looks awesome , hope it'll be real one day , starting the journey from this contest
Picked the wrong day buddy.
hope will have great time and not to lose expert.
Updated
PS : The score distribution is not usual for problems C, D, E!
Is CF running slow?
Alice and bob are more than friends (-_-),
How to become intelligent ?. life is hard
Very good round for me, interesting problems. But very strange B. P.S Thanks to author for really cool illustrations for test cases
The Gif in problem A made me so nervous
good job
Cool gifs in A
I always believe first problem should have simpler statement and should be on easy side.
I made two submissions in A one in the minute 00:08 and one in 1:30 just in case the first one failed in the rejudge but i found that in standings my score in problem A decreased from 490 to 270. Will this be final score of my submission to A even after the rejudge?
yes
But why? I thought that codeforces count consider the first accepted submission like ICPC rules. If I knew this I wouldn't make two submissions in A :(
but ur first soluition isn't really accepted it only passed pretests
If a contestant submits several times a problem's solution that passes all pretests, then the last solution is considered as the contestant's verified solution for this problem. All other solutions will be considered as unsuccessful attempts. Codeforces Contest Rules
Now I feel really sad. But thanks.
The quality of problem preparation is elite, the writer has put so much effort into the pictures... Just darkkcyan appreciation comment
I am sorry to give a negative feedback but Problem E is extremely disappointing: no thinking required at all, and standard bin lifting during implementation. I wonder how KAN accepted this problem for a rated contest.
I don't think there is any need for binlifting, it can be solved in O(N) I think (just find the next letter for each node and rest is just dfs).
okay, with Binary Lifting it was completely braindead, but probably there is a solution with a better complexity. Still a very boring problem.
Agree I think E is just too easy for div2E.
Yes, it is O(n). In my opinion, the problem is hard, not because it requires something special, but because it is simple and the participants, on the other hand, know a lot.
Can you please explain how did you solve the problem with a binary lifting ?
I thought of trying the below solution using binary lifting but ran out of time.
Just as mentioned in the editorial, after finding the current inorder representation, we know the potential candidates eligible for doubling.
Lets forget about the restriction k and solve the question first. i.e we can double as many nodes we want. Now for each of the eligible node from left to right, we can just traverse its ancester chain and double it if not doubled. We can stop once we find one ancestor which is already doubled. The complexity of this is O(n) as we visit each node once.
Now if we add the restriction k, only difference is as below.
Imagine the same process and as we double a node decrement k. Now if the number of not doubled ancestors for a eligible node is > current k, we can't double it. To check the number of undoubled ancestors we can use binary lifting (find the kth ancestor of this node and check if it is doubled). If it is already doubled, we can double the rest of the chain as it is less than k. If not we can skip the node.
This is the initial submission I attempted where instead of using binary lifting for checking number of un doubled ancestors, I just looped through the ancestors to find them.
https://mirror.codeforces.com/contest/1623/submission/140946673
ordered_sett cheated.
140905360 140918865 140935467
Do you have any better proof? Those submissions look suspicious, but that's not a definitive proof.
Codeforces Contest Rules
MikeMirzayanov
You're right. At first glance I thought it was just a commented out template, but it's actually a random code copy-pasted multiple times. Definitely breaks the obfuscation rule.
Loved problem D. Kudos to the author(s).
In E, did it matter that the tree was binary and that we consider the in-order traversal? I don't think my solution uses either...
yeah, neither of them matter, except (of course) for implementation details.
I guess that most participants have implemented methods in $$$O(n \log n)$$$ that works on general trees...
When I saw the particular structure of the tree, I guessed that there might be some method with better time complexity or lower implementation difficulty. But since the implementation of the generic algorithm is not complicated and can pass the constraints in time, I didn't bother to think about it anymore...
Neither of them matters for $$$O(n)$$$ methods also, except for convenience. The only thing that would change is if $$$u$$$ comes before all the children of $$$u$$$.
why didn't you use $$$n*m$$$ or $$$nm$$$ instead of $$$n.m$$$ in D it looks like comma and it ruined my day TT :((
I am sorry to hear that. Initially, I wrote it as $$$n \times m$$$ but after some advice, it was changed to $$$n \cdot m$$$. But, well, the solution is solvable in $$$O(n + m)$$$ as well, which is implemented in my model solution, so maybe you can do a pro gamer's move and implement that solution :).
Anybody have idea on how to get the irreducible fraction in problem D?
I was able to derive an analytical form involving (p%)^i, (1-p%)^i, and O(n) constants. But if I calculate the fraction under mod P, it becomes hard to simplify the fraction. And I cannot find a way to simplify it in its analytical form...
XD
Short version:
You can realize the robot's pattern is cyclic, then every step can be mapped to one position of the and calculated using AGP.
Long version:
The state of motion of the robot can be uniquely represented by the tuple $$$(r, c, dr, dc)$$$, so a given pattern of motion will form a cycle of at most $$$4 \cdot n \cdot m$$$ steps.
Additionally for ease of implementation we can note that due to the grid formulation this cycle will never have a tail.
Suppose the cycle is of length $$$k$$$ and there are $$$l$$$ positions $$$x_1, x_2, \ldots x_l$$$ (0-indexed) in this cycle which share a row or column with $$$(r_d, c_d)$$$.
Then the expected time taken to clean this cell becomes the sum of:
where the probability in row $$$i$$$ and column $$$j$$$ represents the probability of the cell being cleaned from position $$$x_j$$$ during the $$$i$$$-th repetition of the cycle.
We can notice that the $$$j$$$-th column forms an infinite AGP with $$$A_1 = x_j$$$, $$$G_1 = p \cdot {(1 - p)}^{j - 1}$$$, $$$d = k$$$, $$$r = {(1 - p)}^l$$$. This can be calculated easily using the standard formula available from Wikipedia or elsewhere.
Submission — 140937671
Luckily I do have another way of describing, or dare I say it, a different solution that is simpler.
I would love to hear it, I suspect I overkilled the problem since it took me 30-40 mins to implement it in contrast to the 10 mins it took me to arrive at the idea.
Well, I guarantee it to be simple. My Pascal code is only 50+ lines.
The, ahh, benefit of this solution is the ability to use WolframAlpha to take away all remaining specks of brainpower needed to solve the problem.
See: formula
Well I do have something similar:
First, observe that the timesteps that cleaning is possible are cyclic, with cycle length no more than $$$4max(m,n)$$$.
Then, find the cycle, suppose it's $$$p_1, \cdots, p_c$$$.
Calculate the gap between neighboring points to get $$$g_1, \cdots, g_{c-1}, g_c=L-p_c$$$.
Then the answer is $$$[g_1 + g_2(1-p) + g_3(1-p)^2 + \cdots + g_c(1-p)^c] [1+(1-p)^c+(1-p)^{2c}+\cdots]$$$
And the latter term equals $$$\frac{1}{1-(1-p)^c}$$$.
That's where I stuck, cause I dont know how to simplify the fraction...
Aww I realized that the irreducible fraction is actually irrelevant.
Since if u calculate $$$\frac{a}{b}=\frac{tu}{tv}$$$, where $$$gcd(u,v)=1$$$, then $$$ab^{-1} = tu(tv)^{-1}=uv^{-1}$$$ mod P.
Sad that I didn't get this during contest...
Does Cycle always exist? I am getting MLE for Test case 10 because of the infinite loop :(
My submission
My bad :( , in above submission my cycle finding code is wrong,
Here is my AC submission
Here is my solution. Let's build the graph where every node is a tuple
(row, col, row_direction, col_direction)
. Obviously, this is a graph consisting of only one cycle and every node has only one outgoing edge. Each edge will have some weight indicating the probability of taking that edge. If a node is in the same row or column as the goal, its outgoing edge has weight $$$1 - p$$$, otherwise it has weight $$$1$$$.Now, let's say the cycle has length $$$L$$$ and the product of its edges's weights is $$$P$$$. Let's also define $$$length(u)$$$ as the length (number of edges) of the path from the starting node to the node $$$u$$$, and $$$prod(u)$$$ as the product of the edges's weights on the path from the starting node to the node $$$u$$$.
Now, let's say our trip finishes at the node $$$u$$$, after traversing the cycle completely $$$k$$$ times. Then, the probability of such outcome is $$$P^k \cdot prod(u)$$$, and therefore the expected time to reach such outcome is $$$P^k \cdot prod(u) \cdot (L \cdot k + length(u))$$$.
Therefore, for every node $$$u$$$ in the cycle, the expected time of finishing there is:
Now, for every node $u$ not in the cycle, the expected time of finishing there is just $$$prod(u)\cdot length(u)$$$ — somehow, I forgot about this case when I was coding the problem, and still it passed the test cases, (it seems that the graph is always a cycle).
UPD: Thanks to PoIar_ for sharing a simple proof of why the graph is a simple cycle.
Now, for every node $$$u$$$ that is on the same row or column as the goal, we add the above formulas (depending if it's on the cycle or not) multiplied by $$$p$$$ (the probability of cleaning those row and column).
The graph is always a cycle indeed. Let $$$ u_1, u_2, ..., u_k, ... $$$ the sequence of nodes you traversed in the graph where $$$ u_1 $$$ is the node where you started and $$$ u_k $$$ the first repeated node (where you detected the cycle).
If $$$ u_k \neq u_1 $$$ then there are at least two nodes that lead to $$$ u_k $$$. Now if you think about the graph of the reversed moves, it is also a functional graph with the reversed edges. So a node with indegree $$$ x > 1 $$$ in the original graph implies a node with outdegree $$$ x > 1 $$$ in the reversed graph, which is functional. That is a contradiction.
Excellent. Thank you so much!
I don't think it's appropriate to prevent a lot of gifs in the statements. It took me about two minutes to load all things in problem A and D.
I think E is a bit boring. Almost immediately after I saw the problems I came up with the solutions, all that remained was to implement them.
Anyway, thank you for a very well prepared contest! I enjoyed the problems, especially the cool pictures in problem A and D, just the waiting time for the statements to load is really unpleasant xD
Can somebody share the references to calculate the irreducible fraction in general for the problems in which the answer is a fraction?
You calculate everything modulo $$$10^9 + 7$$$ (or whatever) and if you need to divide any time in your algorithm, just use Fermat's little theorem (so to calculate $$$\frac{a}{b}$$$ you calculate instead $$$ab^{10^9 + 5}$$$). The "irreducible" part doesn't really matter.
speed forces again and again and again :(
Can anyone please explain to me his/her Problem C solution? I made 4-5 unsolvable equations and tried solving them for 1.5 hours only to find that they can't be solved (T~T).
Do a binary search on the answer.
Let's do a binary search. We need to check if we can operate so that each pile of stones has at least $$$mid$$$ stones. Notice that if we traverse the pile of stones by their index, from largest to smallest, we can know how many stones can be removed from the pile at most. So we can just greedily move the stone forward.
Note that the number of stones that can be moved forward in the $$$i$$$-th pile cannot exceed the number of stones in the initial pile, so you need to update $$$d_i \leftarrow \min(d_i, a_i)$$$. The total time complexity will be $$$O(n \log V)$$$.
Submission: https://mirror.codeforces.com/contest/1623/submission/140945479
I was wondering if moving forward from 3 to n while checking for possibility feasible?
Use binary search.
Suppose you have a function f and it’s inverse f’. Suppose computing f is straightforward and easy but f’ is tough and you want to compute f’(x). Then sometimes it is easier to search for y = f’(x) such that f(y) = x.
Let us take an example for computing cube root of x. It is straightforward and easier to search for a number y such that y^3 = x than to compute x^(1/3).
I hope it helps.
Can somebody help me to find out a missing edge case for my first problem's solution?
while(t>0) { int n,m, rb, cb, rd, cd; int dr=1,dc=1,time=0; cin>>n>>m>>rb>>cb>>rd>>cd;
you must check for min(cd-cb, 2*(n-rb)+rb-rd)) in the case where cb<cd and likewise when rb<rd
Each case should have some sort of min calculation. For example, in the (cb < cd) else case, you should still be checking (2*(n-rb)+rb-rd).
10 10 9 1 8 10 try this
You have the right idea, but you're not considering the case when the robot "bounces" on the horizontal side, and reaches the line of the dirty cell before reaching the column
As a side note,
2*(m-cb)+cb-cd
could be simplified to2*m-cb-cd
Any readable solution for B? Please help! :))
i simulated all the process using recursion, you can go check it out
Consider the interval $$$[1, n]$$$, and let's say Bob broke it in point $$$d$$$. If $$$d > 1$$$, then somewhere in the process the interval $$$[1, d-1]$$$ was chosen. Let's consider all intervals that start at $$$1$$$, and let $$$x$$$ be the largest index such that $$$[1, x]$$$ was chosen. Notice that no interval other than $$$[1, n]$$$ can contain $$$[1, d-1]$$$, and thus, we have that $$$x = d-1$$$. If $$$d = 1$$$, then the only interval that starts at $$$1$$$ is $$$[1, n]$$$.
Implementation:
I preprocessed a vector of sets
ends
, such thatends[i]
is the set of all $$$x$$$ such that $$$[i, x]$$$ was chosen. I then sort intervals by their respective lengths, and process them in order. When processing the interval $$$[l, r]$$$, I remove $$$r$$$ from theends[l]
set, and see if the set is empty. If the set is empty, then $$$d = l$$$. Otherwise, $$$d$$$ is the largest number in the setYes, i got it.... I implemented my approach only and got it after contest....Ughhh... I wish i did this earlier ;((((((((( Thanks by the way your solution is quite good and understandable! Nice
here is my solution
// ignore — a wrong test case example
Why did you remove your test case? Looks legit to me.
Because this is an invalid test case. I understood the problem statement incorrectly. Discussed this here: https://mirror.codeforces.com/blog/entry/98385?#comment-872273
Video Solutions for A,B,C in case you are interested.
Personally, I think 5 problems is not enough to form a contest. Since there are too few problem, it will always happen that it is unbalanced, and there is a huge difficulty gap between two problems. Codeforces will become Speedforces, if you are not fast enough, or even bad internet, you are finished.
For example, problem C is expert level problem, and problem D and E are master and grandmaster level. Solving 3 problems will make the ranking ranges from 300 to over 2000, and the rating will make very huge difference.
A balanced div 2 contest should at least have 6 problems with the following:
A: newbie level (800-1000),
B: newbie or pupil level (1000-1300),
C: specialist or expert level (1400-1700)
D: expert or candidate master level (1600-2000)
E: master or grandmaster level (2100-2500)
F: grandmaster level above. (>=2500).
There used to be another problem, but there was a problem with constant optimization solutions getting accepted, so it had to be scrapped.
To be fair the intended solution is still 2-3 time faster compared to your solution with the latest constraints. But the thing is, I NEED to support JaVa, which is very painful to optimize. And, the Java solution still works pretty fast on my machine. I don't really know how come it ran a lot slower on Polygon.
Agree, as a 1900 level participant, I feel painful as I spent 1 hour getting the correct formula for problem D and realized I had no time to code it.
Problem B: Any idea why this test
gets
Validator 'validator.exe' returns exit code 3 [FAIL The given ranges are not from a valid game (test case 1)]
For n=2 there must be 1 2 range since set start from (1,n)
weird. Hm. Seems like I do not understand something in this problem. Could you please explain why this test case fails with the same error?
Ohhh. Now I get it. We literally should work with segments and cannot split them other than by Bob's actions.
I solved a different problem, but my solution happened to work on this one as well XD
instead of 1 1 or 2 2 it should contain 1 2 or 2 3. I think I misunderstood the problem as well during the contest, but now reading it back I get it clearly.
If i simplify the problem statement then initially you have range (1,n)
On each step take 1 number d from range and break the range into two ranges.
1 range contains number smaller than d and other contain numbers greater than d.
Now in your test case initially you have (1,3). If you break it at point d=1 then set will contain (2,3). On next step remove either 2 or 3. Other remaining range will be (3,3) or (2,2) respectively.
If you break at d=2 then set will contain (1,1) and (3,3)
If you break at d=3 the set will contain (1,2). On next step if you take d=1 the remaining range (2,2), other wise (1,1)
But test case you made is possible in no way
Its missing this tc: 1 2
why B is easier than Problem A
Both are text understanding problems in first place, so it is arbitrary which one feels more or less complecated.
And reading the problem A statement is so much harder because of these animated pictures flashing into your face. I ended up skipping the contest exactly because of this single reason. I'm not epileptic, but it still felt very uncomfortable.
I had problems distinguishing dr and rd, as well as dc and cd from each other.
Tle in test 6 in B (BFS) Can someone help... Link:- https://mirror.codeforces.com/contest/1623/submission/140934881
use binsearch bro
Video editorial for anyone looking (Problems A to C)
Hello! I found some perplexing behavior with the online judge:
Problem: A
Issue:
the same code gets AC with pypy3/python3 and TLE with pypy3-64
with a small alteration (no difference logic-wise) gets AC with pypy3-64
Submission details: https://mirror.codeforces.com/contest/1623/submission/140947850
Could someone enlighten me what's going on here? Could an admin help look into it if it's some interpreter issue?
I have tested with some other submissions from ao35612:
TLE with pypy3-64: https://mirror.codeforces.com/contest/1623/submission/140938214
AC (much less than TL) with pypy3: https://mirror.codeforces.com/contest/1623/submission/140948424
and n0k:
TLE with pypy3-64: https://mirror.codeforces.com/contest/1623/submission/140916043
AC (much less than TL) with pypy3: https://mirror.codeforces.com/contest/1623/submission/140948345
geranazavr555 or anyone can advise on this issue for python users?
Nice, my simple solution for A got TL:
https://mirror.codeforces.com/contest/1623/submission/140913342
https://mirror.codeforces.com/problemset/customtest can be used to do some experiments. It looks like just your import directives from the top of your source file alone waste 794 ms of the execution time. A much leaner template without excessive imports for the stuff that you even don't need in that particular solution may help. But it's a good question whether pypy3-64 really needs to spend that much time on processing imports.
Edit: Looks like all the damage comes from
import unittest.mock
. Commenting out this single line fixes performance problems. What is the purpose of having this particular import?I think this issue is quite different from the issue I showed above. The above issue may have hidden impacts on many python users.
Thanks for the contest! Here are my thoughts(as I have only recently "unlocked" unrated Div2s):
I thought that this problem A was rather unnecessary, and the slow-loading GIFs + long statement did not make the experience very enjoyable for me. Still, kudos to you for putting in the work of making these GIFs!
No real thoughts, felt like a filler problem.
I enjoyed this problem :) Nice binary search (the way I solved it), though I do believe that the statements in the round could have been a little better, but maybe that's just me!
Brilliant problem! I solved it by considering the path as a functional graph, and even though I have dealt with the resulting equations multiple times, I really enjoyed the way it was used!
Did not get an opportunity to attempt this in-contest. I look forward to upsolving it!
Wow! Thank you for participating and feedback! I really appreciate it. <3
For problem D, after counting the cycle with all possible step number, how to use these information to get the result of the problem(in a brilliant way)? I guess I can force each of them have same denominator and doing the mod operation to every one, but I wonder if there's some brilliant way to do these thing?
Any idea?
Here was my solution:
We only ever have the possibility of cleaning the target, if we are at the same row or column as the target. When we start traversing the matrix as given in the statement, we end up with a graph which has a chain of vertices (possibly of size 0) followed by a cycle.
For the chain and the cycle, let's store the number of moves we took to reach a vertex $$$v$$$, for all vertices $$$v$$$ such that $$$v$$$ is at either the same row or same column (or both) as the target. I call these vertices "potential vertices".
Say the chain had some potential vertices $$$c_1, c_2, \dots c_k$$$ at distances(moves) $$$d_1, d_2 \dots d_k$$$.
Also, say the cycle had potential vertices $$$C_1, C_2 \dots C_K$$$ at distances $$$D_1, D_2 \dots D_K$$$.
Let us consider only the cycle first. Once we have entered the cycle, the expected time to clean the target is:
Now, the total expected time:
Actually, there is always no chain before the cycle. This is because after lcm(2 * n — 2, 2 * m — 2) moves you will be in the starting vertex.
Ah yes, I complicated it unnecessarily yet again! Thanks!
Thanks for this super nice round !
IMO the problems were all interesting and educative. I hope to see more rounds from Vietnam :)
Here are my thoughts about each problem
well I guess it's cool to have a problem related to the D because it saves some implementation time ?
Problems B are often very unbalanced (i.e to easy or to hard) but it seems this one has the right difficulty !
This may seems stupid but I really liked the fact that the greedy algorithm needs to start from the end. It felt like a more "unique" problem to me
I couldn't solve (I thought you could go through the cycle any number of times so the expected value will be an infinite sum) but it appears this sum can be simplified ! I think this problem is really educative and the small number of AC shows that not a lot of people knows about the trick involved.
I found the solution at the end so I couldn't implement it in time but I loved the problem!
PS: The gif in problem A was incredible !! darkkcyan did you use the tool from 3blue1brown to make it ?
yeah in prob C dumb me always thought of a solution preceding "3 --> n" but the key was to start from the end.
Usually when you are stuck on a problem it's a good idea to try a different approach and change the way you are viewing the problem, now you'll know that you need to try thinking backward :p
Thank you so much for participating and feedback! Yes, the library is called Manim. I will also public the source code for animation in the editorial.
thanks!! I hope that more problemsetters will do the same kind of animations in the future
Video tutorial b:https://www.youtube.com/watch?v=AiP4D3vyovQ
Problem C: Is there a way to solve this problem by following the order "3 --> n".
What?
Hey, ive solved c with binary search but was wondering whether this would work as well:
First we find sufix that has minimum average value. Lets say that this value is some k.
Does it stand that the answer is k, k-1 or k-2? Or sth similar?
Okay, definitely not — 1rst case scenario
Will the first to solve every problem be published? darkkcyan
Video Editorial for Problem C: Balanced Stone Heaps
Video Editorial for Problem B: Game on Ranges
I saw some comment explain how to use binary search to solve the Problem C. I encounted same kind of the problem but I still cannot solve it =(
step 1. function "check" to answer the question, is it possible to get the minimum value M for the source array. check it in one pass of the array from last elem to first
step 2. get a estimate for the minimum and maximum of M (minimum is min elem of source array, maximum is min(a[i] + a[i+1]/3 + a[i+2]/3*2)
step 3. binary search — check with M=(min + max)/2. if true, move min, if false, move max
An important note : When you see a problem that asks you to minimize the maximum value of something or maximize the minimum value of something then Binary Search absolutely works.
based on latest contests, binary search will be in mediun task with 90% propability)
More generally, if you can show the monotone of the function that you are checking (that is, before some value, the checking function returns
false
, and after that, it returnstrue
), then you can always do binary searching. There are problems that ask to maximize the minimum (or minimize the maximum) that do not involve binary search, especially when the function is not monotonous.When will rating be updated?
blease giv problems with shorter statement O_o
I hope rating will be updated before today's contest
Lmaooo
I didnt observed there was animated test case until I saw this meme
And did you know, there is also animated editorial :catthink:
unrated?
It seems to be unrated, cause I opened my unrated contest section at my profile and I found it at there
It's not, Any new contest you join will be found in unrated till rating changes occur (i.e : we still don't know) (but it will possibly be rated)
thanks
You are welcome :)
The Update time is unusual, too :(.
was this rated?
The time has come when "is it rated?" gets upvotes.
Sorry for the noob question, is this a unrated contest or do the results take time to reflect in the profile?
The similarity that you found between huddai/140930801 submission and ProgrammatorZihad/140928467 submission is completely coincident. I think the similarity between his debugging template and mine causes you to suspicious about us. But I collect the template from the internet (maybe from a codeforces blog) and I think he also collects the debugging template from the same source. Would you mind considering this matter?
the round became unrated for me because they found similarities between my solution 140930801 for the problem 1623C with ProgrammatorZihad/140928467. But I think they have done something wrong. I didn't use any third-party information(without template) for my submission.
I just want to say that I enjoyed the C problem :)