### dzy493941464's blog

By dzy493941464, 6 years ago, ,

Hello everyone! Codeforces Round #FF(255) is coming soon! We invite you to participate in this round, the round will be held in both divisions.

In this round, the boy DZY appears again! As we all know, he loves many things. This time he also brings us many interesting problems, which are easier than the problems in last round, but he still needs you help. In return, he will present rating to you.

Many thanks to Gerald for giving us much advice and helping us to prepare the round. Also many thanks to MikeMirzayanov, who created such a wonderful platform.

The problem setters are jcvb, jiry_2 and me. This is our first Codeforces round :)

Come and join us in helping DZY again, and you will take the high rating home!

Good luck and have fun! :)

UPD

In Div. 1, scores for each problem will be 500-1500-1500-2000-2500.

In Div. 2, scores for each problem will be 500-1000-1500-2500-2500.

UPD

The contest is over. Thanks for participating.

Congrats the winners.

Division 1:

Division 2:

You can find editorial here.

• +198

 » 6 years ago, # | ← Rev. 2 →   +33 What round 255? You mean Codeforces Round #FF (Div. 1), Codeforces Round #FF (Div. 2), no? :D
•  » » 6 years ago, # ^ |   +44 Yep:)
•  » » » 6 years ago, # ^ |   +133 According to russian traditions, you need to say "Yept" instead of "Yep"
 » 6 years ago, # |   +49 easier than the problems in last round — sounds great! BTW, in last round every problem was solved by >=10 contestants, hard to believe that this time problems will be even easier. But if they do — it will be nice:)
•  » » 6 years ago, # ^ |   +55 Surely it will be :) Wish you high rating ~
•  » » » 6 years ago, # ^ |   +33 You were not serious about easier problems, right?)Thanks for interesting contest. I personally think that problems were a little bit too hard. First 3 problems are enough to get into top-5, and nobody solved E... You expected such results? Could you please tell us what was your prediction of AC range for every problem before contest?
•  » » » » 6 years ago, # ^ |   +11 We've compared each problem in our round with the round #254. And we think our problem is easier.T^T
 » 6 years ago, # | ← Rev. 3 →   +15 Hope this time problems could be more interesting than the last ones :).
•  » » 6 years ago, # ^ |   +43 We will try our best.
 » 6 years ago, # | ← Rev. 2 →   +10 if i remember correctly, in the last round most of the problems were about you. maybe now it is time for some revenge. ;) we will see.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 hope not to be in your room :D like TC srm :|
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +37 Having skilled challenger in your room gives some advantage on CF. It increases chances of your wrong solution being cracked during round so you'll have an opportunity to fix it and get some points (instead of flat 0 without that challenge).
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +18 well, i am certainly not a "skilled challenger". :Pi actually had to resubmit my 250 (which explains my low score of ~100) because i found bug in my code after i submitted. as it turned out, 4 others in my room also failed on the same case as my first submission.P.S. ofcourse, your point about having a good challenger in your room is true. :)
•  » » » 6 years ago, # ^ | ← Rev. 3 →   +21 LOL, but i changed nothing for you. your solution would have Failed System Test anyway. but ofcourse it changed something for me, i got +50 points for making it Challenge Succeeded. :)
•  » » » » 6 years ago, # ^ |   +6 but you should not have challenged the problem of a guy who wished you luck before the contest :P
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   +17 In that case. Best of luck everybody.
•  » » » » » 6 years ago, # ^ |   +1 LOL, nothing personal, as u know. :) in fact, i don't even look at the handle when i open code of participants in my room.
 » 6 years ago, # |   +40 Chinese(Hangzhou Xuejun High School) round again!
•  » » 6 years ago, # ^ |   +5 Looking forward to Raccoon Round :D
•  » » » 6 years ago, # ^ |   +8 you give me A Pretty Good Idea on setting a Contest！ Racoon Round may come soon~
»
6 years ago, # |
-44

# FF :) С юбилеем!

 » 6 years ago, # |   0 Early annovzbbsbsnxnnsnd...
 » 6 years ago, # |   +13 Seem that, DZY himself is the problem setter this time.
•  » » 6 years ago, # ^ |   0 Is it easy??
•  » » » 6 years ago, # ^ |   +18 It's obvious that the problems will be much more difficult than you've expected.
•  » » » » 6 years ago, # ^ |   -12 to khubi!
•  » » 6 years ago, # ^ |   +5 So cute profile picture :3
•  » » » 6 years ago, # ^ |   +14 If you meet xiaodao herself some day,you will find she is much more cute than the profile picture.>_<
•  » » » » 6 years ago, # ^ |   +9 What do you mean? Lol, I don't understand xD Anyway, now I have to meet her :D
•  » » 6 years ago, # ^ |   -84 WOW, super cute girl but sorry I hate China.
 » 6 years ago, # |   +15 Last time I didn't really enjoy DZY problems... Wish this time better than last time...
 » 6 years ago, # |   -8 Why Codeforces Round #FF(255) but not Codeforces Round #255 ?
•  » » 6 years ago, # ^ | ← Rev. 4 →   +25 because 255 is a very big and special number... It's the biggest number char(C++) or byte(Pascal) can hold! (UPD: thanks vas.and.tor, who points out my mistake that unsigned short contains 0..2^16-1... Fixed.)
•  » » » 6 years ago, # ^ |   +16 I guess it's "unsigned char" in C++. Biggest "unsigned short" can be around 32767.
•  » » 6 years ago, # ^ |   0 maybe this is why.
 » 6 years ago, # |   0 I like he also brings us many interesting problems and I like more which are easier than the problems in last round
 » 6 years ago, # |   +1 This is the first contest dzy493941464 hold. Hope him success in this contest
•  » » 6 years ago, # ^ |   0 Thx :)
 » 6 years ago, # |   +25 I think Div 1 E will be 3000...
•  » » 6 years ago, # ^ |   -15 That awkward moment when you don't even realize how hard Div 1 E is...
•  » » » 6 years ago, # ^ | ← Rev. 2 →   -32 Many people know that feel, bro.
•  » » » 6 years ago, # ^ |   +18 Ha ha. That's why I never read div 1 E..
•  » » 6 years ago, # ^ |   +4 NO 3000 but also NO 1000
 » 6 years ago, # |   +12 Crap. It's DZY again. I'm scared.
 » 6 years ago, # |   +11 You should also mention about the unusual time of this round so that no one might miss it.
•  » » 6 years ago, # ^ | ← Rev. 4 →   +2 It seems that the "Event Time Announcer" is wrongly showing this: Event Time in Moscow, Russia 5:00 While it's going to start in 17:00 (Likely a mistake --> 17 = 5 p.m) So its start time doesn't really differ from the last one ;)
•  » » » 6 years ago, # ^ |   +4 i think what m17 means is that most CF rounds start at 1930 MSK, but this one starts at 1700 MSK.
 » 6 years ago, # |   -14 easy problems are not good, because the rating matters how fast you solve the problems :/
•  » » 6 years ago, # ^ | ← Rev. 2 →   +43 Easier problems are good, because it matters how many problems you solve and not just how fast you can solve them.
•  » » » 6 years ago, # ^ |   +16 First of all sequence of problems should be without large gaps in dufficulty, so a bit stronger contestant may easier overcome weaker one by number of problems and not just by time — we are competing in solving first of all, not in typing speed, right? Otherwise there is no difference — "500 guys solved 3 problems, 20 guys solved 4+" and "500 guys solved 1 problem, 20 guys solved 2+" are almost same scenarios for me. As I mentioned in russian topic after last round, that round was pretty good — every problem was solved by 10+ users, nobody solved all 5 problems, number of AC is decreasing from A to E... And I compared that round with "standard 1/5/50/500 round" (talking about number of users with first 5/4/3/2 problems solved). In my personal opinion rounds like previous one are way more interesting than "standard 1/5/50/500".
 » 6 years ago, # |   0 a math round?
•  » » 6 years ago, # ^ |   +5 It's only a normal CF round. :) Wish you high rating ~
 » 6 years ago, # |   0 Hello, ladies and gentlemen! It's DZY's show time! :)
•  » » 6 years ago, # ^ |   0 I will get Violet
 » 6 years ago, # |   +5 As it is Ramadan, is it possible to shift the contest at least 30min ? Current Contest starting time is same as the iftar time here in Bangladesh.
•  » » 6 years ago, # ^ |   0 But great time in Iran! After the contest and system testings we have about 40 minutes to solve the unsolved problems and guess what after that! Iftar time! :) And it's similar for Russia! (But just for their international time! As you know, Russia is really long country and I think the difference between it's leftmost city and rightmost city is something about 9 hours! Russians correct me please).
•  » » » 6 years ago, # ^ |   +8 Russian timezones: from +3 UTC to +12 UTC exclude +5 UTC
•  » » » 6 years ago, # ^ |   0 In Morocco, we are 7 hours away from Iftar x) That luck though
•  » » » » 6 years ago, # ^ |   0 what is that iftar thing?
•  » » » » » 6 years ago, # ^ |   0
•  » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 I wanted to know a Muslim CF contestant's answer
 » 6 years ago, # |   -33 why is Codeforces Round "#FF" ? 0xFF = 255, maybe the Round #FF is the next of Round #254 ?
 » 6 years ago, # | ← Rev. 2 →   -16 That sounds Great! I hope it can be successful.
•  » » 6 years ago, # ^ |   0 Kime gerek sen
•  » » 6 years ago, # ^ |   -9 orz Mao Zhuli
 » 6 years ago, # |   -25 Who has a formulation for the third problem(buuble sort) for the TCO srm 627... Just the dp formulation and the recurrence relation pls?
 » 6 years ago, # |   +22 I can't participate to this contest because of the flight to IOI place.
 » 6 years ago, # |   -86 What does fuking FF mean?
•  » » 6 years ago, # ^ |   0 FF is 255 in hex (base 16)
•  » » 6 years ago, # ^ |   +13 fast finish
•  » » 6 years ago, # ^ | ← Rev. 2 →   -27 it's a recursive acronym. It means Fucking Ff
 » 6 years ago, # |   +13 I think the next contest will be "Codeforces Round #100" as: FF + 1 = 100 (base 16)
 » 6 years ago, # | ← Rev. 2 →   +10 hmm, really odd email i received from Codeforces. I'm glad to invite you to take part in Codeforces Round FF (Div. 1 and Div. 2). Actually it will be two separate rounds "Codeforces Round #254 (Div. 1 Only)" and "Codeforces Round #254 (Div. 2 Only)". firstly, there's no # before FF, which is usually always seen in all CF rounds. secondly, "Codeforces Round #254"? seriously?PS: take this as constructive criticism so that next time these mistakes can be avoided.
•  » » 6 years ago, # ^ |   +7 That means I'm not the only one. At least not the only one to notice :DMaybe an automatic mailing system got confused: "Which name is round FF supposed to have? Oh well, I'll just use the latest one."
•  » » 6 years ago, # ^ |   0 The round number is greater than 254. Codeforces rounds always have had number not greater than 254!
 » 6 years ago, # |   +24 Oh my god... this is last round... Next contest don't will... overflow byte..
•  » » 6 years ago, # ^ |   +7 No problem. Contests will start again from Round #0!
 » 6 years ago, # |   +11 Hello from Taiwan.thanks for our last chance to practice before IOI. Good luck and have fun everyone.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +3 be careful! you will be demotivated if you failed a round just several days before competition. It may bring negative effect to the competition.. haha (at least I experienced this once.)
•  » » » 6 years ago, # ^ |   +4 I already succeeded last topcoder round :D , I hope that I also succeed in this CF round.
•  » » » » 6 years ago, # ^ |   0 Ah OK then, at least you already motivated by something :)Anyway goodluck for IOI! :) It's very sad that I can't participate in IOI anymore :'(
 » 6 years ago, # |   +18 Please prepare a readable and thorough editorial. Thank you :)
•  » » 6 years ago, # ^ |   +4 I hate when it says 'The solution is obvious' Waiiiiiiiit Nooo that is why I am here x)
 » 6 years ago, # |   +3 For me, entering this round means not watching the World Cup Final. it's difficult trade-off...
•  » » 6 years ago, # ^ |   +5 No conflict between this Round and WCF ??!!! maybe you have no time for both
•  » » » 6 years ago, # ^ |   +15 yes, I have at most 4 hours to sleep, if I do both.
•  » » » » 6 years ago, # ^ |   +14 Who cares about sleeping if World Cup final is just once in 4 years?
 » 6 years ago, # |   +6 Soccer Maniacs wouldn't attend this round :v
 » 6 years ago, # | ← Rev. 3 →   +8 Score distribution is a bit strange for me. 500 from Div1 used to be equal to 1500 from Div2, I guess, 1000-to2000, and so on. Today task C from div2 costs 2000, but task A in div1 (which used to be the same with Cdiv2) costs only 500. But, according to the logic of previous rounds score distribution, it must be 1000. I understand, that authors know better, which one is correct, but isn't it a mistake?UPD: Changed to 1500
•  » » 6 years ago, # ^ | ← Rev. 2 →   -6 I think This time task A Div1 Equal task B Div2 My Guess is Div1 Div2 A = B B = C C = D D = Eso the difference between two rounds will be A Div2 & E Div1 maybe I'm wrong let us see
 » 6 years ago, # |   0 After do contest I will watch FIFA World Cup between Argentina and Germany
 » 6 years ago, # |   +1 div2 B shows 1000 in the contest.
 » 6 years ago, # |   +6 I...don't understand why Div 2 Problem A begins with "DZY has a hash table..." Do the problem writers actually expect Div 2 contestants know what a hash table is? (Div 2 contestants that can solve Problem D/E are okay, but how about beginning contestants that can barely solve Problem A?)Personally, this is approximately how I'd phrase it:DZY has p buckets, one of which is colored red. Each bucket can hold one ball. For the i-th ball, DZY starts with facing the red bucket and turns clockwise for x i buckets before putting the ball into the bucket in front of him. However, sometimes DZY cannot put a ball because the bucket he's facing already holds a ball. Output the number of the first ball that DZY cannot put.
•  » » 6 years ago, # ^ | ← Rev. 2 →   -14 There are alternative solutions for this problem without hashtable,We can do Vector Add numbers and Vector Add module for every number and every time , you must check , Are this number contains in this vector or not :) Hope it help
•  » » » 6 years ago, # ^ |   +5 I know there is a solution without hash table. (When I finished reading, I already got the solution using simple arrays.) However, the problem here lies on the wording. It feels like you need to know what hash table is (even if you eventually don't use it) just to understand the problem. My view is that problem wording should be as simple as possible, even if the solution can be terribly complicated.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +5 Here's a hopefully comparable analogy:You are given points on the plane, forming a polygon. It is guaranteed that the polygon has a dihedral group of order 8. (Test case has no picture of the polygon whatsoever.)You will most likely say "WTF" on the last sentence. Compare:You are given points on the plane, forming a polygon. It is guaranteed that the polygon will be symmetric like a square: when you rotate the figure by 90, 180, or 270 degrees, the polygon remains the same, and when you reflect the figure along some line, the polygon also remains the same. (Test case has a picture of the polygon, explaining the symmetries.)
•  » » 6 years ago, # ^ |   0 that's just a bluff :Pwe can see high number of accepted submission for that :)
•  » » » 6 years ago, # ^ | ← Rev. 3 →   0 In hash table, if you put more time one number than it is not collision, but in this problem it was colision :(
 » 6 years ago, # |   +3 In problem A (Div1), are we allowed to change the numbers to zero? E.g. what is the answer for sequence (1 1 2 3) — 3 or 4?
•  » » 6 years ago, # ^ |   +11 4 — why shouldn't 0 be an integer?
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Then I can't find an error in my solution 7083807 which got hacked =\
•  » » » » 6 years ago, # ^ |   0 I think n=1
•  » » » » » 6 years ago, # ^ |   0 Oh no(
•  » » » » » » 6 years ago, # ^ |   0 i asked this http://codeforces.com/contest/447, see below "Questions about problems"
•  » » 6 years ago, # ^ |   0 The answer is 4.
•  » » 6 years ago, # ^ |   0 and you also can change to negative number ...
•  » » 6 years ago, # ^ |   0 Yes, even you can change it to negative integers.
•  » » 6 years ago, # ^ |   0 According to the statement, you may change an integer to any other integer. Meaning that 1 may be changed for 0, -1000000000000, +1000000000000, 20 and -30 (even though some of this numbers are out of the the 10^9 value for array values given in the statement).
 » 6 years ago, # |   0 I tried hacking vatsalyarathod123 div2 C which should have given garbage value for N=1 but it returned correct answer I don't know why .
•  » » 6 years ago, # ^ |   0 If n==1 , The result should be 1 , because there are not any elements again in array,,Every number implies to length
 » 6 years ago, # | ← Rev. 2 →   +1 Hi, Can anyone please explain your approach of Div1 B / Div2 D ? Thanks.
•  » » 6 years ago, # ^ |   0 The mathematical proofs are maybe a little bit long but pretty intuitive. Obs.: 1) It doesn't matter in which order you do the operations. 2) You can let 0<=l<=k be the number of line operations (and take the best variant at the end). 3) For a fixed l, use 2 priority queues to calculate the results for l and k-l elements picked both for rows and columns. 4) Combine the result for l (on rows) with the result for k-l (on columns) with a little bit of maths. 5) Don't forget about long long.
•  » » » 6 years ago, # ^ |   0 Is this equivalent to the greed solution? In my solution, at each step, I would select the best row or column (the one with greatest sum) using two PQ. I don't know if greedy works (couldn't prove it), but it really feels like it should work. No idea why WA. :(
•  » » » » 6 years ago, # ^ |   0 I got WA on pretest 4 doing the same thing!
•  » » » » 6 years ago, # ^ |   +4 It doesn't work.2 3 6 1 1 1 1 1 1 1Sometimes you don't want to select the best row in order not to start getting negative sums.
•  » » » » 6 years ago, # ^ |   +1 It doesn't work. Consider 1 3 10 1 1 1 1
•  » » » » 6 years ago, # ^ |   0 i'm just guessing here, but did u consider that every row's sum reduces by p during every column operation (and vice-versa)?
•  » » » » » 6 years ago, # ^ |   0 Yes JuanMata. It looks like Greedy is a bad idea. (Greedy is almost always a bad idea. I will try to remember that next time) :(
•  » » » » » » 6 years ago, # ^ |   +1 Actually there is a huge greedy part in the solution. You just have to be sure when you are using greedy algorithm, you should have proof or something (maybe not very rigorous). The greedy part here is that if you look at choosing rows and columns separately, when it's about rows, it's always right to choose the largest row. Same hold for columns. Than it's easy to solve this 2 problems separately and merge them. You're gonna need to brute force how many rows you choose.
•  » » » » » » » 6 years ago, # ^ |   +1 Forgot proof of a greedy strategy. Choosing largest row is optimal, because: (1) The order of rows chosen doesn't affect the final score; (2) Assume in the optimal solution the largest row was not chosen. Then, swap the largest row with any other chosen row. Obviously the score will increase, hence contradicting the optimality of a solution.You can also prove that you can choose just rows at first and then choose only columns. I guess the details are already posted (at least in the editorial), so I won't go further into details.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +4 No, its not equivalent. You solve the problem for only rows and only columns separately, and then choose how many rows and how many columns to use based on these results. The key observation is that each row operation reduces the results of each following column operation by p, and vice versa, so the total score is ScoreRows+ScoreColumns-NumRowOperations*NumColumnOperations*p, regardless of the order in which you do the row and column operations — this is because for each pair of RowOperation and ColumnOperation whichever comes first reduces the result of the other one by p, and there is a total of NumRowOperations*NumColumnOperations pairs.
 » 6 years ago, # |   0 Can someone help me to understand why my solution for div 2 problem E is too slow to pass test 9?I use segment tree + lazy updates.Thanks.
 » 6 years ago, # |   +3 In Problem C, DZY Loves Sequences, I made a minor mistake of initialising a variable to 0 instead of 1. So naturally, it gave WA. But after correcting the mistake and trying to re-submit, it says that The exact code has already been submitted, and I could not submit it. How is it possible?P.S. I had saved the file.
 » 6 years ago, # |   +1 I am being hacked at 17:57:37, The Codeforces send me the Announcement at 18:59:25, and I am very surprised about this (so bad)
 » 6 years ago, # |   0 Sorry if this is a stupid question, but how long does it usually take before the ratings are updated?
•  » » 6 years ago, # ^ |   +1 It's not stupid! I've been asking this question from myself since i've been taking contests! It never has a fixed time. It usually takes half an hour before the system testing part and half an hour (or even more) after that for rating updates :)
 » 6 years ago, # |   0 my idea for C div 2 is split the sequence if it's not an increasing subsequence, and join with the neighbour if possible (change 1 number from sequence left or right, and made strictly increasing seq)here is my submission http://codeforces.com/contest/447/submission/7087449any other ideas or my idea wrong ?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 You can merge three consecutive segments(increasing sequences) also if the middle segment contains only one element and the first element of the right segment > last element of first segment + 1 .
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 hmm, cant think of test case for something like that while contestanyway, thx for the answeredit : my solution just lack +1 to the output if the max sequence isn't obtained from 2 sequence :)
 » 6 years ago, # |   0 can anybody explain me how to solve div-2 D . thnx
 » 6 years ago, # |   0 I encounter a strange issue during the contest. my ID became duplicate and every time I refresh my submission page its contents were different ! and when I locked my problem C ! (notice to contest time running!) and some seconds later : I deleted all my codeforces' cookies during the contest but still nothing were changed!what was the problem MikeMirzayanov?
•  » » 6 years ago, # ^ |   +4 I'll investigate it. Thank you. I'll exclude you from the rating. It seems somehow you were registered twice (race condition?).
•  » » » 6 years ago, # ^ |   +5 Yes, You're right. I have registered twice because I didn't see myself in registered users. Interesting racing condition!
 » 6 years ago, # |   -10 why is system testing unusually slow today?
 » 6 years ago, # |   +87 I will never believe in Chinese authors' word about easiness of the contest, specially of dzy493941464 :(
 » 6 years ago, # |   +15 Who's idea to make C and B same points. Oh, well done really, Solvers of B is 6 times more then C : 64 * 6 ~ 343
 » 6 years ago, # | ← Rev. 2 →   0 why most of div2 C submissions failed system tests ?can anyone give me the tricky test case which most contestants couldn't pass ?
•  » » 6 years ago, # ^ | ← Rev. 3 →   +1 I'm not exactly sure whether this is covered by pretests or not, but does your program work for 10 1 2 3 10 4 5 6 10? (Answer is 5; take indices 5 to 9 and change the middle 10 to something low. (Or indices 1 to 5.) You cannot change the middle 10 to 3.5 to take indices 2 to 8.)
•  » » 6 years ago, # ^ |   +2 I'll guess just some cases: n=1 the optimal subsequence takes 0 changes to make the changed element is the leftmost/rightmost
•  » » » 6 years ago, # ^ |   0 I missed the second point. :(Just added : if(!ans)ans=n;Became AC
•  » » 6 years ago, # ^ |   0 some forgot to check whether two segments of strictly increasing order are able to be merged or not, for example:6 1 2 3 3 4 5the two segments are [1, 2, 3] and [3, 4, 5]these cannot be combined to form one strictly increasing sequence.
•  » » 6 years ago, # ^ |   0 Try: 2 1 1 Answer should be 2
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 thanks all , I found the test case that my code didn't solve correctly51 2 10 4 5the correct answer is 5
 » 6 years ago, # |   +81 DZY definitely starts to please me.
 » 6 years ago, # |   +47 three people scored 1134 points, and they took the (joint) 254th position. this unfortunately means that nobody could take the 255th position in the 255th CF round. :(
•  » » 6 years ago, # ^ | ← Rev. 2 →   +15 What a very sad thing, you made me cry -_-
•  » » 6 years ago, # ^ |   +3 I hope you can recover from this horrible shock soon.
•  » » 6 years ago, # ^ |   +11 Let's see the good part of things — in the div2 contest we have: 255, 256 and 4 x 2048 placers.
 » 6 years ago, # | ← Rev. 2 →   0 I got tle on test case 9 in div2-Q5. I used segment tree. was that too tight for the time bounds?
•  » » 6 years ago, # ^ |   0 this is my code, possibly someone could suggest an alternative -> direct link
•  » » » 6 years ago, # ^ |   0 I have not tried the problem but maybe you could get the fibbonacci number using matrix exponentiation !
•  » » » » 6 years ago, # ^ |   0 i precomputed and stored the Fibonacci in O(n), and used it as a hash to get a direct access in O(1) while updating. I don't think that is the issue or m not sure.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Maybe problem with tree array size or recursion? When i downloaded your code and run it on simply test like this: http://morse.swirski.name/pastes/l6hriqm93kn5wx5gvxckznn0ibd5zvh program crashed in build_tree() function. When i change tree[] size i don't have this problem. But i'm not sure, cause it was on Windows 7 x64.P.S. Sorry for my english.
•  » » » » 6 years ago, # ^ |   0 if the solution did crash in build tree function, then it would had not run in that case. I checked the log and it seems that the tree was built perfectly but the program ran out of time while processing the M queries.
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Wait... your update is logarithmic? You stop recursion only when low==high (in leaf). So update is too slow in my opinion (You must visit every leaf in (l, r) ).
 » 6 years ago, # |   +3 Why DIV2 problem C's test 41: 6 7 2 3 1 4 5 answer is 4?
•  » » 6 years ago, # ^ |   0 change 3 to 0
•  » » » 6 years ago, # ^ |   0 thank you.
•  » » 6 years ago, # ^ |   0 Oh, I see.
•  » » 6 years ago, # ^ |   0 Correct segment for ex.: [3->0 1 4 5]
•  » » 6 years ago, # ^ |   0 After change, it can be "7 2 0 1 4 5". So the answer is 4.
 » 6 years ago, # |   -13 Nice contest :D
 » 6 years ago, # |   +11 Excuse me. But why my rating hasn't updated? I found that everyone's rating has been calculated but mine hasn't done.
•  » » 6 years ago, # ^ |   +18 Oh, sorry. Only Div.2 competitor's rating has been updated.
 » 6 years ago, # |   +17 You can view country wise standings here. Send your hugs or bugs here.
 » 6 years ago, # |   +33
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Yes, I really appreciate an opportunity to test my solution for WA/TL on spoj during CF round, but I don't think it is a good idea to give such problems on CF rounds.
•  » » » 6 years ago, # ^ |   +7 I am sure it wasn't on purpose. It's impossible to know all problems from all contests/online judges. And it seems that it is not so easy to google the statement of this problem.
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   +1 I am not sure that it is easy — did not tried to google this one, already seen it on SPOJ before)But now I tried to search for fibonacci updates array query problem and some other similar requests and both of these problems are at first page)
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +5 not so easy to google I wouldn't be so sure. Just keywords from the problem statement, plus where to look (I always add "online judge" when I'm looking for a problem without specific source competition).
•  » » » » » 6 years ago, # ^ |   0 Yes, you are right. I tried another search queries and failed to find this problem, but it is definitely not so hard to do this and authors should have do that.
 » 6 years ago, # |   0 Did anyone try to solve Div2 C using two pointers?
 » 6 years ago, # |   +40 Is the contest unrated for Div.1??? The rating of Div.2 was updated, but Div.1 not.
•  » » 6 years ago, # ^ |   0 It went well and there was no announcement, of course it's rated. It just takes a long time for some mysterious reason.
•  » » 6 years ago, # ^ |   +4 LOL, it's like this was a Div-2 only contest. :D seriously, i guess it's just a small system issue. i'm sure ratings will get updated soon. :)
 » 6 years ago, # |   0 What asymptotics should be in Div2-D? I had O(pk) (I hope) and got TL. Now I wonder is it too bad or just Python?
•  » » 6 years ago, # ^ |   +4 Should be O(k logn + k logm)
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Solution from editorial works in O(k * log(n) + k * log(m)); however, it is possible to do it in O(k * (n + m)) and fit into TL easily (7093794).Upd. This solution is wrong (i described problem here). But you still can pass system tests with it)) Changing long into long long to fix overflow issues will make it correct, but with long long it does not fit into TL.
•  » » » 6 years ago, # ^ |   0 Is long long that much slower than int? Is Codeforces on 32bit machines?
•  » » » » 6 years ago, # ^ |   0 Yes, it is ~2 times slower. You may change long si[12000],sj[120000]; into long long si[12000],sj[120000]; in my solution and it will work >2s.
 » 6 years ago, # |   +22 i'm hoping that the ratings of Div-1 will be updated before the World Cup final starts.
•  » » 6 years ago, # ^ |   0 i'm hoping that the ratings of Div-1 will not be updated
 » 6 years ago, # |   0 Why DIV2 C test 27 1 1 2 3 4 answer is 5 (not 4)?
•  » » 6 years ago, # ^ |   0 change first 1 to a 0.
•  » » 6 years ago, # ^ |   0 answer is (0 1 2 3 4) (i.e. make the change a 1 = 0).
 » 6 years ago, # |   0 Can someone tell me why this submission is giving Runtime Error?
•  » » 6 years ago, # ^ |   +5 vector hashi(p); for(int i=0;i
•  » » » 6 years ago, # ^ |   0 Aah..OK.I failed to notice this during contest :(
•  » » » » 6 years ago, # ^ |   -18 its very bad contest
 » 6 years ago, # |   +6
 » 6 years ago, # |   0 In question C. DZY Loves SequencesShouldn't the answer of (testcase #27) 5 1 1 2 3 4 be 4? Value of ai can never be less than 1.
•  » » 6 years ago, # ^ |   0 Read the problem statement carefully ... It says change one number to any integer you want.
 » 6 years ago, # |   0 I don't see why we need all the complicated logic in the editorial for Fibonacci problem. We can simply precompute the first 300000 values linearly and store them in an array.