Hello, everyone! Codeforces Round #272 will be held at this local time. We're looking forward to your participation!
The problems are from dreamoon_love_AA and drazil(that's me) from Taiwan, and thanks 9mmlitswe for some discussion. Also we want to thank Zlobober and Gerald for helping us prepare the round, Delinur for translating the statement into Russian, and MikeMirzayanov for Codeforces and Polygon.
This is our first round on Codeforces, we hope you'll find it interesting! Please read all problem statements and discover what the main character dreamoon_love_AA do in those problems for he's really cute =)
Update1 Note this round will be held 1.5hrs earlier than usual Codeforces rounds, so please double check the starting time in your local time.
Update2 Score distribution!
Div2: 500-1500-1500-2000-2500
Div1: 500-1000-1500-2000-3000
Update3 The contests are over. Congratulations to the winners!
Div1:
1. Petr
2. qwer1561
3. kutengine
4. ifsmirnov
5. TankEngineer
Div2:
1. ridowan007
2. a00012025
3. xavier13540
4. v_Enhance
5. pkq2006
And standings are here:
Div1: standings
Div2: standings
Update4 Editorial can be found here. It's finished by now but it's welcome to tell me if anything can be improved!
After the rather lengthy round announcements of Round 271, Bayan Contest, Round 270, and Round 269, the age of short announcements are back. And what has dreamoon_love_AA been doing the past few contests? Trying to be another worse ?
Actually, worse began the journey to red
I heard dreamoon_love_AA said that he has some plans about it =)
Just Petr can paint his rating curve according to his wishes, noone else should try to do so.
Please, don't neglect any Coder. Every coder has a high ambition to become RED. And mind the Quote
Failure is the pillar of successDid Zlobober became a long-term problem tester as Gerald? Fact that he is no longer visible in contribution standings (as MikeMirzayanov :P) seems to confirm this.
I think you should write a warning about the unusual time of the round
Some people may miss the round if they didn't notice that.
This round will be held at CST-1:30 (1.5 hours before Codeforces Standard Time)
Let's hope for math :)!
yep he always hope for math for me I always hope for early score distribution announcement :D
I expect it will be a very Nice contest and contains various problem set
dreamoon_love_AA rank at UVA is 7 solved about 3205 problem this is his profile
http://uhunt.felix-halim.net/id/2397
I don't know other Online judges but being rank 7 on UVA is sufficient to see cool & various problem set
Doesn't being an international grandmaster (like dreamoon_love_AA was before his fall (partially on purpose)) is a sufficient proof :P?
sometimes Theorem has more than one proof :P :D
dreamoon_love_AA also solve around 1432 problems here in codeforces ( as like you i don't know others OJ number but i am pretty much sure there must be more than thousands also ) . i always wonder is problem solving is that kind of addiction to him if he won't solve 10 or more problems in a day he can't eat or sleep :D
I wonder how many problem he solved in one day. Did he sleep at night or goes to school? I was trying to see his first solved problem in uva. But now it is still loading for few minutes.
I don't think he'd go to school at night :D
A year has 365 days. His profile shows 8 years of solving. That means about a problem a day (very roughly), probably often several easy ones a day. Do you think sleep matters at all in this case? :D
Of course you are right. He is solving till 2006. At 2014 he solved about 8-15 problem some day. Of course it is easy for him after a lot of solving.
Damn. Bayan Qualification + Marathon24 + NEERC + Codeforces Round #272.
Because screw weekends
You count Bayan Qualification along with those other contests? >_>
I'd replace it with Codechef Long Challenge, it has more decent problems now.
3000 point E problem come back! Do you guys want to make a super hard problem that is even harder than Chinese IOIer's round?
I was about to say the same :). Maybe I should read E in the beginning and in case I got this coded already, paste my solution, otherwise not give it any thought :P.
what a nice contest time :)
In the div2,the second problem is 1500,I dont't think it's easy.
the third problem also 1500 , what do you think ?
I don't think it's easy,too,uha.
I agree with 12310720112 -_-
Thank you for agreeing with me,haha~
I think a newly registered guy will be on top of Div.2 contest.
I think no because newly registered guy has a Div1 contest at this time :D
Petr will win Div1.
Well, you called it O.o
Found out that I don't have a pen at home 10 minutes before the contest. Going to use Paint instead of pen!
Oh I forgot registering contest.. :<
Goodbye red color :(
Goodbye blue color :(
Goodbye green color :(
Welcome Blue color:)
Goodbye purple.
Next time I'm going right to yellow! (not really)
Goodbye green color :(
Goodbye yellow color :((
Sayonara purple!
But not today!
Goodbye Orange, hello Red :D
Goodbye Div.1 :(
Who else failed A because of long overflow
Are you happy with math problems?
C was good non maths problem >:D
Yes I am happy (yay I got B) but failed A
I don't understand why this naive code fail for pretest 5. code
I was using that for find my mistake, but I couldn't
Because (i%b) should be a divisor of (i/b).
I thought: "Problem with MOD! I'll do some hacks today!" and instalock it. After few minutes I figured out that my solution is wrong because I forgot to add some MOD...
Exactly though i didn't give the contest because I actually woke after 30 mins past the start time but definiately this is the first problem I have seen of long overflow.really tricky on this part.
how to solve B -div1 ??
Output ((6i + 1)k, (6i + 2)k, (6i + 3)k, (6i + 5)k) for all i = 0, 1, ..., n - 1. (And thus the maximum is (6n - 1)k.)
missed it completely ...thnx
Why 6i ???
why this 6*i+1 format ?? I mean a simple proof ?
See here
Basically you need three odd numbers for each set, and there are 3 odd numbers every 6 numbers.
First, divide everything by k, so now we want all numbers in each set to have pairwise GCD 1.
Note that we can only have one even number; if we have two even numbers, their GCD is even and thus not 1. So we need three odd numbers.
As it turns out, 6i + 1, 6i + 2, 6i + 3, 6i + 5 has pairwise GCD 1 for any integer i, so we might as well use it. By using all lowest values of i (namely i = 0, 1, 2, ..., n - 1), we have maximum m = 6(n - 1) + 5 = 6n - 1. Also note that since we need three odd numbers per set, we need 3n odd numbers, and if m < 6n - 1 then we don't have enough odd numbers to use. Thus m = 6n - 1.
Remember that we have divided everything by k to make the pairwise GCD 1 instead of k, so now just multiply everything by k again.
why 6 !!!
why not any other even number 4, 8, 2, anything :3 ?
You need three odd numbers (one can be even), and this happens every 6.
I wrote for each set 6i+1,6i+3,6i+5 and first even number, which is coprime with each of these 3 numbers. And each time I was choosing an odd number bigger than previous one. I've checked that the even number in each set is less than all other odd numbers. And also multiplied each number to k and m=(6n-1)k. But this solustion didn't pass. Do you know my misstake? Could you show me some test for this, in which this solution is wrong?
You read in n as k and k as n.
n comes before k in the input.
OMG I've just found it)) that is impossible misstake)) I can't believe it =D tnx
and it passed after changing n and k
92anurag was the first to ask.
Uhm, the solution is in the sample. Just use 6i + 1, 6i + 2, 6i + 3, 6i + 5 (assuming k == 1). Upper bound is easily obtained from the observation that at least 3 numbers in each set should be odd.
thnx ..got it
Nice idea, I haven't noticed this pattern in the sample. :(
What kind of sorcery is this?
math man, math!
Как С (div 2)/A (div 1) нужно было решать?
cout << (((((((a*(b-1)) % M) * 250000002) % M) * b) % M) * ((a*b + b + 2) % M)) % M;Брутфорс->ищешь закономерность. Контест — треш
Там есть формула, тупое решение за a * b, все, что нужно было сделать — сделать его умнее
Я пробегаюсь по всем k, плюсуя к результату сумму арифметической прогрессии, например.
Я сделал так же, но при чем здесь закономерность?
Я вывел формулу, полтора часа втыкая в брутфорс и переписывая его.
why wa on pretest 5 of question C. http://mirror.codeforces.com/contest/476/submission/8207485
Explanation for problem C Div2?
How are you sure that an O(b) solution with multiplication,division and mod solution will pass under 1 second? Same question to O(a) solutions also
10^7 * k operations (where k < 50) should mostly pass.
I did the same. Can you tell me why 8200906 is hacked?
You casted to double, losing precision. (Double can only hold about 53 bits of precision; with a = 109,
that you're computing needs 59 bits.)
Thank you! And also, how do you calculate how much precision it needs?
Oops, I have successfully confused myself. a = 107, not 109.
No, the problem is below that:
, thus you're computing 
. This requires 94 bits; long long only has 63 bits.
sum*i*bessentially explodes. With a = b = 107, i = 107 - 1, we haveComputing precision is simple; take the number, take its logarithm base 2, and round up. That's the number of bits you need.
I actually tried
sum*((a*b)%MOD)I doesn't work either.You want
sum*i*bnot to give overflow. Thus:sumearlier. Insertsum %= MOD;before the line, or perhaps after computingsumwith that casting to double.sum*iby((sum*i)%mod).The good thing is that delaying the modulo to the end of the line is still okay, although you should try making a habit of taking modulo after every arithmetic operation if overflow is a problem.
Yeah, it worked! Thank you really much. I appreciate your effort.
(ll)expected, but(double)foundShouldn't it be double because something divided by 2 might something.5?
use
(ll)(a+1)*a/2insteadBecause there is exactly one even number in a+1 and a.
There should be another mistake somewhere else because it still doesn't pass. 8208763
sumis too large.Observe that all numbers satisfying the condition has the form x = (bk + 1)(mod(x, b)). Since mod(x, b) can be any integer between 1 and b - 1 inclusive, k can be any integer between 1 and a inclusive, and all those numbers are valid, you're adding up (b + 1)(1) + (b + 1)(2) + ... + (b + 1)(b - 1) + (2b + 1)(1) + (2b + 1)(2) + ... + (2b + 1)(b - 1) + ... + (ab + 1)(b - 1).
We group every b - 1 terms; these are all in the form
for some x. Thus our sum becomes 
, which can be simplified to 
.
There you go, an O(1) solution. I wonder why the time limit is 1.5 seconds...
Time limit is 0.00001 seconds ?
hey thanks for the solution.. Can O(b) or O(a) solutions which are given here pass under 1.5 seconds? Also, How do i check what is the expected complexity according to constraints in such problems
Yes, both O(b) and O(a) will pass. Can you rephrase the second question as I did not understand it.
I did the same.
But why i got WA?
http://mirror.codeforces.com/contest/476/submission/8205508
Check your mod and division by 2. http://mirror.codeforces.com/contest/476/submission/8210369
Nevermind.
Change a and b type to long long and it will pass =) You simply overflow in (b*(b-1)/2). http://mirror.codeforces.com/contest/476/submission/8211783
Yes I noticed after :D Thank you !
Thank you.
Are there any mathematics calculations which way you thought that all numbers satisfying the condition has the form x = (bk + 1)(mod(x, b)) ? Does it mean that you get this formula with transform this: k=(x/b)/(mod(x,b) or you just get it by logical analysis ?
I know that 'X' has form (bk + 1)(mod(x, b)) but I doesn't get it by algebraic manipulations. Could I get it from this formula: k=(x/b)/(mod(x,b) ? ( Excuse me for this stupid question but i really don't understand why you add 1 there: (bk **+ 1**)(mod(x, b)) ) certainly if you get this by algebraic manipulations. )
Note that x = b·div(x, b) + mod(x, b). (This is more or less by definition; div(x, b) is x / b rounded down, thus when multiplied by b gives the largest multiple of b not exceeding x, and mod(x, b) is the missing amount to bring the multiple of b up to x.)
The rest is just plugging in what's given in the problem and manipulating a bit.
Thank you ! It's really help me.
Now we see that , r can be 1 to b-1. thus for a particular value of k, we have
so , psudocode is below
don't forget to mod every expression.
I spend more time for problem C div 2, I am bad
Yeah i did that too. i was just getting confused with all those numbers . (defined by problem and me !)
Very interesting problems! Thanks to authors!
div 1 C без дерева отрезков\фенфика зайдет в ТЛ? Ясно что за |S|^2 находим отрезки из которых можно вырезать p, потом перебираем x, берем самые дешевые отрезки, которые не пересекаются, а потом нужно проверять пересечение и отмечать, можно ли делать это за линию?
How to solve Problem C Div 2 / problem A Div 1 ? i am trying to calculated with arithmetic sum formula
Sn = (n/2) * ( 2*a + ( n - 1 ) * d ), where n is the limit of the sequence . here is my code WA at test case 5 . can anyone please explain what is going wrong here .удален.
This is my submission on A Div.1: 8203037
What is wrong with my expression?
Because your algorithm is wrong !!!!!
Thank you, captain obvious :v
Btw I'm asking what's wrong, not why it's wrong :v
I don't understand your questions
ok what? your algorithm
I think you misinterpreted the problem or something, thinking that you're only counting numbers between 1 and a or something, not counting numbers whose k is between 1 and a.
solution of div2-E / div1-C someone please?
DP with state pos, no_char_to_delete, where pos is the position of S.
First pre-calculate next[i] for each i, where you can find P in S[i,next[i]], deleting zero or more character.
Then using this info, you can run the dp.
Isn't this O(pn^2), too slow?
I implemented a DP with those states using some precomputing and making it in total O(pn log n). I suppose the simplest O(pn^2) approach should TL.
I got that, but the number of useful states isn't Theta(pn^2)? If that's not the case, may you only hint which kind of states are useless?
there is precalculation of |S|*|S|
then the dp too is |S|*|S|
Your DP is F[i][j] — maximum amount of patterns that can be formed if you use characters 1~i and remove exactly j letters. O(pn) states.
But its only O(n^2).
Первые 40 минут контеста решал задачу (и решил) с формулой
a * div(x,b)/mod(x,b) = k
Не знаю, чего здесь больше: моей глупости или плохо написанного условия. Но и то, и другое имеет место. Не надо так :(
I tryed to use long double (16 bytes in my gcc) and printf("%Ld",v) for "B" problem but not lucky at 1st test. double and "%f" passed 1st test, and "%.9f" passed all tests... I don't understand why "%Ld" not passed 1st test, where is my error?
long double,you should use cout<< to output....Ld is not using to output long double
BTW,if you run this code in CF.
you will find sizeof(long double) is 12 in CF...
who can tell me where is my "#"? and why the string is bigger than others?
#produces a level 1 heading.Heading level 1 (
#in front)Heading level 2 (
##in front)Heading level 3 (
###in front)Use
~~~~~to delimit your code, putting it above and below the code.THX~~
thanks for your answer.
I'll use cin/cout in future. but. I think printf("%f",(double)ld); is not bad.
C Fail system test on 26.... Yellow, here I come back!
Can anyone explain pretest 5 (input: 4 3) in problem C(div.2)?
Which numbers should be added?
a = 4, b = 3
Try for k = 1. We want div(x, 3) = mod(x, 3). Since mod(x, 3) = 1, 2, we thus have two numbers: one with div(x, 3) = mod(x, 3) = 1, and one with div(x, 3) = mod(x, 3) = 2. The numbers satisfying this are 4 and 8 respectively.
Try for k = 2. We want div(x, 3) = 2·mod(x, 3). Since mod(x, 3) = 1, 2, we thus have two numbers: one with div(x, 3) = 2, mod(x, 3) = 1, and one with div(x, 3) = 4, mod(x, 3) = 2. The numbers satisfying this are 7 and 14 respectively.
Trying for k = 3 gives 10, 20, and for k = 4 gives 13, 26.
Adding them all gives the requested 4 + 8 + 7 + 14 + 10 + 20 + 13 + 26 = 102.
Just write a brute force ....
the numbers are : 4 7 8 10 13 14 20 26 sum = 102
Hello !
what's wrong with my code?! for div 2 C
http://mirror.codeforces.com/contest/476/submission/8197243
((b % mod) * (sum2 % mod) * (sum1 % mod))If
b % mod,sum2 % mod,sum1 % modare together pretty large (about 109 each), they make the resulting number to get overflow (about 1027).Try to mod every value RIGHT AFTER multiply. Don't multiply three values in a time, it will be overflow.
Hi!
I got a TLE on D, but I found out that my program ran exactly 2000ms on some case but the system gave me a TLE :(
Here's the submission link: http://mirror.codeforces.com/contest/477/submission/8206241
Changed
to
and my C passed ;__;. I'm such a loser ;_;.
How to solve div1-C?
First you need to calculate nearest subsequence that match P and start from i for every i<s.size .
Now we can use a simple dp, at each position we have 3 choices :
1- you can skip this position to next one so : rec(pos+1, should_delete).
2- you can delete this position if should_delete!=0 so : rec(pos+1, should_delete-1).
3- if we have match from pos we can use this match, we have the ending position of this match (calculated in first step) so number of characters we need to delete so we can use this match is : end[pos]-pos+1-p.size . now if this number is less than or equal to should_delete then you can use this match so : 1+rec(end[pos]+1, should_delete-(end[pos]-pos+1-p.size)).
The answer for each step is maximum of this three choices.
First, let's calculate for each position
iin stringsvalueL[i]— minimum length of substring which ends iniand it is possible to get stringpby removing some characters from it. It can be easy calculated using dynamic programming.Next, let's find
dp[i][cut]— answer for prefix ofswhich ends iniand withcutcharacter removes done. It can be calculated next way:This solution gives us O(|s|3) complexity. But you can notice that in every
dpvisited in the cycle difference betweeni - kandcut - k + p.length()is fixed: it is equal toi - cut - p.length(). So, you just need to use fenwick trees where inftr[i + cut][i]you will update the answer.Then the cycle will look like this:
dp[i][cut] = max(dp[i][cut], get(ftr[i - cut - p.length()], i - k) + 1);whereget(a, b)function returning maximum on fenwick treeaprefix with length equal tob.Of course, you can examine my solution: 8203748
I read all the problems first time incorrectly. I figured first one after first wrong submission, figure second after frustrated by C which I made it too complex.
Btw problem was very good, lot to think less to code.
Last contest Bayan Warmup, my rank was 150, and top 50 won T-shirt.
This contest, my rank was 46, but top 50 didn't win T-shirt.
Why aren't there any T-shirt for each contest???
Indeed, Codeforces should start giving T-shirts more often. I need Codeforces and Facebook T-shirts to complete my collection.
/\
Then some people would get too many t-shirts :D
Today my contest is not so good at all, but feeling proud to see the participant ridowan007 of our country(Bangladesh) got rank 1 in Div-2. Really nice performance !!
Thanks for the nice comment :)
Welcome vai :)
Thank drazil for this interesting contest!
My submission for Div1-C got TLE, even though first inspection shows its complexity is O(|s|2 + |s||p|). Besides "use a faster language other than Python", is there anything in my code that can be improved?
My algorithm is to first find all "sufficiently close" subsequences of s that is equal to p (this is constructing the array
found), by iterating over each character of s and p, taking note when the latest starting position of a subsequence of s ending with the character in p. Note that since any ending character is used only once, there are only |s| elements at most. Next, I used a DP with states of the form (latestfoundelement considered, number of subsequences) (this is constructing the arraydp).At the end of this, I have an array of how many characters at least must be deleted to give a given number of subsequences (this is constructing the array
dpres), which is easily converted to give the maximum number of subsequences possible by deleting a given number of characters (this is the first state ofres; the second state just takes the minimum of the first state and the theoretical maximum number of subsequences with only having a certain number of characters).what's wrong?
Thanks for all the interesting problems.
I liked Div 2 C and B very much.I didn't come up with solution for A.Interesting and nice problem set.
In problem C div 1 (E div 2)
occ(s',p)was a set of substrings. What does "substring" mean?A substring of another string S is a string of consecutive characters of S; in other words, it is formed from S by deleting some (including all and no) characters from the front and the back, but without deleting any character in-between the chosen characters. If S = abcd, then bc, ab, b, a, abcd, ε are substrings of S (ε is the empty string), but bd, abd, cb aren't.
Thank you, sometimes it is not clear for me, is substring like subsequence — where you can delete some character in-between.
I think there should be one more line in problem C Div.1. div(x,b)%mod(x,b)=0. This causes problem in understanding problem statement for a lot of participants.
You mean C Div 2?
Normally if division is written using mathematical typeset it is to be interpreted as real division. Besides, if the intention is floored division, it should have been div(div(x, b), mod(x, b)) = k instead, as the problem already defined div. And of course you can always ask the problem setter using the question asking feature.
No. It was stressed that their quotient must be an integer (e.g. not real), which is sufficient.
I didn't understand prob C. Could someone please explain me this problem
(a + (a*b*(a+1)/2))*(b*(b-1)/2)
Prob C — Div 2 By using above formula why i am getting WA http://mirror.codeforces.com/contest/476/my#
long long?
Btw — look at the link you've attached. There is "my#" in the end. Is this what you wanted to link :)?
Is there a bug with the rating? It looks weird ._.
:D
didn't reach red, thats bad :D
I apologize for a re-post but i can't understand why this summation works for Div1-A/Div2-C 
)
seeking answer to same question....
Why this summation works/how one has come up to this summation??
hm...please tell me where is my mistake in div2b? (wrong test 11 after all formatting)
abs() (((((((((((((
Div I problem E: an almost same but stronger version of this problem:
http://mirror.codeforces.com/gym/100162/problem/I
This problem can be solved with O(m n log n) with simpler idea and implementation in comparision with Div.1 E.
en,yes,but there is one issue to write this kind problem to contest,if someone has solved the weak version with (n+m)*log(n) approach, he or she can copy previous code and submit in contest,and (I say just in theory) some red coder has opportunity to copy others code in the contest
In fact, there is a more similar problem on regular Codeforces round: Codeforces Round #154 (Div. 2) pC I have considered the case you mentioned. But I think the implementation of this solution is complicated and boring so nobody would implement it before CF272. I cannot deny the risk of providing this problem as pE.
And you always cannot expect a problem nobody solved it before. In fact, I think I can arrive high rating at Coeforces or Topcoder just because there are many contest problems I had written in past.
er... I think you misunderstood what I mean"write problem to contest", I'm not meaning solve problem ,I mean set task for others to solve. I haven't seen you as problem writers for many times
I think I understand what you say correctly. As a writer, I always hope my problem to be the same with other old problems. But usually I can still see other people say he create the same problem before.(I am so sad that see somebody say he set the same problem before with my SRM629 Div 1 hard. OAQ).
At least I think the idea of the problem pE is far away from the problem you mention. But it seems you don't think so. The only thing I can say is very sorry.
I am eager to create totally original problems OAQ.
Round Stats
I'm trying to submit a solution to the Div2 E problem, but I'm repeatedly getting WA on the first test case itself, even though my code is giving correct answer for both the sample test cases on my machine. Here's one of my submissions for reference. TIA.