include&lt;stdio.h&gt;

9 years ago, # ^ |

Hopefully not, last contest was dynamic and it was not rated (even if those two are not related)...

→ Reply

kursatbakis0

9 years ago, # ^ |

yes , all the problems will be about dynamic programming . ok

→ Reply

venki421

9 years ago, # |

Thanks for the problemset. Good luck to all! :)

→ Reply

9 years ago, # |

I can go to bed before the system test over!!!! Because my university will cut off the electricity at 11:30, and my computer can last for only 3 hours without outer-power! What nice news!

→ Reply

0o_o0

9 years ago, # ^ |

-6

mathlover is a super star in my heart,can I admire you?

→ Reply

loujunjie

9 years ago, # ^ |

In our university, The building #15 has electricity supply all the night so I can wait for the system test.

→ Reply

9 years ago, # ^ |

+27

Can I go to your dorm and code with you?

→ Reply

loujunjie

9 years ago, # ^ |

My dorm is very mess now... Maybe next time.

→ Reply

9 years ago, # ^ |

Never mind~

→ Reply

9 years ago, # ^ |

-15

How hard to study in China :D Economy))

→ Reply

wanxiaowei

9 years ago, # ^ |

This is just some of the rules of the school,because the contest time is at midnight in china,but there are still many hard-working students like mathlover got a red name.

→ Reply

lnever

9 years ago, # ^ |

+14

it is because of some fool schoolmasters and teachers but not economy...

→ Reply

9 years ago, # ^ |

Китайцы, успокойтесь!

→ Reply

9 years ago, # ^ |

please translate it to English~THX

→ Reply

I_love_Hoang_Yen

9 years ago, # |

+19

If I'm not wrong, this is the first round set by a Vietnamese! Good job! :)

→ Reply

1D726

9 years ago, # ^ |

I don't think so... http://codeforces.com/blog/entry/8248

→ Reply

ngfam_kongu

9 years ago, # ^ |

ll round =)) you're wrong :p

→ Reply

ErvinK

9 years ago, # |

← Rev. 2 →

+41

I have been wndering....how many languages does Delinur know?? :D

→ Reply

hzyfr

9 years ago, # ^ |

Usually, problem statements will be written in English, if the author wants it to be put in an international site.

→ Reply

PraveenDhinwa

9 years ago, # ^ |

← Rev. 4 →

I know don't the exact answer. But one day during a conversation, she said this "But I can translate your message into 4 other languages if you want :P". It means that she knows may be 5 or 6 languages or more.

→ Reply

kien_coi_1997

9 years ago, # |

22:00 is good time for me to participate. Thank you for your contest.

→ Reply

dht7166

9 years ago, # ^ |

You didn't even register for the contest

→ Reply

kien_coi_1997

9 years ago, # ^ |

I went to register page at least 3 times but failed to register because of some network problems. After coding problem B, I realized that I didn't register for this contest.

→ Reply

mirak94

9 years ago, # |

I hope codeforces won't be down today :S

→ Reply

symbolicConstant

9 years ago, # |

Countdown time and Announced time are Different. I am confused.

→ Reply

laoriu

9 years ago, # ^ |

Both of them are correct. Which announced time have you seen?

→ Reply

sbit

9 years ago, # |

← Rev. 2 →

I wonder will the time be at 18:00(MSK) in the future or 19:30(MSK) for mostly?

→ Reply

hzyfr

9 years ago, # ^ |

I hope most rounds are on 18:00 MSK in the future. That 1-hour switch has really some impact on us(Chinese).

→ Reply

9 years ago, # ^ |

...but 17:30 CET is too early for me, and you can guess what is my opinion about 16:00 CET...

→ Reply

9 years ago, # ^ |

I hope for 19-30(MSK)

→ Reply

Majid

9 years ago, # |

I think :
codeforces Round 277(Div. 2)== Happy Birthday contest !!(for MikeMirzayanov's daughter)!!:)

→ Reply

terminated

9 years ago, # ^ |

-35

bhut fikar hai tumhe mike mirzayanov ki beti ki .-- written in HINDI now translate it Delinur

→ Reply

Majid

9 years ago, # ^ |

← Rev. 2 →

please write in English!!
I can't read this comment.

→ Reply

gkeesh7

9 years ago, # ^ |

He said "Why are you so concerned about Mike Mirzayanov's daughter ?"

→ Reply

Majid

9 years ago, # ^ |

I like mike Mizayanov and him daughter. she is funny and smart and cute and ... daughter!!

→ Reply

gkeesh7

9 years ago, # ^ |

I just translated it Majid, reply to terminated .

→ Reply

gkeesh7

9 years ago, # ^ |

← Rev. 2 →

See previous Edit

→ Reply

Batman

9 years ago, # |

i wish we won't have hack or other problems in this round

→ Reply

9 years ago, # |

I bet that there will be one more blog post by DmitriyH after this round.

→ Reply

AkatsukiPain

9 years ago, # |

← Rev. 4 →

Punish him/her please! (S)he wants solution

→ Reply

Nodir.Daminov

9 years ago, # |

How to solve C ????

→ Reply

Lelby

9 years ago, # ^ |

+12

You always need to fix only a half of a string you are staying at.

→ Reply

alohamaloha

9 years ago, # ^ |

I did exactly that. Got WA on pretest 2. I am sure its a silly mistake on my part. :(

→ Reply

alohamaloha

9 years ago, # ^ |

Was a silly mistake... :(

→ Reply

Abinash

9 years ago, # ^ |

But How to do it by minimum operation ?

→ Reply

Lelby

9 years ago, # ^ |

← Rev. 4 →

Assume we are in the first half of a string. You are to find the segment which you must fix (leftmost and rightmost positions in the first half). Now you can choose the best way to visit all the segment, there are only two of them:

right - pos + right - left and pos - left + right - left

Of course, you also have to do min(abs(s[i] - s[n - i - 1]), 26 - abs(s[i] - s[n - i - 1])) operations for every i=1..n/2

→ Reply

prophet_ov_darkness

9 years ago, # ^ |

What if both left and right are on the same side of pos?

→ Reply

9 years ago, # ^ |

You can take the absolute values, giving

min(abs(right-pos)+right-left,abs(pos-left)+right-left)

→ Reply

prophet_ov_darkness

9 years ago, # ^ |

Well, my implementation ( 8656932 ) was a bit different. So I had to give that extra check, where both left and right were on the same side of pos. Lelby also gave that check ( 8659477 ), but he commented differently. That's where I got confused.

→ Reply

http://codeforces.com/contest/486/submission/8659287

9 years ago, # ^ |

You have to move from first char which needs to be fixed to the last one (or opposite way if shorter).

For example if number or fixes for characters in string aaaaacdefg is 0, 3, 4, 5, 6. Then if you are on position 2, you move to position 5, if in position 3, move to 2 and then to 5 and if on 3, then move to 5 first and then to 2...

→ Reply

Valdemar

9 years ago, # ^ |

We need to operate only with one half of string. Consider we choose left one. If p > n/2 just reflect it. Them found two indicies — 'l' first letter which need to change and 'r' — last letter which need to change. Minimum action for movement will be min(r-p,p-l) * 2 + max(r-p,p-l) if p inside [l;r]. If p is outside first we need to go in this range. Now we know how much ticks we will spent only on movement, during this movement we'll be on each letter. So just calculate cost of each change in range [l;r]. Result will be movement cost + change cost.

O(n)

I hope my approach is right :)

→ Reply

a_kabdygali

9 years ago, # |

+20

How to solve D ?

→ Reply

pavel.savchenkov

9 years ago, # ^ |

← Rev. 2 →

+10

Define root of a set as the node with minimum (a_v, v).

Now we can consider all the sets with that root (each of them will be counted once).

It can be done via simple dymanic programming.

→ Reply

ikbal

9 years ago, # ^ |

← Rev. 2 →

Take a fixed minumum number low then maximum value is low + d.

Find number of sub trees which has at least one node with minimum value and does not has any node that bigger then low + d or less then low. It can be done with dynamic programming in O(N).

Overall complexty is O(ND)

→ Reply

a_kabdygali

9 years ago, # ^ |

Thank you both very much! I've got it.

→ Reply

allllekssssa

9 years ago, # |

Why some people didn't get overflow in first problem when they calculated sum of first n div 2 even numbers and calculated sum of first (n+1) div 2 odd numbers?

→ Reply

mark03

9 years ago, # ^ |

I don't know. I made an unsuccessful hack because of this!

→ Reply

Nodir.Daminov

9 years ago, # ^ |

Same here :(

→ Reply

9 years ago, # ^ |

← Rev. 2 →

+15

It overflows, but both overflow the same, so when they subtract the overflow is gone. If you can find a case such that one overflows but the other doesn't (very unlikely and might not exist because 10¹⁸»10¹⁵), I think their solution will fail. I spent the last 15 minutes on W|A (Wolfram Alpha) trying to do just that, but haven't succeeded. A program would probably do it faster though.

EDIT: Actually I think now that even if one overflows and the other doesn't, subtracting them will again mean the overflow didn't matter. 281474976645119 makes one overflow and the other not, but it still works as the overflow is ignored.

→ Reply

adelnobel

9 years ago, # ^ |

Yeah I noticed this after my first unsuccessful hack :D

→ Reply

9 years ago, # ^ |

let's hope for system testing!

→ Reply

Zergrush

9 years ago, # ^ |

Apparently some solutions failed for the input "3037000499"

→ Reply

9 years ago, # ^ |

This doesn't seem to break one solution I'm looking at. Can you show me a submission that fails it?

→ Reply

Zergrush

9 years ago, # ^ |

This one fails (i failed to find this test in time). 8652729

→ Reply

9 years ago, # ^ |

Ok thanks. It's different because they find the sum of all numbers and subtract twice the sum of the odds, and since they divide by 2 after overflowing, subtracting no longer always removes the effect of the overflow.

→ Reply

contest1234

9 years ago, # |

How to solve problem D(problem D is very hard!!)?

→ Reply

creatnx

9 years ago, # ^ |

My sol is to DFS each note as that node is the max node, then use DP.

→ Reply

HandIeNeeded

9 years ago, # ^ |

← Rev. 2 →

Every valid set can be uniquely determined by the smallest node in it.(If there are more than 1 node has the smallest value, we choose the one who has the smallest id). So let's choose an node to be our special node, and starts to dfs under the limit that our special node has the smallest val and smallest id and the gap is no more than d. We get a sub-tree of the original one. And considered sub-tree, You can use dp to count how many way you can choose a set which contains the root (our special node)from the sub-tree.

It's a classical dp problem on trees. dp[node] means the ways to choose a set which contains the root and the others node come from the sub-tree of it. And you want to calculate dp[x] for the the node x, you just go through his son, and we can either not choose the part from this son's sub-tree or just take it, which has dp[son] ways. So in total (1 + dp[son]) ways. Multiply the sons choices up. And we get the ways to choose a set from the sub-tree of x which contains the node x.As we can let every node in the tree to be our root(special node), we can get the answer for the question.

Check my code hope that helps.

→ Reply

9 years ago, # |

A was easy, B was interesting, C was time-eater and interesting too.

→ Reply

Sehnsucht

9 years ago, # |

+157

+100 to persistency

→ Reply

9 years ago, # ^ |

nice

→ Reply

aangairbender

9 years ago, # ^ |

+28

Wrong answer on test 156... :D

→ Reply

Sehnsucht

9 years ago, # ^ |

You scared me great ... Luckily there are only 40 tests!

→ Reply

Batman

9 years ago, # ^ |

:D did you get any point from this question?

→ Reply

9 years ago, # ^ |

I did the same thing recently. But I was submitting my OK solution to A LITTLE DIFFERENT PROBLEM and got AC after 30-40 changes.

→ Reply

9 years ago, # |

+15

Ban Samsung please.

Translation: he asked me to send him solutions of A, B and C

→ Reply

Suleyman.A

9 years ago, # ^ |

wow the request is so interesting

→ Reply

9 years ago, # ^ |

this site has no report system?

→ Reply

9 years ago, # ^ |

Nope.

→ Reply

9 years ago, # ^ |

-8

Did you sended him smth? No? There is no reason for ban then. Yes? Then both should be banned.

→ Reply

omtcyf0

9 years ago, # ^ |

← Rev. 2 →

I don't think temak would've asked to ban him if he has sent something o_o

→ Reply

9 years ago, # ^ |

It's very same situation as — "You got SMS message: 'Mom! Please, send me 300$ to X-XXX-XXX-XX-XX I'm in big trouble!!!'. You can ignore it, and then there is no criminal. But it's possible to find the owner of this number, send the money and then arrest him, because his attempt was succesful". So there is no chance that Samsung will be banned, because solution wasn't sent! But still, temak posted this image and waiting for something.

→ Reply

inspirer

9 years ago, # ^ |

-6

that's why Iphone better than samsung:D

→ Reply

9 years ago, # |

how to print negative number (A problem) from squee_sp00n's A

if(n&1){
			cout<<"-"<<n/2+1<<endl;
		}else{
			cout<<n/2<<endl;
		}

→ Reply

ikbal

9 years ago, # |

← Rev. 2 →

It seems that nobody solved E using large prime modulos like me.

What was the intended solution?

→ Reply

pavel.savchenkov

9 years ago, # ^ |

I solved it in that way :)

→ Reply

creatnx

9 years ago, # ^ |

← Rev. 2 →

I think it is to count the number of indexes belong LIS of length i :) If there is only one index of length i then it must be type 3, otherwise type 2.

→ Reply

9 years ago, # ^ |

Could you explain what do you mean by "large prime modulos" ?

I solved it simply using segment tree for some calculations.

→ Reply

zeulb

9 years ago, # ^ |

-8

Quite surprised there's an antihash testcase for 2^64 modulos :|

→ Reply

I_love_Tanya_Romanova

9 years ago, # ^ |

While constructing testcase for string hashing is not so easy — hacking similar solution for this problem is very easy (and it is well-known olympiad problem). Just take a look at sequence 2 1 4 3 6 5 8 7 10 9... How many LIS it have? :)

→ Reply

zeulb

9 years ago, # ^ |

-8

Yes, i realize it's not hard to make such testcase, my bad for assuming anything modulo something is hard to hack :)

→ Reply

abdalimran

9 years ago, # |

-8

Will the contest also be unrated as the past contest???

→ Reply

mark03

9 years ago, # ^ |

No :)

→ Reply

rr_

9 years ago, # ^ |

Don't think so. Last one was unrated because of problems with servers etc. Rankings are just always updated few hours after the contest.

→ Reply

9 years ago, # |

+22

Sigh

Top4 are once again unrated, two of them registered in the past 24 hours. I'm not saying they are cheaters, but that happens way too often lately :\

Awesome problems by the way, solved all 5! Thanks, author :)

→ Reply

restart.

9 years ago, # |

← Rev. 2 →

why getting wa in test case 16 in 486A - Calculating Function .. my soln 8655625 it gives correct output in my compiler

→ Reply

Valdemar

9 years ago, # ^ |

Overflow problem. N can be 10^15 so N*(N/2) will be something like 10^29. You can read this comment, to understand why it may work on you compiler http://codeforces.com/blog/entry/14672#comment-196477

→ Reply

bharadwaj75

9 years ago, # |

-34

I HAVE A COMPLAIN IN CONTEST IT SHOWS PRETEST NOT SHOW WRONG OFTER CONTEST ITS SHOWS WRONG ANSWER WHY YOU WOULD NOT SHOW AT THAT TIME?

→ Reply

nam2012abcd

9 years ago, # ^ |

+23

Welcome to CodeForces :D

→ Reply

9 years ago, # ^ |

PRETESTS =/= TESTS, obviously.

This is the format of the competition. Your solution is tested on some part tests that usually do not cover all corner cases and maximal constraints. After the competition your solution is graded on the official tests.

→ Reply

kmamp

9 years ago, # ^ |

pretests are a very small fraction of the entire test

→ Reply

determinism

9 years ago, # ^ |

← Rev. 3 →

I don't know the exact reasons, but if I need to guess, there are probably three reasons for that:

1) Because of pretest/test separation, there's less need of computation while we're in contest; that's why we can get faster feedbacks.

2) It's much more exciting and fun to wait for system testing to see your actual results.

3) Hacking mechanism is based on this feature; this is also related to second reason since hacking is fun.

→ Reply

bharadwaj75

9 years ago, # ^ |

-31

what a joking u its not fun always you show wrong answer at contest but today you cheat me it;s not fare.I wana my full points its your mistake not mine otherwise i'll never participate in your contest

→ Reply

9 years ago, # ^ |

+81

→ Reply

J4T8Z9

9 years ago, # ^ |

What's going on in your head?

→ Reply

9 years ago, # ^ |

This is not your first contest, right? There are few tests when you submit, but all tests are tested during system tests...

→ Reply

-O2

9 years ago, # |

-24

this contest is unrated ?

→ Reply

9 years ago, # ^ |

Why are you asking?

→ Reply

-O2

9 years ago, # ^ |

-7

for Funny :D

→ Reply

Dixtosa

9 years ago, # |

+36

that My_First_Lady seems to have used different templates on C and E. and submitted C after E in two minutes.

just saying.

→ Reply

9 years ago, # ^ |

Yes, that's very suspicious indeed. Sadly I've never seen anyone banned for such reasons which is why we have tons of unrated accounts and/or teams ruining top5 of Div2.

→ Reply

bharadwaj75

9 years ago, # |

-53

see this two code for 1'st question whats differnt.

include<stdio.h>

include<math.h>

int main() { unsigned long long int n,i,j,k; scanf("%lld",&n); if(n%2==0) { i=n/2; k= i*(i+1); j=-(i*i); printf("%lld",(k+j));

} else { i=n/2; k= i*(i+1); j=pow((i+1),2); printf("%lld",k-j);

}

} 2.

include<stdio.h>

include<math.h>

int main() { unsigned long long int n,i,j,k; scanf("%lld",&n); if(n%2==0) { i=n/2; k= i*(i+1); j=-(i*i); printf("%lld",(k+j));

} else { i=n/2; k= i*(i+1); j=(i+1)*(i+1); printf("%lld",k-j);

}

} but first shows wrong answer and second shows correct answer what the difference between them

→ Reply

kmamp

9 years ago, # ^ |

+18

...

→ Reply

lebedkin

9 years ago, # ^ |

In case the guy really doesn't understand smth and not trolling: The first programs uses pow function (http://www.cplusplus.com/reference/cmath/pow/) The declaration of this function: double pow (double base, double exponent); — that means result for even integer numbers could be 255.99999999999 instead of 256 since for float(double) numbers those values are pretty same. But here j=pow((i+1),2) you're doing cast to integer. So result could be 255 instead of 256 and no one can guarantee which one exactly.

→ Reply

venomous

9 years ago, # |

Most of the solution failed test case 31 and 39 for problem B. They didn't know when to say NO :P

→ Reply

9 years ago, # ^ |

+10

We're lucky that we don't need to output "START" / "STOP". Most of us don't know when to say "STOP" :D

→ Reply

a.lammoth

9 years ago, # |

Heh, had solution for C, but just assuming that there's only one turn, not that the cursor always remains in the first half. Much more complicated to write that way : S

→ Reply

gauravbansal20

9 years ago, # |

codeforces should try to improve their website performance during contest..

→ Reply

9 years ago, # |

← Rev. 3 →

8652439 Why can this solution for problem A can pass all the data? It is an O(n) solution!

→ Reply

ItsLastDay

9 years ago, # ^ |

+11

The loop

for (int i=1; i<=n; i=i+2)
 s=s+i-i+1;

is so simple, that compiler (with optimizations on) turns it into

s = s + n / 2

because loop is really just incrementing s by 1 on each iteration, and we know precisely the number of iterations. Thus it becomes O(1) solution.

→ Reply