Привет! В 20.12.2021 17:35 (Московское время) начнётся Codeforces Round 762 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 7-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.
Вам будет предложено 7-8 задач и 2 часа 15 минут на их решение.
Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацией нашей работы. Задачи были придуманы и написаны командой Университета ИТМО: MikeMirzayanov, MisterGu, myav, Gol_D, Aris, ibraevdmitriy, мной Vladosiya, а также студентом СГУ Brovko.
Также большое спасибо Geothermal, Rafbill, Sugar_fan, mango_lassi, hitonanode, Resende, Igorjan94, CtrlAlt, KerakTelor, FlakeLCR, MatheusMonteiro, Loolo, kocko за тестирование раунда и весьма полезные замечания.
Всем удачи!
UPD 1: Мнение тесторов про порядок задач оказалось настолько неоднородно, что нет никакой возможности быть уверенным в возрастании сложности задач в наборе. Советуем вам прочитать все задачи.
UPD 2: Если вы школьник из Саратовской области, то, пожалуйста, воздержитесь от участия в раунде. Одна из задач может оказаться вам знакома. Спасибо!
UPD 3: Разбор
Hope the round is not full of problems based on observations only, also I have a question for everyone, how are observations that are in CP problems relevant for any real life problem, cause I suck at observations, and even after solving many problems I am not getting any better, I am on the verge of quitting programming, please I need help.
Hope for a great round!
Hope the next football match doesn't have much kicking the ball, also I have a question for everyone, how is kicking the ball in football relevant for any real life problem?
Yeah, no kicking football next match, just kick the players instead :hype:
wow, no responses only downvotes, looks like people these days are only competitors not helpers :(
Maybe spend more time observing :/
But by then the train is gone :( , I guess I need to practice more
I mean, you were asking for problems to not have observations (which is the only part of the problem you have to think). Its pretty reasonable to downvote
First time, registered in Div3 as "out of competition". ^_^
GL & HF
The round will be rated for 1600- only or for all who "do not have a point of 1900 or higher in the rating" too?
If you have 1600 or more rating right now, it will be unrated for you
I have 1173 rating, still after solving 4 questions why it was showing unrated for me. Any idea?
Me too! I have only 1016 rating now. But it's still showing unrated.
Same, still not rated for me.
Was this contest unrated?
wait,they have not updated rating yet
Nope,I don't know what's wrong with CF
system testing is going on ..wait for it to get over
Can codechef and codeforces co-ordinate together and one of them shift the date for their 29th dec contest to 30th or 31st dec to avoid a clash?
I guess that will be unfair, because problems are mostly same and somebody could participate at the latter contest knowing most problems
How mostly problem can be same, i don't get it.
Good luck everyone
I hope my rating increases this time
Yeah, we need just to solve 4 tasks quickly.
quick 3, or slow 4 will also work.
how long for new ratings to get updated?
12 hour open hacking phase
more you get more you wish .this is damn true in case of rating also.
This is human nature my friend.
I think many schoolchild from the Saratov region didn't plan to participate until they see UPD2
**Hope we all get positive rank **
we all hope that but it isn't possible.
everybody can get a positive rank since nobody can be the #0th or the #-1st or lower ;)
MNNIT Insomnia has been postponed to start from 10 PM IST. Those who wanted to give the contest can now join in after CF Div3.
PS: The opinion of the testers about the order of problems turned out to be so heterogeneous.
"Read all problems".
Frequent Div.3 are love..
div3 are bliss.
How to delete this comment.
hahahahaha.....
This div.3 blued me away(づ｡◕‿‿◕｡)づ
imagine swapping n and m in D
The hardest Div3 I have ever seen before :(
.
And why ?
The problems are fairly interesting especially from D to G although F is easier than what it's position suggests
.
IMO G was easier than what it's position suggests too
why? it's quite interesting. you didn't even solve any problem.
Maybe he isn't interested in interesting questions.
Is G DSU and binary search or something else ?
exactly
I was trying to do the same maybe my checking condition is incorrect
Thanks
Edit: Found the error
Its funny how I solved 2 similar Gs before today but ended up trying to think of a BFS solution because of "minimum". I think its due to solving many BFS problems lately. Does this happen to you?
I have an intuition for Dijkstra, not sure though. LOL
Basically just finding SCCs in a fast way. Even DFS works.
you can solve it without binary search https://mirror.codeforces.com/contest/1619/submission/140094897
bestial-42-centroids Can you explain your solution, please? Always nice to see deque being used in a solution.
Yes! The first idea is that we want to have some way to know which bombs will explode when another bomb explode. Let's see the explosion process as a graph in which a bomb is connected to another if they are at distance $$$\leq K$$$ and they share some coordinate (i.e they are on the same horizontal/vertical line). Let's consider each connected component. If a bomb from a connected component explodes, then all the bombs of the component will instantly explode. It is know clear that the bomb with the smallest timer of each component will give use the time it takes to explode the whole component !
The question is now the following: how to find the components. For this let's sort all the bombs by increasing $$$x$$$ coordinates and iterate through the vector (in case of equality for $$$x$$$ we sort by increasing $$$y$$$). This way we can iterate through the bombs from left to right and for each vertical line we'll see the bombs from bottom to top. If a bomb $$$i$$$ is at the same $$$x$$$ than the bomb $$$i - 1$$$, they are on the same line and our processing order over $$$y$$$ guaranty that $$$i$$$ is the closest bomb if we walk to the top from $$$i - 1$$$. So we check if $$$i$$$ and $$$i - 1$$$ are at distance $$$\leq k$$$ and if so we add an edge between the two bombs (using a union find). We should also keep track of the minimum timer of each component.
Now we know all the bomb components and the time they take to explode. We could use binary search to end the problem but we can also use some greedy algorithm ! Let's put all of this bomb in a sorted vector (in my code it's a deque because it makes implementation easier but you can also use a vector with two pointers).
The strategy is the following: When manually exploding bombs components, we should explode the components with the biggest exploding time.
Assume we have some optimal sequence of moves such that we manually exploded a component with timer $$$a$$$ while a bomb with timer $$$b \gt a$$$ hasn't been exploded. If we explode $$$b$$$ before $$$a$$$, the answer wont increase but it may decrease as $$$a$$$ has more chances to explode automatically than $$$b$$$ due to the fact that $$$b \gt a$$$).
So the idea is to explode the component with the biggest timer and to update the time that has passed. I then use $$$pop_front$$$ to remove the bombs that exploded automatically while I exploded the biggest components manually.
I hope my explanations were clear! If you have any questions, don't hesitate to ask
My solution for G: Create a graph by connecting edges between two adjacent nodes such that either they have the same X and abs(diff(Y)) <= K or same Y and abs(diff(Y)) <= K. Each node will have maximum 4 edges. Find connected components and let the total components be T. For ith component, assign value i to all nodes in that component. Then, sort the vertices in order of increasing timer and go through them from 1 to N. At ith vertex, add its component value to a set S and update ans = min(ans, max(timer[i], T — size(S) — 1). That's it! Simple dfs.
Accepted solution: 140115861
Yeah couldn't implement since I kept trying to fix my segment tree solution to E that was getting TLE. Turns out if you use stack you can get $$$\mathcal O(n)$$$ implementation. The last few minutes of Div 3 are always a blur. :(
Couldn't think of D and went ahead to AC E instead.
binary search the alpha. if each people have at least one shop to go and at least one shop can satisfy two people or more, then that alpha is OK.
I've solved it with a greedy approach, if two persons are assigned to the same shop, the assigned friends must be the top 2 friends with maximum values for that shop, and the remaining friends are free to choose their shops.
That's exactly what I did for D :D
I think I did something similar. I calculated two values. The maximum of the second highest values for each shop, and the minimum value in each column (highest happiness any individual friend could achieve). Then I return the minimum of the two values.
Good round! I have no idea what is wrong with my code in E, its sadly. But i enjoyed this round
How to solve that D? Was able to solve till F but cant get my mid around D at all?
Binary search on answer
Oh thanks. Will try to apply that now and see if I can solve it
Ok so there are many ways to solve D but I think this is the easiest one: First, compute the shop with the maximum value of each friend.
Let's call the set of the best shops $$$B$$$
If $$$|B| \leq n - 1$$$ then the answer is the minimum of $$$B$$$ ($$$|B|$$$ denotes the size of the set $$$B$$$, i.e the number of distinct values in $$$B$$$).
else, it is obvious that $$$|B| = n$$$ because we can have at most $$$n$$$ different best shops as there are $$$n$$$ friends.
So we only need to remove one shop from $$$B$$$ to be able to buy all the gifts. This means that we need to:
— pick two friends
— assign them to the same shop (so at least one of the two friends will change it's shop)
This way we will reduce $$$|B|$$$ by one (or more) and this is the minimal move we can do so if we pick an optimal move here then it'll give some optimal answer.
So what we need to do is: — Iterate over the shop where we will place the two friends
— Pick the two friends whose joy in this shop is maximum
— Compute the changes on the answer and chmax
Here is my code: https://mirror.codeforces.com/contest/1619/submission/140072358
Thanks for the solution. I was so confused with the problem :/
np! The problem actually looked super hard/intimidating for me :c
Had similar stupid error in 4 problems... C: forgot to check if s % 100 >= 10 D: forgot to check if 1e9 is OK E: forgot the answer could be more than 32-bit integer G: when removing some debug code, deleted the line sorting the exploding time...
also think about H for 20 minutes without any idea.
Implementation Forces
Always
OMG, AC problem E 1 minute after the contest ended. I can be at rank 200. what a pity T_T
Hard luck.
How can u be at rank 200 with such a very high penalty? :| My friend solved 5 and got rank 300 (official) with much lower penalty.
How ?? The last person who solved 5 problems was ranked 28x. you should uncheck show unofficial or sth...
bug_limit_exceeded got rank 280 (nearly 300). If you solve E, your penaly must be at least 87 higher than him (347 vs 260).
I don't know why the rank on the friends list is different when I see it common standing
The common standings does not include the non-rating contestants meanwhile the friends list standing does
I think the difference is due to trusted participants
Video editorial for anyone interested
P.S: HD quality should be available in few minutes
Thanks for very nice problem set
Missed F just by a minute :(
Could any one tell me that at what conditions would we get -1(i.e impossible case) in problem C
a=1 s=20
If it works, there is a unique B that satisfies A + B = S (where plus represents the modified addition operator).
Why? Consider working in order through the indices of A and S in reverse. If the next_dig(S) >= next_dig(A), then the next required digit of B is just next_dig(B) = next_dig(S) — next_dig(A). Otherwise, we must consider the next two digits of S as the target number. If 0 <= next_two_digs(S) — next_dig(A) <= 9 then we have our next B digit. Otherwise, we fail and return -1.
If we reach the end of A and S continues, we can extend A with leading 0s to determine the remaining B digits. However, if A continues further than S, we fail and return -1.
I am making some mistake can you point it out - https://mirror.codeforces.com/contest/1619/submission/140078402
Java looks like a very long code. But have you checked it dif can go negative at the line if(dif > 9). Because I faced similar issue twice but resolved when I did if(dif > 9 or dif <= 0) c ++ kind of implementation
It's hard for me to debug by sight by I think your dif value is perhaps going below 0 and therefore you append "-1" to sb, which is later reversed. This is just a guess based on the error message at the bottom though.
I was aware of next_two_digs(S) — next_dig(A) <= 9 but missed the condition 0 <= next_two_digs(S) — next_dig(A) in the contest time.... As a consequence C was not accepted in the contest :(
Unlucky but don't lose heart. Things like this are a matter of experience — next time you will not make the same mistake: when checking if something is a digit, you will remember to check
0 <= dig <= 9.I got two WA for that and took lot of time to find that error. But it helps in debugging later tests
I dislike the weak example :)
Was the time complexity for E O(nlogn)? I had that, but I still TLE. I binary search for the element to "fill in" the gap, and I think others did as well when I click their submission. Does anyone know what part of my code is higher than O(nlogn)? https://mirror.codeforces.com/contest/1619/submission/140082257
Maybe its cuz you used unordered_map?
I changed it to vector in one of the more recent submission, still TLE:/ Shoudln't affect that much anyway, I see other solution within ~100ms while mine is over 2000ms
The issue is that lower_bound defined in algorithm library takes $$$O(n)$$$ time for non-linear containers.
You should use set.lower_bound(key) instead.
ohh thanks so much, i never even knew that!
Yeah, it immidiately AC when I changed that
O(N) dp solution:
https://mirror.codeforces.com/contest/1619/submission/140071470
well too much cheating going on , I know some may say to do hard work instead of talking about cheating but how can a newbie like me out perform cheaters who are doing better than a specialist, it is really becoming hard for us. guess we have to practice like an expert.
BinarySearchForces for me.
A really enjoyable problem set, although for a Div 3 possibly a little too hard.
I genuinely thought F < E < D. Maybe I just took a while to figure D out. On the surface it looks like quite an intimidating problem. And F my solution was so simple I was sure I must have misunderstood the question but it passed.
In F there is some severe text understanding skills necessary.
That's fair. Understanding the statement is probably more work than solving the problem.
I think people just died on D, cuz they just read it reversed, thinking n is amount shops but rather not friends.
Initially I coded a solution where you were allowed to visit M-1 shops (this is quite easy using prefix and suffix max arrays).
The N-1 version initially seemed difficult to me because I was trying to optimally choose the best N-1 shops. Once you spot that all you need is at least one shop per person and at least one shop with 2 people for a given target value, it's easy. You firstly have to spot the binary search potential (not too hard) and secondly this non-trivial observation. For a Div 3D I thought it was quite tough, even once you understand the question correctly.
True, this is what I would have done too. But kudos to the authors, samples catch this, and as a consequence, I am pretty satisfied with the quality of the samples in this contest.
I think it's a great question. Just intriguing that different people find different things difficult.
There's something psychological about it all as well. When I see that the solve numbers are into the hundreds quite early on, I know the method and/or data structure is not too complex, so I change my mindset around how to approach the problem. In this case I knew that there must be something easier than what I was trying, so I switched my efforts to figuring out what that was.
You don't actually need binary search https://mirror.codeforces.com/blog/entry/98076?#comment-869474 altough it might help in the thinking process
How was the observation non-trivial? Or is pigeonhole logic hard for a div 3D? I got the thought process pretty quickly but took a while implementing.
Applying the pigeonhole principle is trivial. Observing that it’s the correct approach (rather than, e.g., bottom up selecting the N-1 stores), is non-trivial in the most literal possible sense. And indeed since it is not the only approach, it is absolutely non-trivial.
I didn't read F because it looked long and I didn't have enough time (I lost a bunch of time on D because I swapped n and m...and I just had a hard time solving E) but I read G 5mn before the end and insta solved it so for me G < D < E :')
Could you explain your approach for F please?
In each turn, you must assign all N people to one of M tables. Suppose
R = (N % M). ThenRtables will haveX = (N / M) + 1people on them,(M - R)tables will haveY = (N / M)people on them.In the first round, assign the first
R * Xpeople to tables withXpeople (big tables), and the remaining people to tables withYpeople (small tables). Store the indexi_smallof the first person at a small table in this round.In the next round, begin your assignment of people the big tables from
i_small, and repeat the process.Why does this work? We're cycling through the guests from 1 to N in blocks of
R * X. As such, no person is ever more than 2 big tables ahead of any other.(Note that in the case
R = 0all guests are always sat at small tables).Does anyone know what I have done wrong in problem C https://mirror.codeforces.com/contest/1619/submission/140095282 Thanks a lot!
if ((y % 100 - x % 10) > 18 || (y % 100 - x % 10) < 0) { cout << "-1\n"; return; }I think first one should be > 9 instead of 18 because of single digit say if y = 22 and x = 9 it will add 13 to the value which is incorrectIt's hard for me to solve these 8 problems in 2 hours.The duration is short.
If you had that talent, you wouldn't be in division 3.
I can't solve 8 problems either...
I found code that goes against the rules. What should I do? https://mirror.codeforces.com/contest/1619/submission/140060952
What is the person even trying to do? Copied some others code and pasted those whiles?
C was so cancer :( .
In today's problem C, i submitted my code(language: c++17) during the contest at 2:02 while the contest was still running, I got runtime error on test#1 but same code runs fine on changing language to c++17(64), I also ran same code on test#1 in atcoder compiler and it worked fine there
also when I add if(v2.size()>0) before this for loop for(ll i=v2.size()-1; i>=0; i--) { v3.pb(v2[i]); }
same code got accepted but this addition shouldn't matter.
link to runtime error code: 140087080 link to accepted code: 140095620
please look into this @MikeMirzayanov @Vladosiya
vector.size() returns unsigned int, so when you do
v2.size()-1, it will not be -1, it will be out of bound for the unsigned int. And that is why you are getting runtime error. Instead you can store v2.size() in an int variable before the for loop and use that variable in the for loop.And avoid tagging Mike and other coordinators. Your doubt is not a big issue that you are tagging them :)
Just to be clear. C++ is completely ok with you subtracting 1 from an unsigned 0. But the result is
2^32 - 1(in 32 bit) or2^64 - 1(in 64 bit), which is probably is not what you wanted. But it does not directly cause the runtime error.Probably the thing that causes the runtime error is
v2[2^32 - 1].As for why you aren't getting runtime error in C++ (64 bit). The reason is that when
2^64 - 1is casted into a long long, it goes back to being a -1.Thanks for the clarification
hue hue hue
The contest was profoundly unbalanced but the problems were interesting still, thanks!
Can anybody please help me in finding what is wrong with my code for D. Any counter testcase would help.
WA on tc 2 140096931
3 3
1 2 5
5 1 2
1 4 3
Correct Answer: 3
Thanks
Why in B the solution which having the ans by formulas getting hacked??
If anyone's getting runtime error in C try defining your own stoi function rather than using the standard one I dont know why this works tho :(
long long stoi(string s) { long long p = 0; long long k = 0; for(int i=(int)s.size()-1;i>=0;i--) { p = p + (s[i] — '0') * (pow(10, k++)); } return p; }
Use
stoll().Well, I think you can use stoll to get long long int.
Hi everyone This is my first Codeforces contest and I see that now there's a hacking stage. I know you're meant to try and break other people's code but does someone know where I can find the details, please? Many thanks
I solved D with binary Search.
Simply Binary Search over the answer and check for the following two conditions :-
(1) All friends must have at least one joy value which is greater than or equal to our mid(checking for mid) value.
(2) There must exist at least one shop from which we can buy two gifts for our friends with value >= mid because we can visit at max n-1 shops because if we can buy two gifts from a single shop then simply we can visit all other shops to buy left gifts.
For more clarity look at the submission 140061439
We are checking two numbers greater than mid for any shop so let's say there exist two numbers greater than mid and all the rest conditions are also fulfilled then we are taking the answer as mid(which doesn't exist in the array) , so how are you assuring that the final answer will exist in the given 2-D array. Will the binary search cover all the cases ?
Yes it will
Suppose for a certain mid value which does not exist in the array both conditions are true
at that moment we are intializing ans to mid and changing left bound to mid+1 which means for the next value greater than mid which is present in the array ans will be true and our mid value will visit that particular once and our ans will be maximised there
I hope you understand
you can make it easier
for each store find a gift A with the largest joy and gift B with the second largest joy (max and second max in each row)
сhoose the store X with the maximum B value
for two friends, take these two gifts in the store X
for another friends take a gift with larges joy without limiting the store (max in column)
all calculation is performed in one pass O(n*m)
Can someone tell me why this solution is giving WA? https://mirror.codeforces.com/contest/1619/submission/140060676
instead of this you try
why we have to check less than 0 condition?
I checked > 9 conditions and it was giving WA but as soon as I included this it got accepted but why? why this less than 0 need to be checked?
solution without checking the less than < 0 condtion
solution with checking the less than < 0 condtion
The case when
str[0] == '0'Instead of 19 u should be using 9 since single digits is what we want
Oops I thought it's div 3 .
Problem d is so difficult to understand, how to solve it
I explained my solution in this comment :p https://mirror.codeforces.com/blog/entry/98076?#comment-869474
Great round with high quality samples (especially for problem D!) The problems where overall very interesting (it could be more balanced but I just read UPD 1 which is fixing this problem) The little bad point I can find is that problem F statement is way too long
https://mirror.codeforces.com/contest/1619/submission/140090821
can someone pls explain why I get a runtime error on case 2. My code seems to work for every test case I try.
No idea but try on your own for this test:
Most probably it is due to the line usable.back() incase your usable vector is empty In that case mex[i+1] directly becomes -1
What could be done in D if we have to visit atmost K(any arbitrary number) shops instead of n-1 ?
I believe in that case the problem becomes NP-complete. We can reduce the vertex cover problem (which is known to be NP-complete) to the problem you proposed. But first, let's assume that $$$p_{ij}$$$s can only be $$$0$$$ or $$$1$$$. Therefore, your problem becomes: are there at most $$$K$$$ shops such that we can buy $$$n$$$ gifts of joy value $$$1$$$ for each of our friends?
Now let's get back to the vertex cover problem: Given a graph $$$G(V, E)$$$ and $$$K$$$. Does $$$G$$$ have a vertex cover of size at most $$$K$$$?
To reduce vertex cover to your problem, we map each input of vertex cover to some input of your problem.
For any vertex cover input ($$$G(V, E)$$$ and $$$K$$$), you can assume that the set of vertices $$$V$$$ is the set of shops, and the set of edges $$$E$$$ is the set of your friends. We set $$$p_{ij}$$$ to be $$$1$$$ if the $$$i$$$-th vertex is connected to the $$$j$$$-th edge. Otherwise, we set it to $$$0$$$. So now, the number of shops is $$$|V|$$$, and the number of friends is $$$|E|$$$. If you can find $$$K$$$ shops from which you can buy $$$|E|$$$ gifts for each of your friends, then you have found a vertex cover of size $$$K$$$. Hence, the problem you proposed is NP-complete which almost implies that there is no polynomial algorithm to solve it.
not exactly sure what you mean, " no polynomial algorithm to solve it." I solved using binary search, thing is it does not leverages of fact of going to "n-1" shops, so you can just change to k. You can check my submission.
The issue is not with the binary search part. The issue is that when you fix some value $$$x$$$ (the midpoint of the binary search), you cannot use the same logic to "test" whether you can have the answer equal to $$$x$$$. In the original problem ($$$n-1$$$ shops), you can check that:
The same logic cannot be applied when you are restricted to up to $$$K$$$ shops. In other words, you cannot adjust condition 2 to apply to the case with $$$K$$$ shops.
Again not div.3 contest :(
Again the difference is only in format, but not in difficulty. If you don't like to make contests with rooms and hacks, pls use the format name "Educational", which is also nonsense, because any round is educational — has discussion and editorials after it.
hope to get the last 30 rates
is there any solution about this contest?
In problem "Wrong Addition"
Here is My Solution
What I did is I maintained two stacks sta for string a and sts for string s.
I inserted both the string in their respective stacks
Now as long as both the stacks are not empty I did this
Pop the first character from a let it be cha and the first character from s let it be chs and I get the cases as illustrated below
case 1: if chs>=cha then I subtracted it and inserted it in b
case 2: if chs<cha then I popped another character from s converted it into a number using stringstream and subtracted it. Now here I tested for a condition if the value which I get after subtraction is >9 then it is not possible and I return -1 else I inserted it into b
after the whole above operation, I checked if stack sts is empty or not if not empty then I popped the whole stack and I append it in front of b (here what I mean is that b is greater than a, and to do this modified addition we have to append 0 in front of a )
if there are leading 0 in b I remove it
and if stack sts is empty whereas sta is not then I return -1
Where I am getting wrong or is my approach flawed.
PS: the commented-out part in my code is two pointers approach it is also the same approach above described.
Edit: In the starting, I checked another condition if the length of s is small than a then I returned -1 because I think that length of s should be >= length of a
Edit: I got my mistake but why that mistake is happening I didnt get it In my code I have checked for val2-val1>9 but i was not checking val2-val1<0 that is why it was showing WA but as soon as I included it it got accepted. Can someone please tell me why it is relevant to check < 0 condition?
Here is my correct solution
for a = 5 and s = 4 , s-a will be less than zero and no possible value of b can be found
but if you look at my solution
in the else condition i have written this code
Expalnation for the code above: if last character of a is greater than s then i will pop one character of a and two characters from s (provided there are two characters in s if not return -1) and I will subtract the two and check for the necessary checks(be it greater than 9 or less than 0 etc) after.
here it should take care of the test case which you have shown above then why I have to write another condition for checking < 0?
PS: thanks for replying and helping.
i will pop one character of a and two characters from s (provided there are two characters in s if not return -1) -> but the two characters can be 0S (S is that digit in s ) which will be still less than A ( digit in a)
ohhhhhhhhhhhhhh ok ok now it makes sense thanks for helping out!
It was mentioned in the constraints that a < s.
take a 205 and s 904
Can someone tell me why my dp based solution failed on problem d 140078987
Please dont ignore
Sorry didnt read your code.
but,According to test2 case8.
Below test output is 5 but correct answer is 4. Maybe your code choose from 4,5 but 5 is not correct.
test2. case8: 4 2 5 2 4 10 4 8 4 2
Thank you for the contest. orz. Where's the editorial?
I think that it is too difficult to be a div3
ratings not out yet?
Usually it took like 1 — 2 hours before hacking phase off
first of all there was so much noise in comments! and secondly!!! if u dont wanna reply its fine but why so angry?
Did you misread phase off as "F*** off"? lmao.
why is it that usually div3 contests take a lot of time in testing and updating rating where as div2 contests take much lesser time?
Because after a div3 or edu round, there will be a 12-hour phase of open hacks.
why penalty even if i didn't make any wrong submission ?
Penalty is the total amount of time taken by you in minutes to solve the questions. If you had made a wrong submission, the penalty would just have been increased by 10 for each wrong submission.
vovmr , anime lover, KOVAL_ is same acc?
the 3 had almost same coding and F submitted in 1min?!
added Kireev_Andrey
Standings, UserName 3. KOVAL_, 4. titanoBEBRA, 5. imsigma, 12. Kireev_Andrey
Hi, In Problem B (Squares and Cubes), I found a direct formula to calculate the numbers. But when I implemented in Python and tested it locally, it gave wrong answer for big numbers (1e9). I used the same formula in C++ and it got accepted.
Python Submission 140133787
C++ Submission 140033550
If Problem setters hadn't given the big testcases in Example, I would have lost too much time tracking this error. How can I avoid this error. It seems to me like a floating point operation error.
You can solve it easily by noticing that when calculating roots of numbers to some power, there is always some error, the error being the root of the number is generally some number below the desired result. For eg, 1000000000 cube root of this in python will give 999.9999999999997, So for numbers till 10^9 as a limit in question, the answer is generally just the perfect cube root or some number bit smaller than our perfect answer. So to solve it, just check if we get x=int(pow(n,1/y)), than try for (x+1)*(x+1)..y times<=n or not, if it is than it means x+1 should also be taken in consideration. So, now x=pow(1000000000,1/3),int(x)=999. So after checking 1000*1000*1000<=1000000000, we will take 1000 into consideration instead of 999.
ur one line solution is good....can u please explain the last part --(ll)(sqrt(cbrt(n))
sqrt(k) and cbrt(k) are built-in functions in c++ math library. They find square root of k and cuberoot of k, respectively. if I write sqrt(cbrt(k)) , Here I'm finding 6th root of k. To Find all the square roots and Cuberoots, I am finding all the square roots first (1, 4, 9) then all cuberoots(1, 8,27..) some numbers might come in both(64, 729..) So subtracting those.
There are many people who cheat in a very stupid way. This is what they revealed to us. They solve more than 2 problems in a minute or two minutes and their level is not high at all. Please take the appropriate actions with them and please add a feature on the site to detect these cheaters.
Can anyone tell why this works https://mirror.codeforces.com/contest/1619/submission/140135847 and this does not https://mirror.codeforces.com/contest/1619/submission/140025889
in some cases pow(64000000, 1.0 / 6) == 19 you should know this and be able to correct it
But if this is the case, then it should give wrong in both the submissions
floating point digits sometimes behave unexpectedly,
in second submission (140135847) optimizer helped you — possibly the result of previous calculations was used
You can see the GCC Optimize-Options document here.
The
Ofastoption turns on-ffast-math, which includes the-fno-rounding-mathoption and violates IEEE. IEEE 754 defines 4 rounding rules, but the-fno-rounding-mathassumes that the rounding mode is roundings to the nearest. So the floating-point error will be reduced after this option is turned on.More details are in the IEEE 754 Wikipedia page and floating point math GCC Wiki page.
Hope to be helpful.
Understood
Thanks a lot.
Can you help me why am I getting MLE in this code if I uncomment the currently commented lines
https://mirror.codeforces.com/contest/1619/submission/140056266
try to avoid float number whenever you can.
In case you are looking for Video solutions.(for A-E only)
Regarding Problem C, my AC solution, this solution works fine even when accessing indices<0 from string s. I understand that accessing out of bounds need not always give a runtime error, it rather generally is unexpected behaviour. However since the solution was able to pass all the pretest and main tests, I wanted to clarify that was it all luck or is there any specific value one should expect when accessing negative indices from string (particularly -1). thanks in advance, any help is much appreciated.
why no editorials yet?? How to solve H?
feeling so happy i am getting specialist first time from this round
You get ratings????
using predictors he can see expected rating change !!
What's that?
It's a browser extension based on this website
I got a mail from codeforces that's my solution is coincides with two other participants of problem D. And yeah their solution is quite similar to mine I don't know how they got my code (I'm the one who solved it first). I also compare both the solutions using moss the plag is just 46% So maybe it is just a coincidence. I don't even know these two participants I didn't use any online compiler during the contest. Also, one of them is already an expert so for him this contest is unrated So there is no point in sharing my code with him. another thing is if I did share my code I won't be writing this comment. I really worked hard for this contest and I request you to please look into this matter and do the needful. Thanks a lot
Vladosiya MikeMirzayanov
Try to use unique template
Thanks for the suggestion. Will take care in the future.
Please give me some response MikeMirzayanov Should I wait, should I mail to someone regarding this or what should I do to prove that I am not guilty.
I got hacked and it seems that the output differs on codeforces and elsewhere. On few computers I tried to run my algorithm against algorithms made by other people and they gave the same answer.
Is it possible to know on which platform codeforces run to debug the issue? It seems that codeforces long double is not that long :D.
2 42144192 887503681 run your code on this test and compare with others code.
I tested it against the top people and got the same answer.
I already know about some inputs that do not work on codeforces but work on any other PC I have tested it on. I am trying to find why there is this difference so I know what is the problem and next time I will be more successful.
Any hints on E MEX and Increments?
Try calculating least steps needed to get atleast one occurence of i for each 0 <= i <= n. Then the solution logic is straightforward
if you know how many steps it takes to have all the values 0..k in the array ( impact_num )
and you know count of k+1 in source array ( cnt[k+1] )
then answer for k+1 will be impact_num + cnt[k+1]
it remains to calculate impact_num for the next step
if cnt[k+1] > 0, impact_num will not changed
if cnt[k+1] == 0, you must find cnt[j] > 1 where j < k+1, decrease cnt[j] and impact_num += k+1-j;
an effective structure for such a search is a stack
What is k here?
This round isnt rated?
Is it rated?
Is it rated?
ratings have been updated, congrats for expert!
Thanks!
All I needed was 1 more point. Curse that long long int on test case number 4 of question E.
F
Still waiting for the editorial :/
When will the editorials of this contest be released ?
When will the editorials of this contest be released ?
Excited for the contest, Always love the CF round.
Hungry for upvotes
How to solve H ?
How to solve F and G :)
f is construction. you need n%m players sitting on greater part of table (having more player than others). n≥2m -- means if you add layer by layer, they never intersect. like : 111100000000 , 000011110000 and so on. where series of 1's represent the player idx sitting on more greater part of table. n -- people, m — tables. n%m is the length of ones, means it is < n/2.
g is connecting the points by x than by y. (sort by any cor. say if i and i+2 connect, then i and i+1 and i+1 and i+2 also.) so just add these 2 edges. every connected component will blast at min time of each those points. store these in a vector and binary search on minimum number of moves required. Say you do 5 moves. you do not need to blast those having less than 5 seconds as minimum time. but all those having greater time than this (say # cnt). if cnt <= your_choosen_time. then it is possible else not.
--- if you do not understand wait for editorial.
Where is the editorial? Can anyone tell their logic for H ?
First, note that every element of the permutation is part of a cycle if you keep doing $$$i = p_i$$$. We have two possible approaches the first is to keep all cycles using a heavy structure like treap or splay tree, then operation 1 you basically have to cut the corresponding cycles and merge than in the correct form, and operation 2 is somewhat easy you just need the cycle size and know how to find the k'th element of a cycle and the position of a given element on its cycle complexity $$$O(nlogn)$$$. The other aproach is to every element you save the next and previous element on its cycle as well as where you ended up if how make $$$i=p_i$$$ $$$sqrt(n)$$$ times, its possible to do every update of type 1 in $$$\mathcal{O}(sqrt(n))$$$ and answer every query of type 2 in $$$\mathcal{O}(sqrt(n))$$$, you use jumps of $$$sqrt(n)$$$ size until you can't make anymore, and then you make at most $$$sqrt(n)$$$ jumps of size 1 to end up where you want, the complexity of this second approach is $$$O(n sqrt(n))$$$ and it's much easier to code.
Thank you ,i was doing it with dsu but was not come up with a solution on how to use path compression on dsu so got tle on test 13 .The above idea is great ,but do you know how to do the problem with dsu ?the main problem in using dsu is how to do path compression so it doesn't take long enough time to compute values
why my solution for c fails? please help what is it that I am missing? https://mirror.codeforces.com/contest/1619/submission/140180338
It fails on this case — 1 101 From first looks I think you have a bug in your check() function.
Editorial Please.
please help ! multiset is not working properly on codeforces it is giving wrong output, but it works fine on local (problem E)
I have never met such problem before
multiset is working properly
to solve problem E, use vector and any stack implementation (see 140107223)
why the answer of
4 4
3 1 2 7
10 3 9 9
8 1 4 7
1 7 9 3
in [problem:D] is 9 but not 7.
7 is correct answer, your submission 140233437 got WA on another test
test 22 is
4 4
7 10 3 7
10 2 4 9
6 5 1 8
9 7 10 8
correct answer is 9 and last your program find it correctly
exactly i dont know what i know Esquire MohammadParsaElahimanesh
can you help me that what happened?
Please change your user to something shorter
Such as MPE And we can call you MPE when we call this person Arpa We call ARPA How much would we like to call him ostad Amir Reza Pourkhan? Simply say that ARPA does not need a ostad or anything like that
what you think about this offer ?!
maybe someone can't understand my name, for example I don't know your name or Arpa before.
also I love my name MohammadParsaElahimanesh ;)
I guess you are MMT
YE i love your name too but you are wrong im not mmt why are you talking about?
this is can help you :
im how can fall in love with you
now
can you guess?
are you hamafzayy elmi? i can't guess something else.
Nyaharo~~