Soon (on October 24, 21:00 MSK) you are lucky to participate in Codeforces Round #275 for both divisions. **Pay attention to the round begining time!**

Problems have been prepared by team Saratov SU #3 with members: Gridnev Vitaly (gridnevvvit), Danil Sagunov (dans), Roman Kireev (RoKi).

We want to thank Max Akhmedov (Zlobober) for help with preparation of this round, Maria Belova (Delinur) for translation of statements and Mike Mirzayanov (MikeMirzayanov) for marvelous Codeforces and Polygon systems.

Scoring system:

**Div1**: 500 1500 1500 2000 2500

**Dvi2**: 500 1000 1500 2500 2500

**UPD**:

Contest finished, congratulations for winners!

Div1:

Div2:

how to solve the div2 D,please help me

I am really sorry to say but some of your previous contests english translation was quite really bad to understand . If possible please provide explanation of test cases . Hope this time everything will be fine and everyone will enjoy it :)

first round after my 1700+, gl & hf!

And I hope that my first Div. 1 round will be on the next contest...

Same here ;-)

Sherlock comix in prevous edit.

This is probably some hella smart & funny joke, but I just didn't get it.

I'm not sure, but active CF users who watched "Sherlock" should understand the concept (at least).

Waiting for Sherlock's new season...

make sure that better than waiting game of thrones cause everytime who reads books, s\he gives spoiler

Still better than watching Persona 4 before completing it, it completely messed up my wish to grind the exp to just know that Teddie is a actually a person :O.

Ralor awesome :D one of the creative comment post i have ever seen here :D

Thanks!

I wonder what colour Sherlock and Mycroft would have on codeforces, if they were real and were programmers.

I just hope that the round won't be "boring" :))

Whoa the round is at midnight in my country. Overslept is not an excuse.

Sleep is for da weak.

I want to participate in the contest very much!However,it's at 1 a.m in China,we must stay up!

thank you!your problem is hard or easy?your contest has very good problem .!

Please short explanation for problems.

Also explanation of sample tests.

" THANKS FOR READINGwow I'm so happy there are so many new contests on CF these days. Hopefully this pace won't go down in the future!

If the time is corrected, Some of Chinese Coders may start coding from 1:00 a.m. to 3:00 a.m. and waiting the system test until 3:30 a.m. Then sleep for a while and participate the regional warm-up contest. The next day(Sunday) participate the regional onsite contest for 5 hours. What a Fighting weekend.

Definitely no Chinese coders will compete in this round if they are going to participate in ICPC regional just on next day. They just need good rest.

Good night~ wake up at 00:30 a.m.

So admirable！

Alas, I (Chinese coder) really want to compete in this round, though I will not participate in ICPC regional, just the point is that our dormitory's blackout and my laptop can't afford to complete this competition …… ╮(╯▽╰)╭

If only the round beginning time would be advanced to regular 19:30 MSK suitable for most participants.

Where do i go to register for the contest. not allowing me to do so

Wait for a few hours.

you are such a fool and person

He certainly is a person, no arguing with that :D

I'm sorry.

sepehr103 wrote this comment when I was logged in the PC in the class

Any particular reason for the unusual timing of the round ?

Timing is perfect for me again, thanks ;-) 19:00 CEST, typically it's 17:30 which is too early to be finished at work...

@gridnevvvit Your last round was a DIV2 round and the round you arranged before it was a DIV1 round . so , it's good to see you coming back with a DIV1 round once again :)

Smiling:)

Omg the starting time of the contest is coincides with my sleeping time :))

Unfortunately, sleep was delayed because it coincides with codeforces round 275. here is the new time

There has been a lot of math in recent contests! Hope for something algorithmic! :D

First Div. 1 :) Gl & Hf everyone

and your first Div1 has no 1000pt problem :D

I dont understand why this congruency works sometimes :

Scoring system will be announced later== Registrations are closed 5 minutes before the round. Why delay it so long as in few minutes before the contest? Why delay it anyways?? Any specific reasons that I dont know of?Suspense :D

How to Solve division 2 Problem-:B ?

i think with binary search

i solved it recursively. consider lower bound of allowed numbers to be L. the absolute minimum numbers you need to consider is cnt1+cnt2. so you look at numbers from the range [L,cnt1+cnt2+L-1]. the numbers divisible by both x&y cant be gifted. from the remaining numbers those divisible by x were gifted to second frnd and those divisible by y were gifted to first friend. now the numbers left can be gifted to either friend.After some thinking you can argue that they should be gifted to first friend and if some are left even after that then to the second. the arguement for this is based on the fact that x < y.i am sure you can think of it :). after updating cnt1 and cnt2. apply the process recursively with new lower bound as cnt1+cnt2+L (i.e. upperbound of previous process +1).

I tried a solution like that but it wasn't working for me. I ended up using the fact that for any choice of v, there will be v/x multiples of x, v/y multiples of y and v/(x*y) multiples of both x and y (since x and y are unique primes).

You can figure out how many free choices you have left and increment v accordingly.

my solution wasn't accepted, either the logic is faulty or my implementation.

How to solve C DIV1 problem ? . Thanks in advance.

How to solve Div-1 A ?

The first (n — k) numbers could be 1,2,3 ... (n — k) after which we print n, n — k + 1, n — 1,n — k + 2 .... for the rest of the numbers.

First, follow a pattern 1, n, 2, n-1, 3, n-2, ...; do it k-1 times. Than add remaining numbers in the natural order (decreasing or increasing depending on k's parity).

I printed 1 and then printed p=1+k, then decreased k by 1 and then printed p=p-k and continued the series. Like, if k=3 and and n is anything arbitrary for an instance, I printed 1 4 2 3. Notice the difference in each adjacent values. And in the end I printed all the remaining values less than n.

That one's pretty easy. The task asks you to find some array of length

`n`

so that the amount of absolute value of differences of each two consecutive elements is equal to`k`

.I did it that way:

And if we are about to print the

`(k+1)-th`

number we just print our`latest number (- OR +) 1`

which will make it look that way:As you have probably noticed if

`K mod 2 is equal to 0`

then we print our`latest number - 1`

. Else:`latest number + 1`

.Pretty easy solution and easy to write down, work time: O(n)

edit: whoops, i think i'm late for a party

Not accepted yet, but I think it will be so... :) With first k elements You just can generate something like this: 1 1+k 2 2+(k-2) 3. Every needed difference will be here, k = |1+k — 1|, k-1 = |2 — 1+k|, k-2 = |2+(k-2) — 2|, k-3 = |3 — 2+(k-2)| ... And now, after that, just write the rest, n — k elements, one by one: 1+k+1 1+k+2 1+k+3 ... n-1 n. Difference between 1+k+1 and previous element is for sure not greater than k since k>=1 and previous element has to be between 2 and 1+k. Sorry for my English :)

EDIT: Aldiyar explained similar solution much better in his post, but it wasn't there when I was writing mine, sorry for doubling answer :)

for the C div 2 Problem I made the required sequence as -

n n-k n-k+(k-1) (n-k)+(k-1)-(k-2)...till k-i equals 1 and then following left over terms would be placed in decreasing order.

eg for n=6, k=3; 6 3 5 4 2 1

eg for n=15, k=7; 15 8 14 9 13 10 12 11 7 6 5 4 3 2 1

So guys what do you think about the difficulty level of div2 probs?

A-As Usual Difficulty. B-Very Much tricky. Perfect Problem who loves math. C seems easier to most of the div2 contestants but I got lots of pain and still not sure if it will pass. D was an awesome problem. No Idea how to solve it. E- I saw factional output — pressed ctlr+F , looked for a word "expected", found it and immateriality closed the tab.

How to solve problem B of div2 ?

Binary search

can you please explain the some more, i used a different approach and would like to know how to do it with binary search :).

All you need to do is to see if a particular N (1..N) can be split into the 2 sets. Let S1 and S2 be the sets for friend 1 (with prime x) and friend 2 (with prime y) respectively We can observe that in a set we can put the multiples of other prime.

S1 = {all multiples of y — multiples of x*y} S2 = {all multiples of x — multiples of x*y} The elements that can go in either sets are: Remain = N — multiples of x — multiples of y + multiples of x*y

So just check if using Remain you can satisfy the deficiency in S1 and S2.

http://codeforces.com/contest/483/submission/8395374

Bad, it is mathematics.

Relevant profile picture

thx

How was Div2 B supposed to be solved?

I solved it using segment trees (sadly after the contest).

Initially set all the values to 0 and the if a query(L,R,V) comes, update all the values in the range(L,R) with (

`a[i] = a[i] | V`

where L <= i <= R).while joining nodes in the segment tree do

`seg[node] = seg[2*node] & seg[2*node+1]`

and finally check for each query_range whether the bitwise and (&) of all the values equals to the required value i.e check`value(L,R) = V`

. This got AC .He was asking about Div2 B, not Div1 B :D

sorry, seems i commit mistakes even after the contest.

I wanted to know how to solve Div1 B as well :P So, thanks :)

Some people used binary search, I did not. My approach is as follows:

1.Set the answer=cn1+cnt2 initially.

2.Then you can fulfil the requirements of the first friend by giving the numbers to him which are not acceptable by the second friend and vice versa.

3.Let the friend with more requirement of numbers be friend1(cnt1>cnt2).Then you can give the numbers in the range [1,answer] not already given to any of them to friend 1. Then if his requirement is done you can give the remaining numbers to friend 2.

Code http://codeforces.com/contest/483/submission/8394005

i solved taking a long long a = cnt1+cnt2, & then checking if a — (a)/(x*y)>= cnt1+cnt2; if false, then a+=(cnt1+cnt2-(a-(a)/(x*y))), and so on. becouse the numbers that are multiples of x*y cant be taken as answer in any of the two cases. You have to check in the same way if there are enough numbers int the interval that aren't divisible by x, and the same whith y.

Is that working for

`3 1 2 3`

input?but the result is 5 — it was first input from problem statement...

I think 1 sec for B and C is too strict.

Totally agree, especially if you submit in Scala :(

In C, it's necessary to kill off

O(nm2^{m}) solutions.But unfortunately some of them have passed:(

it is not necessary, it can be made greedy

Yes, I got TLE just because of using scanner in Java instead of buffered reader. 2 seconds would have been better

so the author thinks that div1 B as hard as div1 C ?

I agree.Let's hope that no source with correct idea will get TLE.It wouldn't be nice...

Yeah.The hope is not enough...I took TLE with my 2^m*n complexity which works much better in practice.If this was the official complexity, than that limit is too small.In the other case, the pretests are not good(nobody took TLE on pretests)

There are sources which pass the tests and have 2^m*n like mine, so, anyway, the time limit should be bigger for letting the sources which are not optimized at maximum to get AC to...the problems were very nice anyway.

Accepts for C is more than B in DIV2 :D

I dislaked A — div1 very much. f*ck math.

no math lol

well, unnatural mathematical constraints.

I don't think that's considered math? At least to me it seems like simple logic.

Too fast SysTest . Hope Rating update will also be this fast :D

I could not optimize C in time. Unfortunately it works 1.2 secs at worst case :(

UPD: Thank god, codeforces faster then my pc. :D

You can use Custom invocation to see how long it would take on their servers.

Not sure if I'm stupid or just bad at constant optimization — is a 50*20*2^20 solution supposed to pass for div 1 C?

My 50*2^20 got TLE, so I'm guessing no.

If so then 1s TL is not enough for such tight constraints.

Bye Bye div1 :(

In what world are B and C the same difficulty? :D

I'm curious what the hell did the author think

Maybe it was meant to work in 50*20*2^20 =(

We did not notice, that idea of solution with working time

O(len·2^{len}) (len= length of strings) is too hard.Well then 1s is a horrible time limit. And even so, I think the problem is still harder.

You maybe mean "C and D".

No, I meant that the author gave 1500 for both B and C while the results show their complexity to be

slightlydifferentIn general, it's hard to evaluate problem difficulty once you know the solution (especially if you wrote it and tried a few variants).

Hmm, but there are three authors... Typically, getting a couple of others to test a problem gives you a good idea about the difficulty...

True that it is hard, but except the three authors there is usually a tester/helper (I guess Zlobober in this case) who should detect such miscalculations.

I'm really curious of the solution, maybe it does look simple once you know it.

Actually I found a way to improve my 50*20*2^20 solution to 20*2^20 fairly easily, but the explanation would be pretty long. The solution is that if X is a set of questions, then DP[X] is the average of DP[X|(1<<i)] for all i that aren't in X, plus the number of strings that can't be distinguished by that set of questions.

No, B and C. They were worth the same number of points, and the actual gap in difference is dramatical.

Οhh sorry. Misunderstooding :D.

Not only that .This is the condition in DIV2 ->

Yep, serious mistakes in complexity predictions. I guess it would've been really good to use dynamic scoring if the authors weren't too sure .

Good bye Yellow!

Wow, a lot of systest fails and hacks in C. I'm wondering if most of the failed submissions mixed up string length and n somewhere.

WA22 is the case

n= 1. My solution printed 1 while the answer is clearly 0. I saw lots of solutions which failed this test.Ok, this seems like a problem with a high probability for cheap mistakes. Not that I'm complaining. It is the only reason why I got such an unprecedentedly good (for me) result.

This contest was some difficult then other contests! Are someone explain solution of div 2 B problem??? please explain! (sorry for bad english !)

Binary search the answer..... to check whether we can distribute the presents between the friends using a certain v, we can use inclusion-exclusion. this might help : there are exactly n/p numbers between 1 to n which are divisible by p.

hope it helps.

8387870 Why my submission is skipped ?

Only the last "Passed pretests" submit is counted.

it was the only submission .

wasn't! 8387870 and 8393488

because you cheated it

No i didn't cheat

What was the expected time complexity for problem C?

I had O(N * 2 ^ string length)

O(L*2^L) as mentioned in a comment above. Turns out the idea behind such solution is way harder than authors thought. I think O(N * 2^L) also passes, but most of the solutions were something like O(N*L*2^L) and failed.

L — string length

I had tried to use unsigned long long and cin>> in D2B problem, but on my system it was wrong, signed long long works properly. Anybody knows why it may be?

Testcases in div1 C seem to use CRLF line feeds (not LF). I think it is unusual in Codeforces.

Can any one please explain how to solve Div-1 B ?

interesting for me too, after ends I wrote O(2*m*n), so TL.

I used segment tree to find possible answer and another segment tree to check that answer is correct.

Segment tree with updates on segments. 8393603

ohh, i think like adamant , feeling proud of myself :P

For each constraint ... We iterate over the bits of q ... if the ith bit is turned on ... then it means that all elements in the range (l,r) have this bit turned on as well ... else if the ith bit is turned off ... then it means that at least one element in the range(l,r) has this bit turned off.

So for all the turned on bits ... We turn on this bit on all the elements in range(l,r)

After that for the turned off bits ... We check that the range(l,r) contains at least one position where this bit is turned off.

We can use either segment tree or cumulative sum and binary search to implement this idea.

WoW! Amazing!

Can you please explain this statement — "We iterate over the bits of q". What is q here?

The same q in the input description.

The value for each interval

Can anyone please tell me why WA at test case 24 for problem c div 2 . code i handle the condition k == 1 then print ( i + 1) . whats going wrong here .

you used sync_with_stdio(false) and printf together , which will do unexpected thing

ThanQ BUET_moinul_10 :)

Rating has been updated.. time to press F5!

anyone who saw your comment must be already refreshed his/her browser.

So night before yesterday I got 4 hours sleep, I did 6 hours of exams yesterday and got < 4 hours sleep before this contest.

I went from 12th in last contest to 517th in this one.

Damn.

Spent whole contest trying to code D, and only now realized the solution is deceptively simple: note that the number of ways to color a subtree is the product of the number of ways to color each of its children, plus the same product for the reverse order. Or it would be, if it weren't for double-counting.

Turns out that the combinations that will be double-counted are the ones in which every painted subtree has an even number of painted vertices, or every painted subtree has an odd number of painted vertices and the number of painted children is odd.

Great Contest!! Finally above 1700

Btw, can anyone help me out with this http://codeforces.com/contest/483/submission/8393197

Problem D,div2

I tested it one ideone as well but it is giving runtime error there too.

I basically used bitwise range tree to solve the problem.Please help

Looking at number of TL's on C i realize how small is amount of coders who check their solutions in custom invocation before submit:)

Can anyone help me with my code for Div1-B?

My code: http://codeforces.com/contest/482/submission/8386444

I saw some solutions very similar to mine, but I am not finding any bug or seeing why my approach does not work.

Thanks.

SOLVED

First 4 minutes of contest: how I do programming and solving problems, screencast. [EDIT: now not private]

Video is private.

In Div 2 B, I didn't do binary search but derived a direct O(1) formula based answer and it passed. Here is my code : code. Is my solution correct or were the testcases weak??

10 7 3 5

your solution output — 17

right answer — 18

Testcases are weak.

can someone tell me how to solve div2 D????

http://codeforces.com/blog/entry/14387#comment-194124 http://codeforces.com/blog/entry/14387#comment-194131

Segment tree,I guess.

where is the editorial of the round ?

When editorial going to be published? In addition, very surprised to see that Division 2 B problem was much harder than C problem (by statistic)

Problem --> Interesting Array (CF Round 275): Div.1/B or Div.2/D

Tourist's code : http://ideone.com/c5dTmY

In this problem, for every set bit in query, we set the corresponding bit for all the numbers in the given range. I can't understand how he's doing that by:

s[from[k]][j]++; s[to[k] + 1][j]--;

Also, for calculating the number of set bits for a given bit position, for a given range of numbers, he's made some sort of cumulative array. Please explain its construction:

bal += s[i][j]; a[i][j] = (bal > 0); sum[i + 1][j] = sum[i][j] + a[i][j];

I will try to explain by posing a different problem:

Given

`m`

queries of the form`a, b, p`

; Add`p`

to each element between`arr[a] to arr[b]`

; Length of the array is`n`

.Trivial solution will do it in

`O(m * n)`

;To optimize, what you can do is, add

`p`

to`arr[b]`

. And add`-p`

to`arr[a-1]`

;Those two units of information is enough to let you know that you want to add

`p`

from`arr[a] to arr[b]`

.Keep on doing that for all m such queries.

Finally, do, something like:

So, just one final loop like above can add p to all elements between

`arr[a] to arr[b]`

for all such m queries.Complexity is:

`O(m + n)`

Try it on paper.

Thank you so much for you explanation!

became red :D

What's wrong with the editorial ? i can't see it now, but some days ago i can reading it.

translating maybe. the last time I saw the solution of two last problems were written in Russian

Why is the tutorial not accessible now? It was accessible a few days back..!!

You can read the editorial in the google's web cache : http://webcache.googleusercontent.com/search?q=cache:vSOKoA-5IqwJ:codeforces.com/blog/entry/14417+&cd=1&hl=es-419&ct=clnk&client=iceweasel-a

Thank you so much..!! :D

Only solved A，but rating +13.

Why am I getting TLE in problem B(div 1)? My complexity is 32*nlogn*3 which is approximately 6*10^7, that I think should pass in 1 sec. My code is here

Factor of luck

There is a wrong comment in a comment in a problem 1 Wrong comment: In the first sample pair (2, 4) is not coprime and pairs (2, 3) and (3, 4) are. correct comment: In the first sample pair (2, 4) is not coprime and pairs (2, 3) and (3, 4) are comprim.