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!

See you on the leaderboard!

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:

fateice_ak_ioi (solved all the problems and got 22 hacks)

peace (solved all the problems and got 10 hacks)

KrK (solved all the problems)

Benq (solved all the problems)

Div.2:

fateice_ak_ioi (solved all the problems and got 22 hacks)

peace (solved all the problems and got 10 hacks)

ec24 (made 16 hacks)

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

Maybe B and C are a little harder than before,we'll be cautious about this next time.

Hope you have fun in solving the problems and hacking!

See you next time!

Auto comment: topic has been updated by Marco_L_T (previous revision, new revision, compare).Contest number

447This number is considered as a lucky number on codeforces. I wish this is the start of being Lucky. Good luck to allMaybe not always: http://codeforces.com/problemset/problem/630/C

Hope you have fun with the contest! See you on the leaderboard!

If this contest will be rated It will be very good two contests int three days Good luck

wish all the participants high rating! :)

Is is rated?

it has been clarified in the announcement :)

Is it*

I like how you are div1 and think that is unrated

It is rated for div2, but then technical issues happens and it will be unrated

Hope you make progress and show yourselves!

Wish you have fun!

我随手AK

your first and only comment that has positive upvotes. hmmm.

That's why he gets upvotes.

In fact he means he will get full scores VERY EEEEEEEEASY.

To be continue

Applause in the front.

For ratings!

3 months ago i had 100 more rating than now. This contest will get everything back to normal and even higher!!!

Same thing here..

It is r**** ?

Dude you posted under my comment not in the right spot

2 rated contest's in two days. Amazing!

KAN, why the registration is delayed?

Previous contest problem description was realy sort but briefly. I hope this contest will be same :)

I think this is a mathematical contest because the authors are Chinese. I do not like it very much

Don't be so sure.Maybe you're wrong.

What did I say? but the contest is interesting thanks for a good contest!!!

I like mathematical contest.

Why downvote me? I just like mathematical contest, so anyone downvoting me hate it?

Deleted

:) It has been clarified in the announcement.

Prepare for non-alogrithmic idiotic math contest

Don't be that sure, please. :)

i know what im saying

The announcement is not

very shortas previous contests.But we can see sincere thanksgiving...))

Wish every body luck and

highrating !And wish good luck codeforces servers!

Two contests in three days (if not counting contest from CS Academy lately). Well, the excitement inside me is rising high :D

In between there was a topcoder srm and today we also have codechef's cookoff :P

Seems like the stack of upcoming contests has been overflowed :P

RAATATTATATEDEDDDD??!?!?!?!?!??!?!?!?!?

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

Another Chinese round, so exciting! Hope for short statements and high rating.

You are out of competition, aren't you? How you get a "high rating"? :)

is it unrated?

haha

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 :3

Anyway, best of luck everyone. Happy Learning and Coding.

Well,maybe there's something wrong with the mail. The duration of the round is 2 hours if everything goes well.

Yeah, I understand that. Just bringing it to the notice of problem setter/contest setter. This issue had happened once in past too :|

all good luck, and let your rating go up

What will you do at CF#447? Are you free? Can you come to AK?

What a pity! I've just become candidate master. Now I can't get any rating!!!! QAQ

Wow Yayyy!!!!!

I want to sleep now :(

I expect short problem statements.

Beijing time 21：55 , perfect!

There should be another id to get rated. :(

Hope short problem statements just like past contest.

Hope everyone high rating! And hope me not to drop to green.

Wish everybody High rating)))

Today will be a perfect ICPC-style Contest practise!

2:00 hrs Codeforces + 2:30 hrs Codechef! :/

Time to beat some meat.

Don't do, just 10 more days

Why can't i register?

`Don't be late.`

That feel when div2 B is harder than div2 C...

Don't be so sure.

I don't think so :D

:o I definitely missed something. This will be a good learning experience :P

Contest is over, are we allowed to discuss?

Yes

snacache what was the key observation for B?

I don't know haha. I just brute forced for

n·m≤ 20 and found a patternA=B=C < D = E

I don't think that A=B or A=C.

A < B C < B E = D ~ C very izi to E and D

Hacks For C Please :(

HackForces.

10/10 paint skill by the way.

I was excited to see characters from Land of Lustrous in the first problem but then you dropped them later on. :/

I'm sorry but I can't decide all the statement :(

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.)

Hacks everywhere!!!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?

This often happens here.

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

Got it. Thank you all for explaining. _(:3 rz)

The hardest B I have ever seen :D

What's the hack?? Why is:

0 if N+M is odd and K == -1

(2^(N — 1) * (M — 1)) otherwise

wrong?

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 :(

Dont forget to N %= MOD,M %= MOD,before powering

Yes, I did that; there's an N %= (INF — 1) and M %= (INF — 1) before the powering.

Why do we mod the exponent? Is there a name for this technique?

Fermat's Little Theorem. See here.

OMG... That's why I got hacked at the last second.. Thank you

What's the hack for C?

3

1 6 9

What is the answer?

it's possible: 1 6 1 9 1

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?

But 6, 9 need not be adjacent in the actual array.

Only GCD of a sequences matter. In this case

`GCD(6, GCD(1, 9))`

, which is equal to`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.

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...

This is disaster

9 1 6?

ANS = -1 ?

Nope. 6 1 9

You are right

what's C's hack data?It's amazing.

Maybe

EDIT : The output should be -1.

thanks a lot.

Could you tell me how to solve it?

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

How to check if the answer is -1?

`No solution if m does not divide all values in the set.`

No solution means ans=-1.

Got it, thank you very much.

how could prove that we just need to check that m doesn't divide all values in the set? QAQ

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.

Got it! But why there won't have another method to construct a solution while m doesn't divide all values in the set

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.

Got it. thanks a lot.

Sir can you please tell me what your code did for the input -

2

1 6

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.

I got hacked in last 15 minutes :(

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.

1 -> 1 gcd(7) = 7

1 -> 2 gcd(7,35) = 7

2 -> 2 gcd(35) = 35

That's Wrong answer :/

When will you get the 5 then? gcd(7,35) = 7

Oops, my bad ._.

4 2 8 12 16

I really appreciate it

I used 3 18 27.

possible ans is 27 3 18. but most peoples code gave -1.

Was E computing scc and calculating for each scc and taking the max of it???

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.

10 hacks per second !

When u hack 14 but u know that ur own code is incorrect in 2 probs B) .

Problem difficulty: A < C < E < D < B.

D was definitely hard, but, come on, D < B?

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?

Notice that after you choose the numbers in the upper left

N- 1 byM- 1 grid, the rest of the numbers are determined. So the answer is 2^{N - 1·M - 1}. You also need to check the case whereN+Mis odd andK= = - 1. (Answer is 0 in such case).EDIT @below: Yeah, you're right, oops.

Do you mean 2

^{(M - 1)(N - 1)}?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 whenk= - 1 andn≡_{2}m. Otherwise you can show that there is no solution.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 ?

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.Thank you so much!

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.

Write brute force, build a table with answers, see the pattern :)

How to solve E?

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

This is exactly what I did but I got WA on pretest 3? Could you tell me what I is wrong?

Code: http://codeforces.com/contest/894/submission/32475892

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.

can you tell how do the output for third case is 16 ?

Here are the 16 possibilities.

Why not

-1 -1 -1

1 1 1

1 1 1

So, this is not a valid solution.

I am an idiot

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)log^{2}n) would pass. Isn't it almost 4 × 10^{8}? 2.5sseemed impossible.How do the output for third case is 16 ?

PROBLEM: B

Also wondering

Constructive algorithm:

total 2*2 arrays = 16,the parity bits can be inserted accordingly.

Authors thanks a lot for this Hack party! Very nice problems!

I had I idea to code Tarjan for E (still not sure will it work) but then saw so many wrong Cs in room.

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).

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

Well I think he means exponents... It's Fermat's little theorem. when p is a prime number

Authors should care more about the pretests, because there were more hacks than

Acceptedcodes on task B!-_-It's what we intended to do,we intend for a lot of hacks on B and C.

Why did I get this incorrect clarification? Is this how you intend for hacks?

https://imgur.com/a/7kuB4

Context: http://codeforces.com/blog/entry/55858?#comment-395984

Really sorry for this.I don't know who answered your question,maybe he is so busy answering questions that he made a mistake.

Not a Div.

2contest. B, C were too difficult.So, how to solve B? I can't think about it anymore :(

Backtrack on small N,M you'll find that the answer is 2

^{N - 1 * M - 1}Any intuition behind this?

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.

Clear explanation for B

how come some of the test cases didn't pass with that approach?

The extra requirement is that if k == -1 and n%2 != m%2, the answer is 0.

What's wrong with my approach to C?

For each starting position

iwe find the gcd until all positionsj(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

1 5 6 8

ans:6 5 8

I see now. The elements in the initial array don't have to be increasing order. Thanks!

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

Thanks. I unfortunately set a nonexistent constraint for myself :\

can you tell me why absence of 2 is neglected????

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.

you are not alone bro :/

HackForces~

Hack for C :

Answer is

What's the answer for this test case?

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?

You're missing the 3 between 18 and 24.

This is answer, because you need take

`gcd`

on segment, so`gcd(18,3,24)=3`

and all is correctYou 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.

Troll C-task easier then B. Good job, bro

Nop,after the systest maybe you'll change your opinion.

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)

Half of participants during the contest

It is a hacker's round...XD

When everyones gone AND you have to survive

everyone is dead, except YOU!!!!!

Can Anyone Explain How to solve Problem B

Problem C is a very nice trolling problem :D

How to solve D?

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

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.

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. :)

umm. could you please explain the persistent segtree part. I didnt get you exactly. Thanks

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.

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.

I query the segtree on the siblings of ancestors of U and not on any ancestor of U. Those subtrees are mutually disjoint.

Got it. Thanks

y u do zis

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 2lightning electrocuted me

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:

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:

So we get a conflict in the bottom right cell.

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.

Oops nevermind, I made a mistake. I put the last row wrong.

System test already done lol

Fastest ever

Almost nothing to test except A.

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

Diabolical test case for C (I guess):

4

1 3 15 20

Today, I had a bug

inside a bugin problem C whichsaved me from getting hacked!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

ntimes! :D Notice how the inner loop starts fromj= 1 and notj=i.One guy in my room had same situation :D

This is literally fight bug with bug

Room 110 (my room)

my code with scanf accepted but with cin it got TLE!

Not cool author! not cool...

Deleted

I am sorry but I couldnt see in D and E statements it being suggested.

Oops,my fault!I had suggested,but it was removed later. Sorry for not suggesting faster ways to input or output.

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.

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.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 :)

Wrong information. Deleted. Sorry for no max-size cases in pretests.

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.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.

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.

I agree that contestants who don't do such checks should generally blame themselves. Also, you are right that there are no rules about what pretests should contain.

It didn't affect me personally — this contest had no value for me, in ordinary div1 round there is at least a change of some colorful number in profile which is called "rating", and for div2 rounds even that reason to possibly feel bad goes away; so I don't feel bad about this contest in any way (unlike some other people here in comments, especially div2 folks who did it as rated event), and I actually think I had nice time participating in it — thank you for this round!

One thing which you are wrong about is "use custom invocation". Custom invocation has a limit of 256kb for file that you upload. So one can't really check maxtest for problems D or E there in some trivial way — because it is much larger. You can either put generator into code, which will not allow you to check I/O part (at best you can check only output part, for problem E it is just a single number — so not very useful), or test it locally, which generally requires you to create local environment which is as close to CF as possible.

P.S. I understand that it is possible to do something like "generate a test of size max.test/30, use it and multiply the result by 30", but it is not very precise and not trivial.Sorry for my wrong information. Someone told me we have max-size cases in pretests.

And have fun FST on Problem C. QAQ

I like the way of setting pretests and main tests ;-)

good job

Counter strike fan ?

yes

Less Codeforces, more Hackforces.

B was TOO DIFFICULT! Lol, now the correct submissions after system tests are in perfect order: A>B>C>D>E.

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.

B is pure evil!

Why time limits for first three problems are 1 sec? Usually its 2 sec.

The solution of the first three problems is very fast. So there's no need for 2sec

squirtle used used 'hard b and c' attack critical hit sandshrew fainted

Hi guys whats wrong with this http://codeforces.com/contest/894/submission/32469968

i am very sad i got the algo in contest but dont know why it got hacked

read my next comment

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 ;-)

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

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

No need.It's too complicated.We can calculate in this way:pow(pow(2,n-1),m-1)

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

Today's Round is the Proof of The First Law of Online Judges.

They are twince ! Hacked !

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.

For Prob C (Marco And GCD Seq)

Input:

15

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Ouput:

10

6 7 8 9 10 11 12 13 14 15

Why this is given wa verdict? (set of pairwise gcd of elements produced the input set)

You never generate any of 2,3,4,5 as gcds.

gcd(12,14)=2 gcd(6,9)=3 gcd(8,12)=4 gcd(10,15_=5

The gcd must be of consecutive elements.

You cannot get 2 using your output sequence.

gcd(12,14)=2

It needs gcd(ai,ai+1,ai+2,...,aj) So gcd(12,13,14)=1

because you can not find gcd 2,3,4,5 (i<=x<=j)

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 !

emmm……At first, my wrong B is skipped……

We will fix that.

Thanks

Can you please also take a look at my comment below? Thanks!

Dear Codeforces team,

I received this email few minutes ago: "Your solution 32459520 for the problem 894A significantly coincides with solutions MoodyFares/32459305, one_two/32460865, Redwan_hossain/32461143, Ali_Shehab/32461775, Hinke/32462032. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties."

I didn't cheat. I solved the problem in 4 minutes — it was super easy. I believe the system reported a similar code because people tend to use i, j, k — for loop variables; s — for strings; and ans — for the answer.

Please rerate my submission.

Thank you!

UPD:Even in the editorial you used i, j, k, s, and ans :)UPD2:The violation was removed. Thank you for the quick response!Mine too...

Amazing problems... Amazing system testing... Amazing Ratings Update.. Amazing CONTEST

the contest was bad. dumb weeaboo trash and weak preliminary testcases.

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.

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.

I think that a person can not understand the organizer until he tries to hold a contest.

Agreed. And his manner of expressing his disappointment was very immature too.

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.

Don't ever put a contest again ever are you sure that it was for DIV 2 ? really ?

I partially agree with you since problem B was at the level of task D. But everything else was excellent. It is my opinion.

I am disqulafied ,why????? My solution was by me . I am disagree with this decision

I think you should create a separate blog about your problem, because there will be more people there and the Administration of the

will see your appeal.Codeforcesreally terrible contest :/

very easy problems and shity codes

very very easy problem E and because of fast i/o 80% failed

worst contest ever with shity problems that sucks

Wow this is the hardest CF Round I have participated.

Why the ratings are altered again now?

maybe rejudging

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

Ohhhh!!

Hackforces Round!!!Really bad time limit for problem E due to big i/o

Input TLEInput ACD 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.

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).

C was such bait. Made the observation that the largest number in

Smust 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.

What the hell was this? the worst round ever. The worst problems ever! Go home.

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!

The problems where very interesting, But the pretest where weak that is why.

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.

Dear Codeforces Team, sorry being late because of exam, I couldn't reply. I got this email : Attention! Your solution 32466219 for the problem 894A significantly coincides with solutions codex0196/32463081, Uchchash/32466219. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. honestly speaking when I was in my first year of my BSc. I got a question about how many sub-string in a string question and at that time I had solved it exactly by the same technique, and really I haven't cheat, and the common way i used like a, b for two strings and a function count to count how many times the second string b can appear in the first string a. Please take my submission granted, Thank you.

My midterm exam is going on so that take too long me to reply, so sorry for being late. and another thing the time I mension in the comment of my BSc. 1st year was last year, 2016

Good Contest