### Marco_L_T's blog

By Marco_L_T, 4 years ago,

Hello, Codeforces!

I'm quite excited to invite you to participate in Codeforces Round #447 (Div.2 Only) which will be held on November 19 16:55 MSK.

All five problems are created by Zerui Cheng (Marco_L_T), Bingheng Jiang (NOIRP), Yiming Feng (whfym). And it's our first round on Codeforces. We want to show our great thanks to our school The High School Affiliated to Anhui Normal University and our coach Guoping Ye in competitive programming training.

And we also want to show our great appreciation to Mikhail Krivonosov (mike_live), Gleb Lobanov (Glebodin), Weihao Zhu (Tommyr7), Shiqing Lyu (cyand1317) for testing the problems, to Nikolay Kalinin (KAN) for coordination and to Mike Mirzayanov (MikeMirzayanov) for the fantastic Codeforces and Polygon platforms. The round can't be realized without their great help.

The contest will consist of 5 problems and you'll be given 2 hours to solve them. As usual, the scoring will be announced shortly before the start of the contest.

The contest is rated for Div. 2 contestants. And the same as before, Div. 1 contestants can take part out of competition.

Wish everyone high rating and bugless code!

Clarification: In the mail, it reads that the duration is 2 hours and 30 minutes and it'll contain 6 problems. There's a mistake. The duration of the contest is 2 hours and there will be 5 problems.

UPD1: Scoring: 500-1000-1500-2000-2500

UPD2: The contest is finished! Have fun hacking!

UPD3: The system test is finished! Congrats to the winners!

And do you find something interesting in the statements,especailly for Chinese contestants?

Div.1 & Div.2:

1. fateice_ak_ioi (solved all the problems and got 22 hacks)

2. peace (solved all the problems and got 10 hacks)

3. dreamoon_love_AA

4. KrK (solved all the problems)

5. Benq (solved all the problems)

Div.2:

1. fateice_ak_ioi (solved all the problems and got 22 hacks)

2. peace (solved all the problems and got 10 hacks)

4. daaaaaaaaaaaaaaaaaaa

5. QYitong1

UPD4: Maybe you're complaining that there're too many hacks and the pretests are so weak,but it's our intention to do so. We regard hacks as a very important part and a feature of Codeforces.Do you agree?

UPD5: Editorial

Hope you have fun in solving the problems and hacking!

See you next time!

• +280

 » 4 years ago, # |   +29 Auto comment: topic has been updated by Marco_L_T (previous revision, new revision, compare).
•  » » 4 years ago, # ^ | ← Rev. 4 →   +39 Contest number 447 This number is considered as a lucky number on codeforces. I wish this is the start of being Lucky. Good luck to all
•  » » » 4 years ago, # ^ |   0 Maybe not always: http://codeforces.com/problemset/problem/630/C
 » 4 years ago, # |   +38 Hope you have fun with the contest! See you on the leaderboard!
•  » » 4 years ago, # ^ |   +20 If this contest will be rated It will be very good two contests int three days Good luck
 » 4 years ago, # |   +75 wish all the participants high rating! :)
 » 4 years ago, # |   -36 Is is rated?
•  » » 4 years ago, # ^ |   +47 it has been clarified in the announcement :)
•  » » 4 years ago, # ^ |   -10 Is it*
•  » » 4 years ago, # ^ |   0 I like how you are div1 and think that is unrated
•  » » 4 years ago, # ^ |   0 It is rated for div2, but then technical issues happens and it will be unrated
•  » » 4 years ago, # ^ |   +94
 » 4 years ago, # |   +29 Hope you make progress and show yourselves!
 » 4 years ago, # |   +5 Wish you have fun!
 » 4 years ago, # |   +36 我随手AK
•  » » 4 years ago, # ^ |   +3 your first and only comment that has positive upvotes. hmmm.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +3 That's why he gets upvotes.
•  » » 4 years ago, # ^ |   0 In fact he means he will get full scores VERY EEEEEEEEASY.
 » 4 years ago, # |   +7 To be continue
 » 4 years ago, # |   +6 Applause in the front.
 » 4 years ago, # |   +9 For ratings!
 » 4 years ago, # |   +12 3 months ago i had 100 more rating than now. This contest will get everything back to normal and even higher!!!
•  » » 4 years ago, # ^ |   0 Same thing here..
•  » » 4 years ago, # ^ |   -12 It is r**** ?
•  » » » 4 years ago, # ^ |   +11 Dude you posted under my comment not in the right spot
 » 4 years ago, # |   0 2 rated contest's in two days. Amazing!
 » 4 years ago, # |   0 KAN, why the registration is delayed?
 » 4 years ago, # | ← Rev. 2 →   +16 Previous contest problem description was realy sort but briefly. I hope this contest will be same :)
 » 4 years ago, # |   -34 I think this is a mathematical contest because the authors are Chinese. I do not like it very much
•  » » 4 years ago, # ^ |   +16 Don't be so sure.Maybe you're wrong.
•  » » » 4 years ago, # ^ |   +12 What did I say? but the contest is interesting thanks for a good contest!!!
•  » » 4 years ago, # ^ |   -17 I like mathematical contest.
•  » » » 4 years ago, # ^ |   -7 Why downvote me? I just like mathematical contest, so anyone downvoting me hate it?
 » 4 years ago, # | ← Rev. 2 →   -24 Deleted
•  » » 4 years ago, # ^ |   +3 :) It has been clarified in the announcement.
 » 4 years ago, # |   +3 it seems an nice contest excited :)
 » 4 years ago, # |   -28 Prepare for non-alogrithmic idiotic math contest
•  » » 4 years ago, # ^ |   +19 Don't be that sure, please. :)
•  » » » 4 years ago, # ^ |   0 i know what im saying
 » 4 years ago, # |   -7 The announcement is not very short as previous contests.But we can see sincere thanksgiving...))Wish every body luck and high rating !And wish good luck codeforces servers!
 » 4 years ago, # |   0 Two contests in three days (if not counting contest from CS Academy lately). Well, the excitement inside me is rising high :D
•  » » 4 years ago, # ^ |   0 In between there was a topcoder srm and today we also have codechef's cookoff :P
•  » » » 4 years ago, # ^ |   0 Seems like the stack of upcoming contests has been overflowed :P
 » 4 years ago, # |   -14 RAATATTATATEDEDDDD??!?!?!?!?!??!?!?!?!?
 » 4 years ago, # |   +2 Thanks to all the people --> 2 contest in 3 days awesome feeling :) Hope for large number of hacks and good rating Wishing all the best to everyone
 » 4 years ago, # |   +1 Another Chinese round, so exciting! Hope for short statements and high rating.
•  » » 4 years ago, # ^ |   +29 You are out of competition, aren't you? How you get a "high rating"? :)
 » 4 years ago, # |   0 is it unrated?
 » 4 years ago, # |   0 haha
 » 4 years ago, # | ← Rev. 3 →   0 And the mail reads that the contest will be of 2 hrs 30 minutes. :| Also, it reads 6 problems instead of 5 as declared in announcement :3Anyway, best of luck everyone. Happy Learning and Coding.
•  » » 4 years ago, # ^ |   0 Well,maybe there's something wrong with the mail. The duration of the round is 2 hours if everything goes well.
•  » » » 4 years ago, # ^ |   +3 Yeah, I understand that. Just bringing it to the notice of problem setter/contest setter. This issue had happened once in past too :|
 » 4 years ago, # |   +1 all good luck, and let your rating go up
 » 4 years ago, # |   +16 What will you do at CF#447? Are you free? Can you come to AK?
 » 4 years ago, # |   +3 What a pity! I've just become candidate master. Now I can't get any rating!!!! QAQ
 » 4 years ago, # |   0 Wow Yayyy!!!!!
 » 4 years ago, # |   0 I want to sleep now :(
 » 4 years ago, # |   -7 I expect short problem statements.
 » 4 years ago, # |   +1 Beijing time 21：55 , perfect!
 » 4 years ago, # |   0 There should be another id to get rated. :(
 » 4 years ago, # |   +1 Hope short problem statements just like past contest.
 » 4 years ago, # |   +2 Hope everyone high rating! And hope me not to drop to green.
 » 4 years ago, # |   +1 Wish everybody High rating)))
 » 4 years ago, # |   +1 Today will be a perfect ICPC-style Contest practise!2:00 hrs Codeforces + 2:30 hrs Codechef! :/
 » 4 years ago, # |   0 Time to beat some meat.
•  » » 4 years ago, # ^ |   0 Don't do, just 10 more days
 » 4 years ago, # |   0 Why can't i register?
•  » » 4 years ago, # ^ |   +3 Don't be late.
 » 4 years ago, # |   0 That feel when div2 B is harder than div2 C...
•  » » 4 years ago, # ^ |   +8 Don't be so sure.
•  » » 4 years ago, # ^ |   +6 I don't think so :D
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +3 :o I definitely missed something. This will be a good learning experience :PContest is over, are we allowed to discuss?
•  » » » » 4 years ago, # ^ |   0 Yes
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +6 snacache what was the key observation for B?
•  » » » » 4 years ago, # ^ |   +8 I don't know haha. I just brute forced for n·m ≤ 20 and found a pattern
 » 4 years ago, # |   -17 A=B=C < D = E
•  » » 4 years ago, # ^ |   +17 I don't think that A=B or A=C.
•  » » » 4 years ago, # ^ |   +3 A < B C < B E = D ~ C very izi to E and D
 » 4 years ago, # |   -29 Hacks For C Please :(
 » 4 years ago, # |   +32 HackForces.
•  » » 4 years ago, # ^ |   +11 10/10 paint skill by the way.
 » 4 years ago, # |   +10 I was excited to see characters from Land of Lustrous in the first problem but then you dropped them later on. :/
•  » » 4 years ago, # ^ |   0 I'm sorry but I can't decide all the statement :(
•  » » 4 years ago, # ^ | ← Rev. 2 →   +5 If I have the chance to propose a contest on my own, I would write the statement in the similar way.(But maybe it will be long long time before I have the chance.)
 » 4 years ago, # |   +33 Hacks everywhere!!!
 » 4 years ago, # |   0 I was intended to hack some one on Problem C (while I found my code was wrong). But I could never load the "hack" page, watching the cycling circle. Then my submission got HACKED...??? So is it a bug?
•  » » 4 years ago, # ^ |   0 This often happens here.
•  » » 4 years ago, # ^ |   +3 I had the same and then I changed my browser (using Microsoft Edge) and I was able to hack 18 times the C problem it was really nice cause I only managed A and C
•  » » » 4 years ago, # ^ |   +5 Got it. Thank you all for explaining. _(:3 rz)
 » 4 years ago, # |   +90 The hardest B I have ever seen :D
•  » » 4 years ago, # ^ | ← Rev. 3 →   +1 What's the hack?? Why is:0 if N+M is odd and K == -1(2^(N — 1) * (M — 1)) otherwisewrong?EDIT: My code is here: https://hastebin.com/uteviyadig.cpp and I do not see any possibilities of overflow?EDIT EDIT: Oh my god, I'm so dumb, I didn't consider the case where N = INF — 1. Thank you Benq. Oops :(
•  » » » 4 years ago, # ^ |   +8 Dont forget to N %= MOD,M %= MOD,before powering
•  » » » » 4 years ago, # ^ |   0 Yes, I did that; there's an N %= (INF — 1) and M %= (INF — 1) before the powering.
•  » » » » » 4 years ago, # ^ |   0 Why do we mod the exponent? Is there a name for this technique?
•  » » » » » » 4 years ago, # ^ |   0 Fermat's Little Theorem. See here.
•  » » » » 4 years ago, # ^ |   0 OMG... That's why I got hacked at the last second.. Thank you
 » 4 years ago, # |   +3 What's the hack for C?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 31 6 9
•  » » » 4 years ago, # ^ |   +7 What is the answer?
•  » » » » 4 years ago, # ^ |   +18 it's possible: 1 6 1 9 1
•  » » » » » 4 years ago, # ^ |   +4 But 6 and 9 gcd is 3 and it is not present in the given intial set. Was I solving the wrong problem all the time?
•  » » » » » » 4 years ago, # ^ |   +2 But 6, 9 need not be adjacent in the actual array.
•  » » » » » » 4 years ago, # ^ |   +3 Only GCD of a sequences matter. In this case GCD(6, GCD(1, 9)) , which is equal to 1.
•  » » » » » » » 4 years ago, # ^ |   +1 Okay, indeed I misread the whole contest. I assumed that any two numbers GCD should be in the set. Now the problem is relatively simple. If the smallest number divides all other number, then print a[0], a[1], a[0], a[2], a[0], a[3] and so on.
•  » » » » » 4 years ago, # ^ |   +11 Interesting, I asked for a clarification in contest and I received this answer back:"If answer exists,we can always find an answer in increasing order."It seems that this answer is not in increasing order...
•  » » » » » 4 years ago, # ^ |   +3 This is disaster
•  » » » » 4 years ago, # ^ |   0 9 1 6?
•  » » » 4 years ago, # ^ |   0 ANS = -1 ?
•  » » » » 4 years ago, # ^ |   0 Nope. 6 1 9
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 You are right
 » 4 years ago, # |   0 what's C's hack data?It's amazing.
•  » » 4 years ago, # ^ | ← Rev. 4 →   0 Maybe 3 5 7 35 EDIT : The output should be -1.
•  » » » 4 years ago, # ^ |   0 thanks a lot.
•  » » » 4 years ago, # ^ |   0 Could you tell me how to solve it?
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   +15 Let m be the minimum value of the set. A possible solution is A[0] m A[1] m A[2] m ...... m A[n-1] No solution if m does not divide all values in the set. Code
•  » » » » » 4 years ago, # ^ |   0 How to check if the answer is -1?
•  » » » » » » 4 years ago, # ^ |   +10 No solution if m does not divide all values in the set. No solution means ans=-1.
•  » » » » » » » 4 years ago, # ^ |   0 Got it, thank you very much.
•  » » » » » 4 years ago, # ^ |   0 how could prove that we just need to check that m doesn't divide all values in the set? QAQ
•  » » » » » » 4 years ago, # ^ |   0 Because if m does divide all of them, the construction I showed above is always valid as any subarray of size >= 2 will have GCD exactly m, and all the elements of the original set are present as subarrays of size 1.
•  » » » » » » » 4 years ago, # ^ |   +5 Got it! But why there won't have another method to construct a solution while m doesn't divide all values in the set
•  » » » » » » » » 4 years ago, # ^ |   +8 GCD of the whole array will be the minimum value in the set. So, that value should divide GCD values of all the subarrays, i.e. all members of the set.
•  » » » » » » » » » 4 years ago, # ^ |   0 Got it. thanks a lot.
•  » » » » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Sir can you please tell me what your code did for the input -21 6
•  » » » » » » » » 4 years ago, # ^ |   0 Prabably because minimum of S must be GCD of the whole sequence. If if doesn't divide all other subsequences, then given S is invalid.
•  » » » » 4 years ago, # ^ |   0 I got hacked in last 15 minutes :(
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 One greedy solution also can be to calculate the GCD of the set and then if the GCD is itself present in the set then answer will be 2n numbers where at odd positions will be the GCD and at even positions will be the numbers of the set. Otherwise -1.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +6 1 -> 1 gcd(7) = 71 -> 2 gcd(7,35) = 72 -> 2 gcd(35) = 35That's Wrong answer :/
•  » » » 4 years ago, # ^ |   0 When will you get the 5 then? gcd(7,35) = 7
•  » » » » 4 years ago, # ^ |   0 Oops, my bad ._.
•  » » 4 years ago, # ^ |   +1 4 2 8 12 16
•  » » » 4 years ago, # ^ |   0 I really appreciate it
•  » » 4 years ago, # ^ |   0 I used 3 18 27.possible ans is 27 3 18. but most peoples code gave -1.
 » 4 years ago, # |   0 Was E computing scc and calculating for each scc and taking the max of it???
•  » » 4 years ago, # ^ |   0 That's what I tried but I got WA on test 3. I also traversed from the SCC of the starting tree until the end of path and took maximum over all using DP.
 » 4 years ago, # |   +3 10 hacks per second !
 » 4 years ago, # |   0 When u hack 14 but u know that ur own code is incorrect in 2 probs B) .
 » 4 years ago, # |   +32 Problem difficulty: A < C < E < D < B.
•  » » 4 years ago, # ^ |   0 D was definitely hard, but, come on, D < B?
•  » » » 4 years ago, # ^ | ← Rev. 3 →   +11 Believe or not, my mind completely draw a blank in B. In the last 30 minutes of the contest, I tried some idea (like flipping sign of four cells that are corners of rectangle won't change the result), but none of them works. By the way, how to solve it?
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   +24 Notice that after you choose the numbers in the upper left N - 1 by M - 1 grid, the rest of the numbers are determined. So the answer is 2N - 1·M - 1. You also need to check the case where N + M is odd and K =  =  - 1. (Answer is 0 in such case).EDIT @below: Yeah, you're right, oops.
•  » » » » » 4 years ago, # ^ |   +5 Do you mean 2(M - 1)(N - 1)?
•  » » » » 4 years ago, # ^ |   +28 It's a classical combinatorics problem. In case k = 1, you can arbitrarily fill the top-left (n - 1) × (m - 1) matrix — other fields will be uniquely determined and correct. Thus in that case the solution is 2(n - 1)(m - 1). The same logic applies when k =  - 1 and n ≡ 2m. Otherwise you can show that there is no solution.
•  » » » » » 4 years ago, # ^ |   +4 Problem B. Let's consider the k = 1 case. I don't understand the fact why solution is uniquely determined by fixing the top-left matrix arbitrarily. I get it that all the elements (i,j) where j = m and i = 1 to n-1 and i = n and j = 1 to m-1 are uniquely determined by parity of negative numbers in that row/column. The now filled numbers of the last row and the last column determine the element (n,m). What if they contradict each other ?! Then the sign of (n,m)th element is not uniquely determined right ?
•  » » » » » » 4 years ago, # ^ |   +13 They won't contradict because the product of all the numbers in the last row (except the last element) is equal to the product of all the numbers in the last column (except the last element), because they are both equal to the product of all numbers in the (n - 1) × (m - 1) submatrix.
•  » » » » » » » 4 years ago, # ^ |   0 Thank you so much!
•  » » » » » » 4 years ago, # ^ |   0 After chosing one columm after another, numbers of product of cells in the same row and in each columms before is always even. So product of the last columm is even.
•  » » » » 4 years ago, # ^ |   +7 Write brute force, build a table with answers, see the pattern :)
•  » » 4 years ago, # ^ |   0 How to solve E?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +6 Compress the strongly connected components. In each SCC, you can repeatedly traverse cycles and reduce each edge to 0. After compressing SCCs, do DP on the DAG to get max path length from source to any leaf. Code
•  » » » » 4 years ago, # ^ |   0 This is exactly what I did but I got WA on pretest 3? Could you tell me what I is wrong?
•  » » 4 years ago, # ^ |   0 For B, I did a simulation to get the pattern. Was able to make 2 hacks in my room. let's see if my solution passes the system test.
•  » » » 4 years ago, # ^ |   0 can you tell how do the output for third case is 16 ?
•  » » » » 4 years ago, # ^ |   +5 Here are the 16 possibilities.  1 -1 1 -1 -1 -1 1 -1 1 -1 1 1 1 1 -1 1 -1 1 -1 -1 -1 1 -1 1 1 -1 1 1 1 -1 -1 1 1 1 -1 1 -1 1 1 -1 -1 -1 -1 1 1 1 -1 1 1 1 -1 -1 1 1 1 1 -1 1 -1 1 -1 1 1 -1 -1 -1 -1 1 1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 1 1 -1 -1 -1 -1 1 -1 1 1 -1 1 -1 -1 -1 -1 1 1 -1 1 1 -1 -1 -1 1 1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 1 1 -1 1 1 -1 -1 1 1 1 -1 1 1 1 -1 1 -1 1 -1 1 1 1 1 -1 
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Why not-1 -1 -11 1 11 1 1
•  » » » » » » 4 years ago, # ^ |   0 -1 -1 -1 => Product = -1 1 1 1 => Product = 1 1 1 1 => Product = 1 So, this is not a valid solution.
•  » » » » » » » 4 years ago, # ^ |   +6 I am an idiot
•  » » 4 years ago, # ^ |   0 I cannot agree more! Even for me solutions of D and E were much more obvious than B. That's not something happens any often. I believe if B/C were not such killers, D and E would be solved by many more people though they were tedious.Then again I did not expect this solution of D with complexity O((n + m)log2n) would pass. Isn't it almost 4 × 108? 2.5s seemed impossible.
 » 4 years ago, # |   0 How do the output for third case is 16 ? PROBLEM: B
•  » » 4 years ago, # ^ |   0 Also wondering
•  » » 4 years ago, # ^ |   0 Constructive algorithm:total 2*2 arrays = 16,the parity bits can be inserted accordingly.
 » 4 years ago, # | ← Rev. 2 →   +10 Authors thanks a lot for this Hack party! Very nice problems!
 » 4 years ago, # | ← Rev. 2 →   0 I had I idea to code Tarjan for E (still not sure will it work) but then saw so many wrong Cs in room.
 » 4 years ago, # |   +11 Wow, that was the hardest B I have seen in a while. I had to bruteforce to find the formula. Moreover, I guess a lot of people are either hacked or FST because of taking modulo mod p instead of (p-1).
•  » » 4 years ago, # ^ |   0 Hi, I used mod p and got accepted (submission here)I see you used p-1, Why is mod (p-1) the correct answer?Thanks
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +5 Well I think he means exponents... It's Fermat's little theorem. when p is a prime number
 » 4 years ago, # |   +24 Authors should care more about the pretests, because there were more hacks than Accepted codes on task B! -_-
•  » » 4 years ago, # ^ |   +8 It's what we intended to do,we intend for a lot of hacks on B and C.
•  » » » 4 years ago, # ^ |   +14 Why did I get this incorrect clarification? Is this how you intend for hacks?https://imgur.com/a/7kuB4
•  » » » » 4 years ago, # ^ |   +7 Really sorry for this.I don't know who answered your question,maybe he is so busy answering questions that he made a mistake.
 » 4 years ago, # |   +4 Not a Div. 2 contest. B, C were too difficult.
 » 4 years ago, # |   0 So, how to solve B? I can't think about it anymore :(
•  » » 4 years ago, # ^ | ← Rev. 2 →   +9 Backtrack on small N,M you'll find that the answer is 2N - 1 * M - 1
•  » » » 4 years ago, # ^ |   +4 Any intuition behind this?
•  » » » » 4 years ago, # ^ |   0 I can try. At each cell you can either put a 1 or -1 . Hence for one row there are 2^m possibilites. now suppose all cells in a row are 1. for the product to be 1 you need even count of -1s to be present in each row. so you have mChoose0 + mChoose2 + mChoose4..... which is 2^m/2 = 2^(m — 1). the count for -1 product is exactly the same.Now you do the same for columns and multiply the exponents to get the overall count. I hope this helps a little bit atleast.
•  » » » » 4 years ago, # ^ |   0
•  » » » 4 years ago, # ^ |   0 how come some of the test cases didn't pass with that approach?
•  » » » » 4 years ago, # ^ |   +3 The extra requirement is that if k == -1 and n%2 != m%2, the answer is 0.
 » 4 years ago, # |   0 What's wrong with my approach to C? For each starting position i we find the gcd until all positions j (i < j < m). Then, for each gcd, we check if it's in the given array. If it's not, output -1; otherwise, output the given array.Thanks in advance.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 41 5 6 8ans:6 5 8
•  » » » 4 years ago, # ^ |   0 I see now. The elements in the initial array don't have to be increasing order. Thanks!
•  » » 4 years ago, # ^ |   +3 3 1 4 6 your approach would give -1 as 2 is absent which is gcd of 4, 6 but answer is possible. answer : 5 1 4 1 6 1
•  » » » 4 years ago, # ^ |   0 Thanks. I unfortunately set a nonexistent constraint for myself :\
•  » » » » 4 years ago, # ^ |   0 can you tell me why absence of 2 is neglected????
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   +3 because in the final answer array every alternate position is occupied by the number which is divisible by every other number say num. so it is easy to see that now for every subarray of size greater than 1 you can achieve num as gcd. Rest remains the case for every single element (for which gcd is equal to the element itself) which are already present in the original array. if no candidate is possible for num then answer is -1.
•  » » » » 4 years ago, # ^ |   +3 you are not alone bro :/
 » 4 years ago, # |   +1 HackForces~
 » 4 years ago, # | ← Rev. 2 →   +2 Hack for C : 3 3 18 24 Answer is 4 3 18 3 24 
•  » » 4 years ago, # ^ |   0 What's the answer for this test case?
•  » » 4 years ago, # ^ |   0 when we take gcd(18,24) we get 6 but 6 is no where present in the set. how is this possible answer? am i missing something?
•  » » » 4 years ago, # ^ |   0 You're missing the 3 between 18 and 24.
•  » » » 4 years ago, # ^ |   0 This is answer, because you need take gcd on segment, so gcd(18,3,24)=3 and all is correct
•  » » » 4 years ago, # ^ |   0 You calculate gcd(ai, ai + 1, ..., aj) for every 1 ≤ i ≤ j ≤ n, so there won't be gcd(18,24) at all, instead, it is gcd(18,3,24), which is 3.
 » 4 years ago, # |   0 Troll C-task easier then B. Good job, bro
•  » » 4 years ago, # ^ |   +13 Nop,after the systest maybe you'll change your opinion.
•  » » » 4 years ago, # ^ |   0 mmm...no non-trivial formula for B and example S[0],S[1],S[0],S[2],S[0],S[4]... (and some exception, then S[i]%S[0] !=0)
 » 4 years ago, # |   +39 Half of participants during the contest
 » 4 years ago, # |   0 It is a hacker's round...XD
 » 4 years ago, # |   +14
•  » » 4 years ago, # ^ |   0 everyone is dead, except YOU!!!!!
 » 4 years ago, # |   0 Can Anyone Explain How to solve Problem B
 » 4 years ago, # |   +4 Problem C is a very nice trolling problem :D
 » 4 years ago, # |   0 How to solve D?
•  » » 4 years ago, # ^ |   0 It is almost a complete binary tree and has max depth logN. To solve query for V, I checked all ancestors as LCA and did a range query on the subtree of the other child using persistent segtree (can be done offline with BIT too). Code
•  » » » 4 years ago, # ^ |   0 Your method is too complicated. The author's solution uses merge sort to pre-process and takes O(log^2) time to check the answer by brute force.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +3 Okay, yeah I know it is too complicated but it struck me immediately and I coded it. My solution solves in log^2 time too but I guess persistence is unnecessary. :)
•  » » » » » 4 years ago, # ^ |   +1 umm. could you please explain the persistent segtree part. I didnt get you exactly. Thanks
•  » » » » » » 4 years ago, # ^ |   +3 Given vertex V and parameter L, I need to find sum of distances from V to any vertex U in its subtree such that dist(V, U) <= L. I flattened the tree and constructed persistent segtree on it. So, the query reduces to find the sum of values in some subarray such that value <= L.
•  » » » » » » » 4 years ago, # ^ |   0 How do you manage not to count twice or more the nodes of his subtree. For example in node U you count some childen node (call it x), and then when you climb up to U's parent maybe you can count again that x node.
•  » » » » » » » » 4 years ago, # ^ |   +3 I query the segtree on the siblings of ancestors of U and not on any ancestor of U. Those subtrees are mutually disjoint.
•  » » » » » » » » » 4 years ago, # ^ |   0 Got it. Thanks
 » 4 years ago, # |   +1 y u do zis
 » 4 years ago, # | ← Rev. 2 →   0 although i am a bad coder because i dont practise algos efficiently i have this mathematical intution for b which lead m to solution.I though answer as 1 and 16 and immediatley power of 2 came to my mind 16 is 2^2*2 and 1 is 2^0*0 so i guessed 2^n-1*m-1.Immediately lightning fell i though i could fill up n-1*m-1 internal squares nyway then fill last row in last column my wauy. That 16 was a big hint. Power of 2
•  » » 4 years ago, # ^ |   +3 lightning electrocuted me
•  » » 4 years ago, # ^ |   0 This was my thought too but I got hacked. I don't think you can fill up the internal squares in any way you like and then fill last row and column to make it work. For example consider a 4x4 grid with k=1. One way to fill in the internal 3x3 is:  1 1 1 1 -1 1 -1 1 -1 But there is no way to complete this. The last row would have to be: -1 1 -1 1 and the last column would have to be:  1 -1 1 -1 So we get a conflict in the bottom right cell.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   -14 You miscalculated the last row with your example. With you example the last row should be all -1's because each column currently has a product of -1.
•  » » » 4 years ago, # ^ |   0 Oops nevermind, I made a mistake. I put the last row wrong.
 » 4 years ago, # | ← Rev. 2 →   +3 System test already done lolFastest ever
•  » » 4 years ago, # ^ |   0 Almost nothing to test except A.
 » 4 years ago, # |   +10 Some of the weakest pretests I have ever seen in my life. Solutions with n and m defined as integer passed the pretests in problem B. Solutions that didn't check the case (n + m) % 2 = 1 and k = -1 passed the pretests in B. And problem C pretests were obviously a troll because most people solved a completely different problem yet passed the pretests. gg problem setters
 » 4 years ago, # |   0 Diabolical test case for C (I guess):41 3 15 20
 » 4 years ago, # |   +23 Today, I had a bug inside a bug in problem C which saved me from getting hacked! // ok? bool ok = true; for (int i=1; i<=n; i++) { int g = 0; for (int j=1; j<=n; j++) { g = gcd(g, a[j]); if (!x[g]) { ok = false; } } } int gg = accumulate(a+1, a+n+1, 0, gcd); if (!ok) { cout << -1; return 0; } So, my original idea was to check, for every subsegment of the given set, whether its GCD appears in the set. Now this is obviously wrong (testcase = [1, 4, 6]), but in doing so I misimplemented this piece of code and I actually checked whether the whole set's GCD was in the set, which is, coincidentally, exactly what I should have done, only not n times! :D Notice how the inner loop starts from j = 1 and not j = i.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +8 One guy in my room had same situation :D
•  » » 4 years ago, # ^ |   0 This is literally fight bug with bug
 » 4 years ago, # |   +58 Room 110 (my room)
 » 4 years ago, # |   0 my code with scanf accepted but with cin it got TLE!Not cool author! not cool...
•  » » 4 years ago, # ^ | ← Rev. 2 →   -17 Deleted
•  » » » 4 years ago, # ^ |   +8 I am sorry but I couldnt see in D and E statements it being suggested.
•  » » » 4 years ago, # ^ |   -24 Oops,my fault!I had suggested,but it was removed later. Sorry for not suggesting faster ways to input or output.
•  » » » » 4 years ago, # ^ |   +32 Why do you need to recommend faster I/O at all? Wouldn't just setting higher time-limits be a better way of dealing with it, unless you already had some slow nearly-passing solution in mind?If a problem's only solvable with fast I/O that means that most likely you can only solve it in a very small number of languages. In fact, in this contest 100% of the accepted solutions were in C++. There are a few correct-looking Javas but they all got TLE. That's not great.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 First, scanf works better than cin, I think. And if we guarantee that cin is ok, the time-limits must be set much higher. Some TLE algorithm could pass tests easily (such as some slow O(n(log(n))2) algorithm for problem D). And we don't want this happen.
•  » » » » 4 years ago, # ^ |   +15 Also, did you decide not to include max tests into pretests intentionally? I agree that contestants can (and in a lot of cases should) generate max.tests by themselves to be sure that their solutions work, but still — making such pretests sounds like a way to decrease success rate at first place :)
•  » » » » » 4 years ago, # ^ | ← Rev. 3 →   -22 Wrong information. Deleted. Sorry for no max-size cases in pretests.
•  » » » » » » 4 years ago, # ^ | ← Rev. 3 →   +33 OK, let's take a look.My cin/cout solution to E which passed pretests fails on test #14 with n=400k, m=1e6. Looking at first 13 tests and assuming that all of them are pretests, the biggest one I see has n=1e5, m=233333. It means n+m=1e6/3=1/6 of max.test.My cin/cout solution for D fails on test #18 with n=1e6, m=1e5. Looking at first 17 tests, there is test #8 with n=438275, m=22553, and a bunch of tests with n=2e5, m=1e5. Adding it up for test #8, we'll get ~4.6e5, less than 1/2 of max test.So can you please tell exact constraints of largest tests provided in pretests? It seems to me like they are quite far away from being maxtests. Yep, maybe they are rather large — but from your comment it sounds like tests are "special" if N=1e6 and ordinary if N=1e5 :) I already saw your comment in contest announcement, and that's why I'm curious — is the story with D and E same and you expected that it will lead to a lot of hacks, or you just wanted more people to fail, or was it some sort of preventing server load or anything like that, or was it just a miss in contest preparation, or what was the motivation at all.In case it was done trying to increase number of hacks — such strategy doesn't work well :) I see as many as total of 2 hacked solutions on E and no hacked solutions on D. I didn't check if they failed because of TL or not :) First of all, not many people are trying to hack hard problems (most of the contestants don't even solve them), and second — hacking I/O is generally harder and takes more effort — you have to be sure about it and know some benchmarks, and there are quite a few tricks like "this thing works fast in GCC but slow in MVS" etc.. Also, I believe that most of the contestants think about it like "OK, there is probably maxtest in pretests, so if they passed — that should be fast enough". It may be different for some trickier tasks, when people try to push NsqrtNlogN algo for 5e5 or take naive solutions with a bunch of optimizations and breaks, but not for something like D/E yesterday, where complexity of any reasonable solution barely depends on input structure — but only on its size.
•  » » » » » » » 4 years ago, # ^ |   -12 Sorry for any inconvenience caused.We set a tight time limit on D and E because we don't want to see slow solutions pass.For example,someone used O(nlog^2n) solution on D which is not intended and someone used brute force to calculate the answer for each edge which is O(m*sqrt(Ai)).We just didn't want to let this kind of solution pass.As a result,cin/cout may get TLE.
•  » » » » » » » » 4 years ago, # ^ |   -12 Also,you said that we didn't put maximum tests in the pretests.However,in our opinion,a contestant should be able to generate some data and use custom invocation to check whether the solution can fit in the time limit.And there isn't any regulation saying maximum tests should be put in the tests.If it made you feel not so good,we apologize for this.
•  » » » » » » 4 years ago, # ^ |   +11 Sorry for my wrong information. Someone told me we have max-size cases in pretests.
 » 4 years ago, # |   0 And have fun FST on Problem C. QAQ
 » 4 years ago, # |   +5 I like the way of setting pretests and main tests ;-) good job
•  » » 4 years ago, # ^ |   0 Counter strike fan ?
•  » » » 4 years ago, # ^ |   0 yes
 » 4 years ago, # | ← Rev. 2 →   0 Less Codeforces, more Hackforces.
 » 4 years ago, # | ← Rev. 2 →   -15 B was TOO DIFFICULT! Lol, now the correct submissions after system tests are in perfect order: A>B>C>D>E.
 » 4 years ago, # |   -7 What a fuck. It was so fucking hard. A easy, C normal C. But dudes come on. WTF is with B. Even if you find the correct formula like i did, you still need to take care of corner cases and also B and fast exponentiation that's funny.
 » 4 years ago, # | ← Rev. 2 →   +20 B is pure evil!
 » 4 years ago, # |   0 Why time limits for first three problems are 1 sec? Usually its 2 sec.
•  » » 4 years ago, # ^ |   0 The solution of the first three problems is very fast. So there's no need for 2sec
•  » » 4 years ago, # ^ |   +4 squirtle used used 'hard b and c' attack critical hit sandshrew fainted
 » 4 years ago, # |   0 Hi guys whats wrong with this http://codeforces.com/contest/894/submission/32469968
•  » » 4 years ago, # ^ |   0 i am very sad i got the algo in contest but dont know why it got hacked
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 read my next comment
•  » » 4 years ago, # ^ |   +3 bro in youre pow function you should set it to :long long pow(long long x, long long y, long long mod) { ... }you've overflowed ;-)
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +3 shit you are right it got accepted now. feels sad small mistake destroyed me.Else i culd have felt happy that i solved b in contest Thank you so much
 » 4 years ago, # | ← Rev. 3 →   +2 For those who can't understand why they got hack on B, here is a problem using Fermat's Little Theorem -> see the editorial from this problem https://www.hackerrank.com/contests/infinitum18/challenges/tower-3-coloring; why a^b mod c is a^(b mod(c-1)) mod c
•  » » 4 years ago, # ^ |   +24 No need.It's too complicated.We can calculate in this way:pow(pow(2,n-1),m-1)
 » 4 years ago, # | ← Rev. 2 →   +30 B and C were harder than normal (perhaps it would have been better to lower the constraints to avoid fast exponentiation?), but overall this round was not as hard as some other Div 2 rounds, considering that I managed to finish in 50 minutes ...... well, until I realized that my solution to E was incorrect. Anyways, I have nothing against weak pretests. :P
 » 4 years ago, # |   +34 Today's Round is the Proof of The First Law of Online Judges.
 » 4 years ago, # |   +132
•  » » 4 years ago, # ^ |   +3 They are twince ! Hacked !
•  » » 4 years ago, # ^ |   0 For me, A as well. Some people forgot that string.size() returns an unsigned integer. So using string.size() — 2 when string length is 1 will lead to overflow.
 » 4 years ago, # |   +2 For Prob C (Marco And GCD Seq)Input: 151 2 3 4 5 6 7 8 9 10 11 12 13 14 15Ouput: 106 7 8 9 10 11 12 13 14 15Why this is given wa verdict? (set of pairwise gcd of elements produced the input set)
•  » » 4 years ago, # ^ |   +2 You never generate any of 2,3,4,5 as gcds.
•  » » » 4 years ago, # ^ |   0 gcd(12,14)=2 gcd(6,9)=3 gcd(8,12)=4 gcd(10,15_=5
•  » » » » 4 years ago, # ^ |   +3 The gcd must be of consecutive elements.
•  » » 4 years ago, # ^ |   0 You cannot get 2 using your output sequence.
•  » » » 4 years ago, # ^ |   0 gcd(12,14)=2
•  » » » » 4 years ago, # ^ |   +3 It needs gcd(ai,ai+1,ai+2,...,aj) So gcd(12,13,14)=1
•  » » 4 years ago, # ^ |   0 because you can not find gcd 2,3,4,5 (i<=x<=j)
 » 4 years ago, # |   -8 Solution to problem A. QAQ was already available on the internet, well before the contest.Please visit source — http://www.geeksforgeeks.org/find-number-times-string-occurs-given-string/ Hence I don't think people should be penalised if their code matches with someone...as they both referred the same source....codeforces please see into it !
•  » » 4 years ago, # ^ |   0 emmm……At first, my wrong B is skipped……
•  » » 4 years ago, # ^ |   0 We will fix that.
•  » » » 4 years ago, # ^ |   0 Thanks
•  » » » 4 years ago, # ^ |   0 Can you please also take a look at my comment below? Thanks!
•  » » 4 years ago, # ^ |   0 Mine too...
 » 4 years ago, # |   +11 Amazing problems... Amazing system testing... Amazing Ratings Update.. Amazing CONTEST
 » 4 years ago, # | ← Rev. 2 →   -41 the contest was bad. dumb weeaboo trash and weak preliminary testcases.
•  » » 4 years ago, # ^ |   +16 No. I disagree with you. So maybe there were mistakes somewhere. But they did work to create a contest. You do not have the right to say that it was bad so-as you have never conducted a contest. Sorry if I did not put it right.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +11 While I don't agree with his sentiment, what you are saying is totally wrong too. You don't need to conduct a contest to recognise a bad one. That being said, I don't think today's contest was bad. However, he is free to express his opinion.
•  » » » » 4 years ago, # ^ |   +2 I think that a person can not understand the organizer until he tries to hold a contest.
•  » » » » » 4 years ago, # ^ |   +5 Agreed. And his manner of expressing his disappointment was very immature too.
 » 4 years ago, # |   0 if test case is: 3 1 6 9 and answer is 6 1 1 6 1 9 1 why we can't take gcd(6,9)==3; which is missing in test case.
 » 4 years ago, # |   0 Don't ever put a contest again ever are you sure that it was for DIV 2 ? really ?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 I partially agree with you since problem B was at the level of task D. But everything else was excellent. It is my opinion.
 » 4 years ago, # |   +11 I am disqulafied ,why????? My solution was by me . I am disagree with this decision
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 I think you should create a separate blog about your problem, because there will be more people there and the Administration of the Codeforces will see your appeal.
 » 4 years ago, # |   -27 really terrible contest :/very easy problems and shity codesvery very easy problem E and because of fast i/o 80% failedworst contest ever with shity problems that sucks
 » 4 years ago, # |   0 Wow this is the hardest CF Round I have participated.
 » 4 years ago, # |   +17 Why the ratings are altered again now?
•  » » 4 years ago, # ^ |   +3 maybe rejudging
 » 4 years ago, # |   +16 codeforces should become ready for the goodbye 2017 contest which has the most participants :) it did very well this round i hope it remains the same
 » 4 years ago, # |   +1 Ohhhh!! Hackforces Round!!!
 » 4 years ago, # |   +1 Really bad time limit for problem E due to big i/o Input TLEios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> ...  Input ACinline void Scanf(ll& a) //(https://github.com/mvpossum/eldiego) { char c = 0; while(c<33) c = getc(stdin); a = 0; while(c>33) a = a*10 + c - '0', c = getc(stdin); } ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); Scanf(...) 
•  » » 4 years ago, # ^ |   +3 D as well. Difference between fast IO and scanf/printf is about 1.5s, which is more than half the time limit.You have to be soo careful during implementation to even have a chance at getting AC without fast IO.
•  » » 4 years ago, # ^ |   0 Author's code uses scanf/printf for D and E. For D,it runs in 1.1 seconds and for E,it runs in 1 second. So maybe cin and cout without ios::sync_with_stdio(false) will get TLE,otherwise,maybe your complexity isn't the intended one,so it gets TLE. For example,the intended time complexity for D is O(nlogn+m(logn)^2) and for E it is O(n+m).
 » 4 years ago, # |   +17 C was such bait. Made the observation that the largest number in S must be in the sequence, and then tried to construct it from there... red herring.Realised the correct solution with 7 minutes left in the contest.
 » 4 years ago, # |   -25 What the hell was this? the worst round ever. The worst problems ever! Go home.
•  » » 4 years ago, # ^ |   +4 If you're not satisfied with the contest,please point out where we didn't do well.Only blaming will make no sense and will never help us improve and prepare better problems.Thank you!
•  » » » 4 years ago, # ^ |   +10 The problems where very interesting, But the pretest where weak that is why.
 » 4 years ago, # |   +1 Rip those submissions on C, where people saw the score board, saw high and extremely fast increasing rate of pretest passed, panicked, wrote some garbage greedy and then submitted themselves.And they got pretests passed too ! Too bad, WA. Never ever open score board during the contest is what seems best to me. The problem C is not very difficult and things may have been different with strong pretests.