Hi everyone! I'm glad to invite all of you to participate in Codeforces Round 574 (Div. 2) which will take a place in Jul/17/2019 17:35 (Moscow time).
This round is based on SIS team contest. You will be given 6 problems and 2 hours to solve them. This round will be rated for Div. 2 participants. In other words, this round will be rated for the participants with rating lower than 2100. As usual, participants from the first division are welcome to join out of competition.
Problems was invented and prepared by budalnik, Kurpilyansky, meshanya, tsarn, sava-cska, ima_ima_go and craborac. I am just a coordinator of this round, I made a small amount of work such as English translations and editorials. I want to thank Mikhail MikeMirzayanov Mirzayanov for amazing systems Codeforces and Polygon, all authors of this great contest, KAN and cdkrot for help with difficulties estimating and choosing the problems and my dear friend Ivan BledDest Androsov for help with round preparation!
Good luck everyone and see only green system testing messages! :)
UPD: The scoring is 500 — 1000 — 1500 — (1000+1500) — 3000 — 3500.
UPD2: I would like to thank testers galloska, NatInTheHat and AlexPop28 for help and advices about the round!
UPD3: Editorial is published!
It is usually a good contest if vovuh is a coordinator. Good luck
CF574
Why some people participate out of competition even though their raiting is < 2100?![](/predownloaded/14/ad/14ad83d6c8e2f9ab946f2f2576a8ed62829955b6.jpg)
It will be fixed.
sir i submitted solution when 20-30 seconds remaining for problem D1 and D2 ,but it's not showing into mysubmissions please look into it.. i am on a very good broadband network, submit button was also working(not inactive) at that time. how it's possible??
I hope to become cyan again.
I hope to become white after this contest.
I hope to become blue finally. :D
I see people hoping to improve their colors (ratings). But I hope to have no WS, more ACs and a lot of fun :)
Clashes with topcoder SRM 763!
Some codeforces round will delay the start.I hope this round will not be like this.
I'm noob so i wanna know what's the difference between div 2 and div 1 :D thanks
Generally,div.1 is harder than div.2
div.2 C=div.1 A
div.2 D=div.1 B ....
Obviously.
thank you bro
There are three divisions (the more digit the easier problems):
I'm sorry that I can take place.
you're sorry that you can take place!!!!???? Hey everybody, I'm sorry that I'm alive lol :P
If i can solve Div 2 A,B,C regularly,can i ever become a specialist?
Absolutely yes!
And if you are lucky enough,you can even become an expert.
What is SIS contest?
I think Summer informatics School like Codeforces Round 530 (Div. 2).
SIS is for russian ЛКШ. It's a summer training camp in Russia
What does it mean to coordinate a round ? What does the coordinator do ?
Coordinator finds mistakes in problems statements
Will the pretests of problems in this contest be strong, like those in Educational Codeforces Round 68?
I agree that Educational Codeforces Round 68 had very strong pretests, which made hacking very difficult.
Oh, you are strong enough, and you won't be afraid of the strong pretests.
What will scoring distribution be like?
Please let me see my repay! ->Codeforces Round #574 (Div. 2)
This round clashes with Codeforces Round #574.
i will be cyan today....waiting for div3 vovuh (^.^)
i will be master today....waiting for div1 vovuh (^.^)
Challenge accepted :)
What is SIS team contest ?? Can't find any relevant info about it on dd
SIS stands for summer computer school, so SIS team contest means team contest held in SIS.
500 — 1000 — 1500 — (1000+1500) — 3000 — 3500
Is it even div.2 ???
Easy div1 :)
Just one more div2D and this would've been a beautiful round with 2 divisions.
GOOd luc to all ! .. xd hope rating get
No Hackforces or Queueforces please!
Gray here I come!
rating count begins from 1500 , if you perform well ,you can directly reach blue after first round, else you would be green
“ Else you would be green ”. You forgot one else if that he might be cyan if he writes contest not very bad)
Welcome to FairyForces :P
That boy reminds me of Jace Beleren
Sorry to say, but A is much to much text. That is not very motivating.
I didn't even understand the problem. Why the english is hard
Nobody :
Me:
(5 mins before the contest): watching hunter_x_hunter
(contest begins) : reading problem-A...
(5 mins in contest) : still reading problem-A......
(10 mins in contest) : (yawning) still reading-A.........
(15 mins in contest) : watching hunter_x_hunter again
is there someone else too or only me.
till 20 min reading problem a.
solved b in 5.
again reading a for another 10.
solved c .
again reading a.
solved d1.
now still reading a...
basically A ruined my mood .. :( .. what the question is saying. at one moment i thought of shut down and play pubg but b c d1 were easy ...
&& also share approaches for d2 and e after the contest.
Thanks.
Exactly .... B should have been A , A question is supposed to be cakewalk right and I wasn't able to understand what it was saying for the first 10 mins ....
I think D2 worth more points. D1:750 D2:1750 would be better.
Maybe there isn't too much difference if U think a lot about them:)
F: another problem that Wikipedia makes a difference
So it means we can reduce the problem to querying the number of different directions of the directed arrows in a certain range. Didn't figure out this until the last minute of the contest.
Woah, how to solve E? Is it some observation on the recurrence, or simply data structures? :O
data structures
Wow, really? I tried Seg2d but the time is too low. I tried Sparse Table 2d but the memory is too low... Which data structure have you used?
I used a 2D Deque
Do you mean a 2D monotone queue?
I use Sparse Table and AC
You shouldn't save all powers of 2 in your sparse table, save just 2 greatest
though save all powers of 2 is also OK look at mine http://codeforces.com/contest/1195/submission/57270378
I had 2d sparse table in my solution, so 3000*3000*13 is too much)
no only 3000*13 and reuse it
Link
Pretty much the same as https://discuss.codechef.com/t/chsqarr-editorial/12662
I think it is using trees, but I failed to pass it in time.
Argh, deque. The tutorial is everywhere, but it's not that hard to not figure out, so just blame myself.
Thanks abhayps! ;)
and only O(n*m*log(n+m))
In fact only use Sparse Table can solve it. My submission http://codeforces.com/contest/1195/submission/57270378
Spoiler E?
For E, why doesn't a segtree solution pass?
Simply too costly, keep in mind that $$$n$$$ and $$$m$$$ may both reach $$$3000$$$.
Do I have to drop two logs?
Even one additional log into the $$$nm$$$ will cause TLE immediately. I tried.
The proof of the pudding is in the eating. Thanks a lot.
Best solution (based on
std::multiset
) withO(nm log(n + m))
asymptotic 57272696Just
new
/delete
optimisation with small test generation analysis (weak test cases)but not at the contest time...
UPD: This is just an example of how to reduce the execution time of a program.
My solution using
std::priority_queue
has one $$$\log$$$ in its time complexity. Some other solutions with $$$\log$$$ also passed system test.I'm on the first page of fastest solutions with $$$O(nmlog(nm))$$$... Edit: my runtime increased by about 20% after systests so this statement is no longer true. It's still 420 ms though.
Can anyone share how to solve D1? I bruteforced it and got tle in tc7.
Also A took me so much time to solve like 3*(time req for B). It was really demotivating :(
-First i solved examples on paper, then recognized pattern. Result=summation(f(a[i],a[i])*n
Wow! Was it that simple.
My solution to D1 is:
I didn't get a solution for D2. I think the same process should work, but step 1 is more difficult.
How to solve D2 ?
For $$$f(x, a)$$$ and $$$f(x, b)$$$, if $$$a$$$ and $$$b$$$ have the same number of digits, the effect of $$$x$$$ on the answer is always the same. The same holds for $$$f(a, x)$$$ and $$$f(b, x)$$$. In addition, if $$$a$$$ has at least the same amount of digit as $$$x$$$, the effect of $$$x$$$ on answer is always the same. We only need to store the frequency of number of digits.
The contribution of $$$x$$$ would be like follows (take $$$x=1234567$$$):
$$$12345670 -> 123456070 -> 1234506070 -> ... -> 10203040506070$$$ if it is $$$f(x, a)$$$.
$$$1234567 -> 12345607 -> 123450607 -> ... -> 1020304050607$$$ if it is $$$f(a, x)$$$.
$$$a$$$ has number of digits $$$1 -> 2 -> ... -> numberOfDigitsOfx$$$.
To insert a zero between the digits, you can just use the *, /, % operators.
Problem D: So the digit combining function helped the students find the coordinates of the treasure?
Where am i wrong.Can someone please help? For C problem https://codeforces.com/contest/1195/submission/57227259
change int to long long
Such a silly mistake. Spent 45 mins trying to find the error. So sad.
typedef int long long;
Why didn't you send a single announcement that you updated problem B statement? I didn't refresh and wasted a lot of time with it.
Nice round! I solved two problem but didn't have idea of problem C. Does someone teach me how to do?
-I solved with Dynamic Programming. for (i=1;i<=n;i++) { dn1[i]=max(dn1[i-1],a[i]+dn2[i-1]); dn2[i]=max(dn2[i-1],b[i]+dn1[i-1]); } cout<<max(dn1[n],dn2[n])<<endl;
The main idea is DP. Let dp[i][0] be the best sum if we only take players up to position i and take the player in the top row at position i. dp[i][1] is defined similarly, except we take the player in the bottom row at position i. dp[i][2] is also similar, except we take no player in position i. We can then fill this dp table in O(N) time, as the transitions are relatively simple.
simply 2 variables would have been enough i think?
Yes
use dp. let dp[i][j] be the max sum u can take till column i and u choose jth row {0 , 1} in current column. now transition will be either from i-1 or from i-2 because no point in skipping 2 elements.
I don't get the exact logic of "There's no point in skipping 2 elements". I think I can get a feel that at any state we have two paths to go — one from taking just next element and the other is from taking next to next element but I can't prove it. I recurse for all the states with memoization but got TLE only because your logic works but I couldn't prove why?
prabhat7298 there is nothing to prove in it.
take this example :
1 2 3 7
5 6 8 9
taking index — 1 based.
suppose we are at column 4, and we choose element from row 1 that is 7. now we must choose a previous element from row 2. suppose u skip 2 elements and choose 5 from 2nd row. now to choose 7 u can go through 5 -- 2 -- 8 -- 7 . since the numbers are positive we will only add +ve numbers to our answer. if we skip two elements we can always form a ziz zag path. so it would be optimal for us to not skip 2 elements.
Thanks you guys, I will think how to do it with your tutoral. Hope me I will get accept :D
You can refer to my submission here. It is an easy application of dp
I'm so sad if just 3 minutes I could've solved D2 ugh stupid bug lost 30 more rate
Edit : it was WA lol I'll never assume my solution is right unless I see the fukin accepted
After lot of searching, I found problem C at https://www.geeksforgeeks.org/maximum-sum-from-three-arrays-such-that-picking-elements-consecutively-from-same-is-not-allowed/ only to find out the code does't give correct output on pretest 2. Tried to fix it, failed.
RIP rating.
Very good round!! First round to solve 4 problems. I usually solved 2 or 3
I think it's better to solve few harder problems, rather then wasting time implementing easy ones. I haven't liked it -_-
Agreed
Is it possible to solve B mathematically? To solve this system of equations:
1. x(x + 1)/2 - y = k
2. x + y = n
which givesy^2 - y(2n + 3) + n^2 + n - 2k = 0
and solve this quadratic equation for y. Then, check whether y fits [0, n]. It fails on the 11th test, what have I done wrong?You can put $$$y = n - x$$$ which gives you $$$(x^2 + x)/2 + x - n = k$$$. It's quite simple to solve :)
I did it same way. If
n>=1e9
thensqrt(n)
gives not an accurate answer.How i dealt with it:
Standart C++'s
sqrt()
gives AC.Hmm, yes it does... But, anyway —
sqrt
isn't precise =)Ofc, but as condition says
It's guaranteed, that for the given n and k the answer always exists.
If it hadn't guaranteed,
sqrt()
probably would have got WA.Try to avoid using fractional types if it is possible to
For example in this problem you can iterate over x from 0 to C and try each of them to fit your formula (here C is some constant that x will never exceed e.g. 10^5)
Any other non-math solution?) my solution: 57211560
x^2 + 3x -2(n + k) = 0
its positive root will solve the problem. and it is a guarantee that it has only one positive root. so the answer will be unique. let its positive root is x, then answer will be (x * (x + 1)) / 2 -k.
can someone explain the first sample in D1 please ?!
I think that you forgot f(45,45)=4455 also makes sense.
f(12,12) = 1122 | f(12,33) = 1323 | f(12,45) = 1425 | f(33,12) = 3132 | f(33,33) = 3333 | f(33,45) = 3435 | f(45,12) = 4152 | f(45,33) = 4353 | f(45,45) = 4455
Sum these up, you'll get 26730.
Hope this explains :)
f(a[0],a[0]) + f(a[0],a[1]) + f(a[0],a[2]) + f(a[1],a[0]) + f(a[1],a[1]) + f(a[1],a[2]) + f(a[2],a[0]) + f(a[2],a[1]) + f(a[2],a[2])
Lucky me.
Problem F,why the sample input different with the image.
but the image is:
why??????
Here is an interesting approach for problems like today's E. It provides an $$$O(n)$$$ solution to the minimum element on all subarrays of length k problem
Link
Do this for every row with a sliding window (two pointers) of length b, and then with these results do it again for every column with a sliding window of length a (or vice-versa)
I tried it using a map, but it seems $$$O(n\cdot m\cdot logn)$$$ is too much this time :(
If I submit two correct solutions in different time, which one is scored? Latest one or first one? I miss submit D2 solution to D1...
last correct submission is considered.
OMG... It's unfair
Why is the TL of E so tight? Even O(n * m * log(m)) solution is not passing the time limit :(
The problem E.aka TLE :D
In my case, O(nmlogn) was accepted by 500ms. I used efficient segment tree. I saw your solution, it was O(nmlog(nm)) and set/map have much overheads.
I had the same problem. After dozens of attempts to push O(n*m*log(2)), I decided to write something else. And finally, i wrote solution with sparse table. In my implementation queries were with fixed size, so i could answer them with O(1) time. But anyway Sparse table uses O(n*m*log(m)) precalc, but this is much faster then segment tree or other structure.
Wow, another ImplementationForces round, so cool (yes!)
Same code during contest:
ljc2002 — https://codeforces.com/contest/1195/submission/57239042
ChthollyTree — https://codeforces.com/contest/1195/submission/57235611
deleting the comment lines and thinking that it will be missed out from the codeforces users :D:
It definitely missed the plagiarism check though.
how the system did not detect it? it is kinda weird
MikeMirzayanov Please look into this.
Both from Hangzhou, China. Coincidence? I don't think so ...
???
I think I don't give this guy my code.
Anyway,I find the similar problem of this round's E
Might he use my code by the similar problem.
So Why [user:ljc2002]not skipped?
hello . I'm ljc2002 and I want to explain why my code is very similar to yours.
The problem E may be a combination of two subproblems(the "sliding window" ,滑动窗口)。But, I completely copied the solution to this topic into this question. However,the author of the problem I referenced participated in the competition again.So it may led to this misunderstanding.
I’m terribly sorry about this thing. I hope to get your understanding.
I emphasize one point,the code of ours is done by ourselves.And,there is no any communication in the examination.
大家好,我是ljc2002,我想和大家(特别是对ChthollyTree同学)解释一下这次事件的原因。
problem E是由两次的"滑动窗口"组合而来的,但是我使用了某篇题解的代码来解决这个问题,但是,这篇题解的作者可能也参加了这个比赛,所以就导致了这样的误会。
我对ChthollyTree同学感到非常抱歉,并且希望得到他的谅解。
我指出一点,两道题目的代码是由我们两个自己分别独立,完成的。不存在考场上的交流
复用已有代码是符合规范的,没必要道歉。
I believe that ljc2002 can solve problem by himself.
In round #574 (div 2), problem D1 I had submitted my solution with 10-20 seconds remaining and it was in the queue for verdict but suddenly the contest was over and I was redirected to the home page of contest. Please look into the problem.
editorial?
Idea for the problem D1?
Observe that for each digit of each number, you can predict what position it would occupy in the functional output. For ex., if the numbers are
22 34
thenf(22,34) = 2324
andf(34,22) = 3242
. So, the ith digit in, say,x
would be the2*ith
or the(2*i + 1)th
digit in the functional output. So, simply iterate over the 10's expansion of each number and add to anans
variable the value that each digit in the expansion would occupy in the output.To complete the example above, you'd have
s=(4*(10^0)+4*(10^1))+(3*(10^0)+3*(10^1))
from34
for each number it is going to be paired with. Each number will be paired withn
numbers (including itself), so, you'd haveans+=(n*s)
for34
. Proceed similarly for each number in the input array.My submission: http://codeforces.com/contest/1195/submission/57225770
What about d2. How to solve it.
It's very similar. You just have to be careful about the weights in the 10's expansion that you assign to the longer number.
For this, my approach was to maintain a frequency array having
a[i]
as the number of elements with lengthi
.Now, for each number in your input array, traverse its 10's expansion. If you're at the
ith
digit then surely, all numbers with>=i
digits will ensure that thisith
digit will play out similarly as in D1. Only for numbers with<i
digits, you'll have to figure out the 10's expansion weights.For ex.,
f(12,3456) = 341526
andf(3456,12) = 345162
. Observe how for the lowermost 2 digits, this case was similar to the case for D1, ie.f(12,56)
andf(56,12)
. You only have to be careful about the weights you assign to3
and4
. You should be able to arrive at an equation for the weights in terms of thelen(a[i])
andi
. Think about it.My submission: http://codeforces.com/contest/1195/submission/57237562
during 10's expansion in both d1 and d2, will there be an issue of carry generated?
It's always taken care of on its own. For ex., when you're doing
98+76
, you're essentially doing(9*10)+(8*1)+(7*10)+(6*1)
. Any generated carry will be taken into account in the calculations by itself.Editorials?
can any one explain test cases in (problem D1) >> thanks ..
3
12 33 45
you need to calculate element's sum of this
f(12,12) f(12,33) f(12,45)
f(33,12) f(33,33) f(33,45)
f(45,12) f(45,33) f(45,45)
calculated values of functions:
you can present as
you can see that sum of this equals to
(1020*n + 102*n) + (3030*n + 303*n) + (4050*n + 405*n)
where n=3
or just:
f(a1,a1)*n + f(a2,a2)*n + f(a3,a3)*n
What was the correct approach for A? Many people (including myself) got WA in test 13 :/
Just store frequency of each type of drink and for any type of drink having frequency more than zero, say having frequency f, (f — f%2)/2, sets of that drink(decrease frequency by f — f%2), decrease the drink set count(originally ceil(n/2)) and after doing it for all present type of drinks, we have at max 1 drink of a particular type , so say K(not question's K) drinks are still required(Since all remaining drinks are having frequency 1) then choose to add minimum of (K, remaining sets) to the final answer, and finally that would be the answer I THINK!!!!
Nice answer, fits the style of the question ;)
It's been almost 10hrs since the contest ended. Why isn't the editorial released yet ? Isn't it prepared beforehand ?
My submission for D1 gives a WA verdict for the test
5 1000000000 1000000000 1000000000 1000000000 1000000000
. But the answer matches the expected output in my system. Any help would be appreciated. Link to my submission https://codeforces.com/contest/1195/submission/57257009Try debugging your code through 'Custom invocation' feature of Codeforces.
Where are the EDITORIALS?
can someone pls tell me where i went wrong. It is for question B,I used a function similar to binary search one and after 10 pretests I got wrong at 11th one. //
int ans(int l, int r) { if (r>=l)
{
int idx = l + (r — l) / 2; long long int o= idx*(idx+1)/2;
}
return -1;
} // the following test case gives me wrong answer. 999999994 108004280
Overflow. The right side is calculated first. (int)*(int) -> overflow.
thnk u and also bro I dont know how to solve this issue . could u pls tell me how to solve this??
"long long idx" or "1ll*idx*(idx+1)/2"
either of these things doesnt help. still getting wrong answer :(
http://ideone.com/TZUo26
yeah, i used long long unsigned int for o which gave 6 as answer for 5 0, while the answer should have been 3. when i removed 'unsigned' it somehow gave right answer and my code got accepted. thank you.
How to solve E
Consider the row and the column respectively. Let
The answer is obvious.
Now the problem is to find the minimum value of fixed-length subarrays in a sequence, and it can be solved in linear time with sliding window(or monotone queue)method.
Why is the meaning of question A so difficult? 0.0
Can anyone suggest a testcase to make this solution fail? https://codeforces.com/contest/1195/submission/57264099
You can even take look at this one! I've checked your solution for all valid inputs such that $$$N \le 10^4$$$ and It was okay (I'm not sure that there exists any counterexample).
This problem can be solved using the quadratic equation (submission).
Yeah I know the solution, just wanted to find the counter example for this. Thanks anyways :)
I don't think you will find one. The correct solution is:
(actually for valid test cases the floor function doesn't change anything).
This code does:
If we say
x =8*(k+n)
then the difference between these is:For
x>=0
we have0 < sqrt(9+x) - sqrt(1+x) < 2
so d(x) is either 0 or 1.For valid testcases x is an even number such that
9+x
is an perfect square.If
9+x
is a perfect square andx > 0
then1+x
isn't, so d(x) will be 0.In other words, the code will get the correct answer for all valid testcases, even if it does it in a slightly strange way.
Hi,
these 2 people have exact same code for D2 all they did was just rename the variables and added spaces and random ass functions which have no job in the code. Is this allowed to do so? it can't be coincidence that their code is exact same except the variable names.
BTW they from same college too.
cuber_coder 57239152
RaunaqRoxx 57235255
Sad
Cheating on codeforces is quite common. More shameful thing is that MikeMirzayanov doesn't take any serious action. I only remember one time when he responded. Otherwise he has nothing to do. But if you are red he might respond. Example when he even responded a blog asking for debugging help
I guess we should not blame anyone for that, Codeforces contest frequency is so high, all the people who are providing these for free,work very hard .Not because of money,but because they love this work.if some people cheated it's shame on them.but I want to ask why are you wasting your time .I guess codeforces have plagiarism checker it might be slow.Think it as learning platform,its not some real exam.its the platform u make mistakes and learn. Time is valuable resource invest it in right direction, try to solve hard problems instead of looking into such matters, it's for your benefit.no offense.
Will the editorial be published for this round, vovuh?
The editorial will be within one-two hours. I almost done with it. Sorry for delay.
You are really a good author and coordinator. Thank you!
following is the solution for B in O(1) time complexity:-)
How to solve F
Can anyone help me indicate why this situation happens?
GNU C++11: https://codeforces.com/contest/1195/submission/57351255
MS C++ 2017: https://codeforces.com/contest/1195/submission/57351301
They are both my submissions (in practice) for problem E (https://codeforces.com/contest/1195/problem/E) in this contest.
They are exactly the same code yet submitted with different compilers, e.g., GNU C++11 and MS C++ 2017. However, the one submitted using GNU C++11 got wrong answer with the output 0 for the first system test while got accepted if submitted using MS C++ 2017.
What wrong with my submission on test case 5 D2 problem. Thanks in advance!
https://codeforces.com/contest/1195/submission/57376447
Hard div.2(A) problem ever:)
Maybe you would like to know CF200A :D
I know this is really late but test cases for F are weak; solutions which use doubles to store atan2(example: 58176014) pass system tests even though the following test case makes them output 3 instead of 5:
Thank you! Added your test into testset to prevent accepting such solutions in the future.
guys in the problem C basketball exercise I wrote 2 recursive solutions one I wrote in each state and got accepted and the other I converted the tail recursion into a loop since theoretically this is faster BUT it GOT TLE!!!? can anyone tell me if I have something wrong in this code which increases complexity
this is the first one ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ int dfs(int i, int prev) { if (i == n) { return 0; } if (~dp[i][prev]) { return dp[i][prev]; } int ans = dfs(i + 1, 0);//skip if (prev != 1) { ans = max(ans, dfs(i + 1, 1) + team1[i]); } if (prev != 2) { ans = max(ans, dfs(i + 1, 2) + team2[i]); }
}
this is the ONE THAT GOT TLE
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ int dfs(int i, int prev) { if (i == n) { return 0; } int ans = 0; if (~dp[i][prev]) { return dp[i][prev]; }
}