### One_touch_finish's blog

By One_touch_finish, 4 years ago, ,

Hello Codeforces,

Manthan, Codefest 16 will take place on Friday 26th February, 2016 10:35PM IST with a duration of 2.5 hours. The round is rated and consists of 8 problems.

The Department of Computer Science and Engineering is conducting Codefest from 25th-28th February. Manthan( मंथन in Hindi, meaning Brainstorming), the algorithmic programming contest under the banner of Codefest, is being held as a special Codeforces round. The round follows regular Codeforces rules. The prizes for Manthan are being sponsored by Walmart Labs.

The round is prepared by One_Touch_Finish, mkrjn99, FoolForCS, IITianUG and code_note.

We express our heartiest thanks to GlebsHP and AlexFetisov for their help in preparing the contest and MikeMirzayanov for the awesome Codeforces and Polygon platforms!

### Prizes:

Don't forget to register for Manthan at our website also to be eligible for prizes.

Overall 1st place: ₹25,000 Overall 2nd place: ₹15,000 Overall 3rd place: ₹10,000

1st place in India: ₹15,000

1st place in IIT(BHU) Varanasi: ₹4,000 1st place in freshman year, IIT(BHU) Varanasi: ₹1,000

About Codefest: Citrix presents Codefest is the annual coding festival of the Department of Computer Science and Engineering, IIT (BHU) Varanasi, which is held online and is open to participation by all! Register on the Codefest website now! Free .tech domain for everyone who registers on the Codefest Website. Total prizes worth ₹450,000/- up for grabs with events covering domains from Math, Machine Learning Cryptography and Capture The Flag style competitions. Go to the Codefest website to find out more!

Update: The editorials have been posted: http://codeforces.com/blog/entry/43392

Announcement of Manthan, Codefest 16

• +196

 » 4 years ago, # |   +213 Regarding the prizes, I have a funny story from Manthan 2011 — five years back.The announcement promised cash prizes to the top participants, and I ended up second. The page with the exact distribution of prizes is gone already, much as the whole Codefest'11 site, and the announcement does not list the details. Anyway, the contest was on March 13, 2011, and the results of this Codefest'11 track were finalized on March 16.Then, in May 2011, it looks like no one got their prize yet (here is a relevant comment thread in Russian).Long after, on September 13, 2012 (one and a half year after the contest), an email was sent by organizers to the top finishers, where they explained that they had technical difficulties, but the situation now improved, and now they are able to send 25% of the prizes in Amazon gift cards, as well as scanned certificates of achievement. Now, Amazon gift card is not exactly cash, but nevertheless, they held to this one and indeed sent the gift card and the certificate after a couple of days.I haven't gotten any mail from them since, but who knows: maybe they will be able to send another 25% in a few years?.. The bottom line is, well, I don't actually expect to receive anything from the 2011 contest organizers anymore. But I really hope the 2016 organizers are more responsible.
•  » » 4 years ago, # ^ |   +94 Few days ago I received a T-Shirt from CodeChef for having a high place in a Long Challenge that took place at summer 2014. Hope that is not a common issue for Indian competitions :)
•  » » » 4 years ago, # ^ |   +37 Heh, I have not received any T-shirt from Codechef Cook-offs too! But that was also earlier than 2014. Maybe the situation improved since, or I am just not as lucky as you ;) .There were some Indian contests which actually managed to deliver some stuff to me (Bitwise comes to mind), so yes, it depends on the contest.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +25 Related: see Egor's comment about ByteCode 2016, which just happens to be another Indian contest.
•  » » » 4 years ago, # ^ |   +35 Let me add my two cents. Some time ago, there was a series of three AI contests hosted by HackerEarth (Indian company) named "Battle of Bots". What do we have now: Battle of Bots #1 (September 2015). I finished 4th, was promised a T-shirt, hasn't received it yet. Battle of Bots #2 (November 2015). I finished 8th, was promised a T-shirt, hasn't received it yet. IndiaHacks Bot Challenge (January 2016). I finished 15th, was promised the unknown gift voucher. Later it was announced that prizes will be awarded in May 2016. A little bit too long for a gift card, isn't it? :) Hope that is not a common issue for Indian competitions :) Unfortunately, you seem to be wrong :(
•  » » » » 4 years ago, # ^ |   +74 Hi, I am co-founder of HackerEarth. It's really unfortunate that you haven't got the t-shirts yet. We have very strict guidelines to ship t-shirts on time and work with an external vendor to ensure this. I am working on this issue and you will get the t-shirts and any other prizes asap. Let me know if there is anything else.
•  » » » » » 4 years ago, # ^ |   +31 By the way, when I finished in top 3 of some Codemonk contest I received a t-shirt from India Hacks in which I haven't participated :D It's not a problem, just pointing it out :)
•  » » » » » 4 years ago, # ^ |   +12 Also, just to mention, I have finished 3rd on Code Monk (Segment Tree,RMQ,Lazy Propagation) and haven't received the T-shirt yet.
•  » » » » » » 4 years ago, # ^ |   +8 Just a note, you may need to claim your prize, just look at your e-mail, I found that months after I got into top3 :D
•  » » » » » » » 4 years ago, # ^ |   +5 Just checked and I haven't received one.
•  » » » » » » » » 4 years ago, # ^ |   +8 I finished 3rd in https://www.hackerearth.com/code-monk-number-theory-iii/hof/Didn't get the T shirt :(
•  » » » 4 years ago, # ^ |   +16 I got mine within 3 weeks.. I guess it is an issue only for non-Indian participants..
•  » » 4 years ago, # ^ |   +103 Last year TooDifficuIt,zhj and I took part in IOPC2015 on Codechef and got the first place. But so far we still have not received the prize which they promised.
•  » » 4 years ago, # ^ |   +48 Hi Ivan, I'm sorry you had such a negative experience the last time you participated. I apologize on behalf of the Codefest 2011 team, and can assure you that this will not happen again. In 2011, Codefest had faced some very serious difficulties due to which it had to eventually shutdown the same year. The situation has changed a lot and after 5 years, we are reviving the event with a completely different organization team. I hope you will have a good contest this time around. Rest assured, all the prizes will be delivered to the winners in time. All the best for the contest. :)
•  » » » 4 years ago, # ^ |   +30 Well, better luck to the organizers this time! Let's hope they really know what they are doing.
•  » » 4 years ago, # ^ |   +70 It definitely is a common issue for "Superpower by 2020".
•  » » » 4 years ago, # ^ |   +15 Can't agree more :)
•  » » » 4 years ago, # ^ |   -17 What are you talking about?
•  » » 4 years ago, # ^ |   -6 It looks like this contest's results also going to like it :D
 » 4 years ago, # |   -79 I would like to know whether GlebsHP and AlexFetisov have carefully checked the problem statements, data, etc. It's quite common in Indian contests that they make wrong data, write wrong statements, or even add a new problem during the contest.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 you have participated in just 2 contests till now . how can you say that ?
•  » » 4 years ago, # ^ | ← Rev. 2 →   -19 you just can't make such a statement about Indian contests!
•  » » 4 years ago, # ^ |   +1 have u tried the questions they were worth trying
 » 4 years ago, # | ← Rev. 2 →   +10 XD
•  » » 4 years ago, # ^ |   +13 Yup. Its going to be rated. (Mentioned in blog)
•  » » » 4 years ago, # ^ |   0 thx!
•  » » » » 4 years ago, # ^ |   +10 are you familiar with Find option in your browser?it's easy to find "rated" in blog
•  » » » » » 4 years ago, # ^ |   +16 After I learn Machine Learning I will write a bot to insult those jerks who humiliate those annoying butts who keep posting annoyingly repetitive comments. So beware!!!And I'll call it toughlilshit.
•  » » » » » » 4 years ago, # ^ |   0 Your mother was a hamster.
•  » » » » » » » 4 years ago, # ^ |   +16 Oh fuck! I have predicted that! You tough little shit! Muahahahahahahaha!
•  » » 4 years ago, # ^ |   +15 The standard question for every round......
•  » » » 4 years ago, # ^ |   +34 With the only difference that if it's a low-rated user who asks the question, he is usually downvoted by the others, here the case seems to be different. Colorism...
 » 4 years ago, # |   -15 2.5 hrs for 8 problems ? I don't know, seems a little though for Div.2 competitors.
•  » » 4 years ago, # ^ |   +8 Its literally tough for div2 people, because the contest will have both div1 and div2 people competing ;) i.e Its an open round for both divs !
 » 4 years ago, # |   0 I can not understand one thing, you are organizing 3 contest as HackerRank Collage rounds and one as regular CF round ?Even I think that you are providing better prizes for winner of HR contest :)I hope the size of code isn't important as on yesterday HR round :D
•  » » 4 years ago, # ^ |   0 Hi Aleksa, Yesterdays contest, viz Perplexed, was a constrained programming event, which was bound to have Code-Golf and TLE style problems. And for other 2 contests, CTF and Mathmania, Hackerrank is a good platform (where we have question and the answer, without code).However Manthan is the Algorithmic contest of Codefest. And associating it with Normal CF round makes it more obvious that Code Length etc are not that significant. Just the speed and the accuracy ;)
 » 4 years ago, # |   +2 what will be the scoring distribution ?
 » 4 years ago, # |   +4 We must register at codefest.tech?
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 Hi Alexandru, You need to register on www.codefest.tech to be eligible for prizes and to get a .tech domain free for 2 years. You can however, choose to not register and simply compete. :)
 » 4 years ago, # |   +4 Question from blind: russian texts?
 » 4 years ago, # |   +7 Are the problems suitable for both divisions?
 » 4 years ago, # |   +21 How can I get the ".tech" domain? I'm quite interested because it's not common to give out such things.
•  » » 4 years ago, # ^ | ← Rev. 4 →   +8 Hey!The ".tech" domain will be made available to you via email. The moment you register here. In order to be eligible for receiving the ".tech" domain be sure to register with the same email that you intend to use for following up with the registration of the domain. The detailed instructions will be emailed to you!In case any one hasn't received the instructions but has registered on codefest.tech drop me a message with your email.
 » 4 years ago, # |   -9 GOOD LUCK. I wish the problems don't have math very much :)
 » 4 years ago, # |   -65 Is the contest rated?
•  » » 4 years ago, # ^ |   +15 oh boy not again
•  » » 4 years ago, # ^ |   +5 "Hello Codeforces,Manthan, Codefest 16 will take place on Friday 26th February, 2016 10:35PM IST with a duration of 2.5 hours. The round is rated and consists of 8 problems."-quoted from blog postIt's literally on the second line of the announcement.
•  » » 4 years ago, # ^ |   +138 Is it rated?
•  » » » 4 years ago, # ^ |   -46 oh boy not again
•  » » 4 years ago, # ^ |   +30 Yeah it is colorism... :D
 » 4 years ago, # |   +3 Register and get a .tech domain for free? that simple ? :P
•  » » 4 years ago, # ^ |   +5 Hi!Yup! It is that simple! In order to be eligible for receiving the ".tech" domain be sure to register with the same email on our website that you intend to use while registering your free domain.Please note that the domain will be free for 2 years..tech domains has partnered with Codefest for 2016 and made this offer to our participants. :)
•  » » » 4 years ago, # ^ |   0 brb, registering hundreds of .tech domains and scamming people by selling the domain access to them :D
•  » » » » 4 years ago, # ^ |   +5 Why no upvotes? Its technically not illegal.
 » 4 years ago, # |   -22 will this round be rated ?
 » 4 years ago, # |   +105 Let's forbid using words "rated" and "unrated" in comments.
•  » » 4 years ago, # ^ |   +35 U, sir, just used them twice. :p
•  » » » 4 years ago, # ^ |   +30 If we consider substrings thn actually thrice :P
•  » » 4 years ago, # ^ |   +9 I'd prefer to forbid the word "scoring". As for me, it's the most useless and annoying kind of comments.
•  » » » 4 years ago, # ^ |   +2 Why not both? :D
•  » » » 4 years ago, # ^ |   +10 getting to know whether it is dynamic or static may be useful
•  » » » 4 years ago, # ^ |   0 Sounds good but then at least the authors must use it at least once in their announcements. Btw, what about the scoring distribution of this round, I see nothing in the blog?
 » 4 years ago, # | ← Rev. 2 →   +35 I probably shouldn't participate if I want to keep my rating, but fug it :DDDD.Btw there are quite a lot less reds registered than in the last contest. Even when adjusted to the total number of participants.
 » 4 years ago, # |   -9 Seriously? Delay? -_-
•  » » 4 years ago, # ^ |   0 After a long time We are facing delays again :)
•  » » 4 years ago, # ^ |   +4 Because there were less than 5000 participants
•  » » 4 years ago, # ^ |   0 They prolly found a mistake in testsuite huehuehue
 » 4 years ago, # |   0 why the delay??? the site didn't break just before the contest start???
 » 4 years ago, # |   -17 good luck guys!!!
 » 4 years ago, # |   -36 10 mins delay, seriously? F*ck this shit, I'm going to sleep :\
•  » » 4 years ago, # ^ |   0 10 mins delay, seriously? I have my exams coming up :/ !
•  » » » 4 years ago, # ^ |   0 Seriously, 10 minutes is dramatic enough to mess up your exams?
•  » » » 4 years ago, # ^ |   +3 Yes and these 10 minutes are gonna make you fail your exams. Bad Codeforces.
•  » » » » 4 years ago, # ^ |   0 (sarcasm)
•  » » » » » 4 years ago, # ^ |   0 u don't say :/
 » 4 years ago, # |   0 Good luck to all!
 » 4 years ago, # | ← Rev. 2 →   +7 before contest start: 3:12 one hour laterbefore contest start: 2:24
 » 4 years ago, # |   -84 When I was at hacking ... I think that he was not sure to include all of libraries.
•  » » 4 years ago, # ^ |   +45 You just made his solution public, during contest. Are you nuts?
 » 4 years ago, # |   +6 For two hours I was trying to devise fast method to calculate factorial of 400009... and I did it!What kind of brain malfunction is that?
 » 4 years ago, # |   +4 Now I know I am not the only one who completed Devil May Cry 4 recently .As I saw the name of problem A I was like ' wait for it ' o.OAnd when I saw the problem I was 'Hey' :v =D
•  » » 4 years ago, # ^ |   0 Yes but in the game you could break the shields of "The Savior" using rebellion and Ebony and Ivory do not do different damages :D
•  » » » 4 years ago, # ^ |   0 Yeah =DThough I broke them using panadora and dark slayer style :p =D
 » 4 years ago, # |   +5 I see many hacks in this contest :D First time i was able to submit 4 problems that passed pretests. I wonder if backtracking would work under time limit for C :? I saw different solutions some using hashing in my room.
•  » » 4 years ago, # ^ |   0 I used backtracking too :) hope it will pass :D
•  » » 4 years ago, # ^ |   +6 I hacked 2 backtracking solutions with this generator.
•  » » » 4 years ago, # ^ |   0 What's the reason for the wrong answer for your testcase in backtracking solution?
•  » » » » 4 years ago, # ^ |   +3 Unefficient solutions using backtracking will time out.
•  » » » » » 4 years ago, # ^ |   0 Can you check my solution : http://ideone.com/mfEKvy
•  » » » » » » 4 years ago, # ^ |   +1 737 ms.
•  » » » » » » » 4 years ago, # ^ |   0 I don't how was my solution hacked.
•  » » » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0
•  » » » » » » » » » 4 years ago, # ^ |   0 I think that is not acceptable input. The only word in dictionary having "b" has 100 consecutive and the input string requires just ab.
•  » » » 4 years ago, # ^ |   +15 Hi!
•  » » 4 years ago, # ^ |   +9 I used Trie.
 » 4 years ago, # |   +31 And again tourist in the last moment, awesome! :D
•  » » 4 years ago, # ^ |   +81 Good Game!
•  » » » 4 years ago, # ^ |   +15 TooSimple ;)
•  » » » 4 years ago, # ^ |   +4 First of all, congratulations! Yeah, it was definitely good for spectators, I was watching the top places during the last 20-30 minutes. When you submitted on E, I was like "This guy is astonishing, he just killed the intrigue" and then on my last refresh I saw tourist on the top.
•  » » » 4 years ago, # ^ | ← Rev. 3 →   +11 TooDifficuIt you should learn how to hack :D
 » 4 years ago, # |   0 What was the pretest 4 of D ?
 » 4 years ago, # | ← Rev. 3 →   +21 hacks on B,C,D in 15 minutes before end... Why are you doing this to me :(
 » 4 years ago, # | ← Rev. 2 →   +5 Can anyone tell why this test case is invalid for C? 3 aab 3 a aa ba 
•  » » 4 years ago, # ^ |   +1 Maybe you forgot to output newline at the end?
•  » » 4 years ago, # ^ |   +6 No linebreaks.
•  » » 4 years ago, # ^ |   +5 " It is guaranteed that at least one solution exists. If there are multiple solutions, you may output any of those. " no solution exists with this test
 » 4 years ago, # |   +6 Hey guys I used a Trie Based solution for Problem 3...and I got MLE on pretest 10...Isin't that really unlucky?? I mean MLE??? why ????
•  » » 4 years ago, # ^ |   0 If you're like me you used way more than 1,000,000 chars memory to store because you were storing prefixes to all of them. I don't even know if that's still a trie but it's what I did, when I hashed the strings it passed pretests but I have no faith in it.
•  » » 4 years ago, # ^ |   0 your memory = 262100 KB > memory limit per test: 256 megabytes
•  » » » 4 years ago, # ^ |   0 Ya I even wrote a question to the moderators asking them to increase the ML to 512 mbs out of desparation...Lol...
 » 4 years ago, # |   +97
 » 4 years ago, # |   +47
•  » » 4 years ago, # ^ |   +4 How can I post pictures?
•  » » » 4 years ago, # ^ |   +79 Step 1:Step 2:Result:
•  » » » » 4 years ago, # ^ |   +5 Thanks!
 » 4 years ago, # |   0 How to solve C?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 pretty easy with hash and dp but needed to use a small mod in order not to use a map which would lead in to tl
•  » » » 4 years ago, # ^ |   +8 My solution is aproximate N*sqrt(Length of all words)*log(sqrt(n)) and I used a big mod. The main fact here is that there are at most Sqrt(lenght of all words) different lengths of words.
•  » » » » 4 years ago, # ^ |   0 of course mine is n * 1000 :) but couldnt add another log n
•  » » 4 years ago, # ^ |   -13 I have solved C in this way:For every index i, make a new word up to the last index j, where the last word matched, and check the list, whether the word is listed or not.If the word is found in the list, then print the original word, otherwise ignore it. To find the newly made word in the list easily, I used a map which keep the vector index of every original word.You can see my solution here: 16366352 For further query post your comment.
•  » » » 4 years ago, # ^ |   0 Unfortunately, this solution will not work for some cases like: 2 ba 2 b ab 
•  » » 4 years ago, # ^ |   0 My solution is trie. first reverse W's , then add them to trie.Then use dp , if suffix of s starting with position i can became partitioned with some of W's dp[i]=1 else dp[i]=0.
 » 4 years ago, # |   0 I Love Death Note :|
 » 4 years ago, # |   +9 Why were the constraints so tight in C,D,E? :|
•  » » 4 years ago, # ^ |   0 Especially D. Submitted because of my experience with fast CF servers :P
 » 4 years ago, # |   0 Please discuss C and D. In D, the sequence depends upon the 1st 2 numbers. So that's n^2. Then we must determine the sequence, adding an extra n which clearly times out. What is the correct approach? Is it using binary search?In C, I thought KMP of all words on the text(10^9 complexity)and store all occurences in text. and then DP with the result. Again, very bad complexity.
•  » » 4 years ago, # ^ |   0 I used trie and greedy to solve problem C.
•  » » 4 years ago, # ^ |   +10 In C, I think you need to use trie.
•  » » » 4 years ago, # ^ |   0 Please elaborate.
•  » » » » 4 years ago, # ^ |   +1 If I had solved it then I could tell the process. That's why I said "I think".
•  » » » » 4 years ago, # ^ |   0 Solve the entire dictionary in a trie. Now traversing the trie you can, in O(N) time determine all words that, when reversed, would be suffixes to the scrambled sentence.Now, for all prefixes of the scrambled sentence, in a similar manner you can also determine in O(N) time all words that, when reversed, would be suffixes to the prefix (essentially, substrings)Do this for all the prefixes sentence[:i], from longest to shortest, but if and only if there is a previously found substring or suffix that matches that prefix (that is in the form sentence[i:j]). That is essentially DP.Running time is O(N2)
•  » » » 4 years ago, # ^ |   0 I got MLE using Trie!!! MLE of all??
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 I got a MLE initially, but I optimized the trie so that each node has only 27 (initially NULL) children, not 128 for each ASCII character or something else bigger. This shouldn't give MLE because there are at most 1 000 000 nodes, each node taking up 224 bytes (27 64-bit pointers and two integers for depth and value). This gives definitely less than 256 MB, even after accounting for other things that need memory.
•  » » 4 years ago, # ^ | ← Rev. 3 →   +4 IN D: Choose 1st and 2nd, n^2, and sequence is most log n , so O(n^2 log n)(check 1st and 2nd are 0 because if they are, sequence can be n)
•  » » 4 years ago, # ^ |   +4 In D, I stored all checked pairs (and those which occured during generating the sequences in both directions) in set, thus sequences were not rechecked.In C, I used Trie. On reversed string, go char by char. Maintain set of possible places in Trie. When the node in Tree is end of some word, you branch (either continue word or start new word). But on each position you will branch at most once, because it does not matter which word has ended here, if there are multiple words possible.
•  » » 4 years ago, # ^ |   -13 I have solved C in this way:For every index i, make a new word up to the last index j, where the last word matched, and check the list, whether the word is listed or not.If the word is found in the list, then print the original word, otherwise ignore it. To find the newly made word in the list easily, I used a map which keep the vector index of every original word.You can see my solution here: 16366352 For further query post your comment.
 » 4 years ago, # |   -8 In E, I used Sparse Tree for range min/max queries, building the two instances for 106 took almost 3 seconds (and the limit is 3 seconds).. Though anyway got WA.
 » 4 years ago, # |   +146 Why this solution (for problem A) http://codeforces.com/contest/633/submission/16351079 is hacked? I really can't get it.
•  » » 4 years ago, # ^ |   -18 what is the input used to hack ?
•  » » » 4 years ago, # ^ |   +26 how can I know that, lol
•  » » » » 4 years ago, # ^ |   +6 sorry , i was so dumb
•  » » » 4 years ago, # ^ |   -6 tell it to the hacker
•  » » 4 years ago, # ^ |   0 I did the same, seems like mine will get WA too :(
•  » » 4 years ago, # ^ |   +41 Your solution is correct. During the contest we noticed a very unpleasant thing — validator for problem A accepted tests with c up to 100k instead of 10k.There are 14 hacks that used this mistake in validator. We are investigating the case and will report you the results soon.
•  » » » 4 years ago, # ^ |   0 Wow, thanks :)
•  » » » 4 years ago, # ^ |   +35 Do whatever you see necessary just don't make it unrated. Please.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +12 Don't worry you must get 1900 today! :)Good Luck!
•  » » » 4 years ago, # ^ |   0 So that's why the system testing has been pending for so long...
•  » » 4 years ago, # ^ |   +58 Hi, i hacked you, but i think your code is ok. Test was 1 8 100000, i thought that c<=10^5, but it is 10^4. I apologize :D
•  » » 4 years ago, # ^ | ← Rev. 2 →   -28 I'm wrong :((
•  » » » 4 years ago, # ^ |   +16 but a <= 100 and b <= 100
•  » » » 4 years ago, # ^ |   0 But that number fits in signed integer right?
 » 4 years ago, # |   +6 The difference between first two tasks and other tasks are big. I think that many solution for C and D won't pass final system testing (even I am not sure for my submissions).
•  » » 4 years ago, # ^ |   +5 Pretests for D seem to be strong enough.
•  » » » 4 years ago, # ^ |   +6 Nope, they allow passing the solutions that try to start the sequence from all possible pairs of integers in the input (not only the distinct pairs). Such solutions are about to fail on test consisting of 1000 zeros (since the sequence length is linear for each starting pair).
•  » » » » 4 years ago, # ^ |   +3 By the way, do you know any other starting pair of numbers, other than 0 0, that allows very long sequence that does not reach large numbers quickly? I couldn't think of any other pair, but decided to start from unique pairs just in case.
•  » » » » » 4 years ago, # ^ |   +3 x -x
•  » » » » » » 4 years ago, # ^ |   +3 You are wrong. x, ( - x), 0, ( - x), ( - x), ( - 2x), ( - 3x), ( - 5x), ( - 8x), ....
•  » » » » » » » 4 years ago, # ^ |   +5 Sorry, I'm stupid :)
•  » » » » » » » » 4 years ago, # ^ |   -16 I'm blue and I find saying that you're stupid offensive.
•  » » » » » 4 years ago, # ^ |   +14 One can prove a bound of for the length of the sequence different from constant zero.
•  » » » » » 4 years ago, # ^ | ← Rev. 3 →   +1 Maybe not really what you're looking for, but sequences can first decrease to smaller numbers, and then either stay at 0 or grow again.Fn,  - Fn - 1, Fn - 2,  - Fn - 3, ..., 3,  - 2, 1,  - 1, 0, ...EDIT: Fixed sequence, thanks Zlobober.
•  » » » » » » 4 years ago, # ^ |   +5  - 1 + 0 ≠ 0.
•  » » » » » » » 4 years ago, # ^ |   +5 Good point, in retrospect its obvious no sequence that starts with a nonzero value converges to zero.
•  » » » » » » » » 4 years ago, # ^ |   0 This is wrong — the longest possible sequence (the one reaching 2logφ109) does exactly that:13 -8 5 -3 2 -1 1 0 1 1 2 3 5 8 ...Or generally if your starting values are P and Q, then on N-th step you get Fn - 2 * P + Fn - 1 * Q, so if you set P = Fn - 1 and Q =  - Fn - 2, you will first reach 0 on n-th element, and then start growing from there.
•  » » » » » » » » » 4 years ago, # ^ | ← Rev. 2 →   +15 I know, that's the sequence I gave a few posts above. By 'converge to zero' I mean the mathematical definition of convergence, so a sequence that just visits 0 once does not converge to 0.
•  » » » » » » » » » 4 years ago, # ^ |   0 Converges  ≠  approaches.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 I start from all possible pairs and it finishes in 160ms for 1000 zeroes on my laptop.edit: I just realized that I don't start from all possible pairs, haha.
•  » » » » » 4 years ago, # ^ |   0 Takes 8 seconds if I do that, so would get TLE.
•  » » » » 4 years ago, # ^ |   -9 That's evil! They should've added that test to pretests.
•  » » » 4 years ago, # ^ |   0 I hope so, but I saw some hacks with TLE. Also I didn't have brave to try some test like it :)Also I saw many strange solutions for C, many users don't have trie and even top guys wrote solution with it.
 » 4 years ago, # |   +24 What is "Unexpected verdict"? I get it when I'm using a large random test case (http://ideone.com/oRhDoe) to hack C.
•  » » 4 years ago, # ^ |   0 We are investigating this issue, I will reply you as soon we will find out the problem.
•  » » 4 years ago, # ^ |   +3 I think it's because the input data you generated don't have a valid outcome while in the problem it says it's guaranteed to have at least one valid answer?
•  » » » 4 years ago, # ^ |   +2 Then the verdict should be "invalid input", not "unexpected".
•  » » » » 4 years ago, # ^ |   0 I think the validator didn't check whether the input has a valid solution or not, so it unfortunately validated the input as correct, but the model solution couldn't make an answer, therefore "unexpected verdict" :p?
•  » » 4 years ago, # ^ |   +13 It's ok now. I have investigated that everything is correct and may now conclude that what happened is: your test broke one of solutions we considered to be correct.
•  » » » 4 years ago, # ^ |   +57 Does that mean you will run the system test now or what :'D
•  » » » 4 years ago, # ^ |   +39 Ironically, this case becomes the only one that cause my program WA (by hash collide).So I got -1200 points by this successful hack.
 » 4 years ago, # |   +8 When will the Editorials come?
•  » » 4 years ago, # ^ |   0 Editorials are out now.
 » 4 years ago, # | ← Rev. 2 →   +23 Why drain of points was not adjusted to the contest length (as during Goodbye 2015)? I got less points for E (which I needed more than 1 hour for) than D (which I needed few minutes for).
 » 4 years ago, # |   +73 .
 » 4 years ago, # |   +5 Why pending so long?
 » 4 years ago, # |   +5 Why so much delay in System Testing? :(
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Look at thisThere are problems with the correction system, it seems that we are going to wait more than expected ;(
 » 4 years ago, # | ← Rev. 4 →   0 I can't find the contest on the contest page anymore... Obviously you can still find it with the URL (/contests/633).EDIT : maybe they have enough of people refreshing the standings page. :PEDIT2 : fixed
 » 4 years ago, # |   -83 i think this will be unrated because of unexpected behaviour during hacks
•  » » 4 years ago, # ^ |   +16 Surely not for everyone
•  » » » 4 years ago, # ^ |   0 How will they undo this ? he could have hacked many
•  » » » » 4 years ago, # ^ |   +1 Only 14 hacks. You can't make such contest unrated for only 14 casualties.
•  » » » » » 4 years ago, # ^ |   0 -_- thats not the one with 14 casualties, open the link please
•  » » » » 4 years ago, # ^ |   0 What's the problem? They will just re-run all hacks :)
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   +12 Its possible that someone lost a lot of time fixing bug, that cannot exist
•  » » » » » » 4 years ago, # ^ |   +3 Ok, that's right :) But since there are just 14 such hacks, maybe they can ask those people to choose whether they will have rated or unrated contest :)
•  » » » » » » » 4 years ago, # ^ | ← Rev. 2 →   -6 http://codeforces.com/profile/Antoniuk and http://codeforces.com/profile/ngochai94 ? They spent a lot of time and organisators will ask them to be unrated????? time=money
•  » » 4 years ago, # ^ |   -8 I think it will not be the case. Adjusting the score for a few hacks doesn't take long. Contest become unrated due to errors in question itself, i.e. error from problem setters.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +13 Did anyone say that this contest become unrated?
 » 4 years ago, # |   +26 not unrated.. please...
•  » » 4 years ago, # ^ |   +67 Don't worry, it's not going to be unrated
•  » » » 4 years ago, # ^ |   0 Then it will be fair for all
 » 4 years ago, # | ← Rev. 3 →   +112
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 in 12 mins lolbtw resize the picture a little bit!
 » 4 years ago, # | ← Rev. 2 →   +1 anyone who hacked was lucky :) i think the best way is that hackers get their hack points and the ones who got hacked because of this get their points back too
 » 4 years ago, # |   +29 I hope the contest won't become unrated just because of 14 hacks. But, then again, for those 14 it will be unfair. Can't just those 14 people who were hacked be unrated? Since there are a lot of participation, I think it will be unfair to the other participants. Of course, if those 14 want to be rated, then its a different matter :) . I hope the contest organizers will take steps that will be fair for all.
•  » » 4 years ago, # ^ |   0 I agreed with you
 » 4 years ago, # |   +40 Not sure if I should go to sleep and see the result tomorrow or wait for system test. . .
 » 4 years ago, # |   0 What is wrong with my submission ? http://codeforces.com/contest/633/submission/16358059
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 try 100000answer is:5 400005 400006 400007 400008 400009not 0
•  » » 4 years ago, # ^ |   0 i <= 100000 should be i <= 400010try to get the answer for m = 100000
•  » » » 4 years ago, # ^ |   -10 <= 400009 :)
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Why downvotes?Am I wrong?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Problem is you are running your loop till 10^5. You need to run it to 5*10^5 at least.Or as many people did, just let it run to infinity. The else case (when the value exceeds input) will break the loop timely, so you don't need to worry about the upper limit.
•  » » 4 years ago, # ^ |   0 your code doesn't work for n>=23000
 » 4 years ago, # |   -26 It was a nice contest! LOL! Thanks for really fast system testing and fast editorial! LOL! Thanks for being on time and no delay! LOL! Thanks for anything!
•  » » 4 years ago, # ^ |   +5 Editorials are out now.
 » 4 years ago, # |   -58 It was unfortunate I seem to have been deprived a chance to hack solutions. The hacking phase was on, yet there was no lock button to lock my solution :(
•  » » 4 years ago, # ^ |   +28 Well, none of us have ever seen "Pending system testing" and a lock on the same page have we :)
•  » » 4 years ago, # ^ |   0 Go drunk you're home
•  » » 4 years ago, # ^ |   -7 Oops! I'm being a newbie. I'm sorry, I didn't know that's how stuff works.
 » 4 years ago, # |   +4 A few days ago, I wished the rating changes was announced fast. Today I am tired of waiting for the system testing
 » 4 years ago, # |   +10 Plz just say when system tesing is running?? TIME LIMIT EXCEEDED!
 » 4 years ago, # | ← Rev. 2 →   +213 Hello everybody! As you may see the systests haven't yet started, let me explain you the reason.Issue: during the contest we have noticed the mistake in the validator for problem A (Ebony and Ivory). It accepted tests with parameter c up to 100k, instead of 10k limitation given in the statement.Scale of the problem: 19 hacks.Decision: we have tried to find the most "fair" way to resolve this issue. Decision is the following: If the hack was unsuccessful, do nothing. If the hack was successful, but the solution was incorrect anyway, and could be hacked removing the extra sign, do nothing. For example, if the test was "1 1 100000", but the solution will obviously fail on test "1 1 10000", when we decided to keep thing as they are, as this is fair both for hacker (he still has his points) and the person being hacked (he knows his solution is incorrect). If the hack was successful, but the solution was actually correct, then we ignore this hack and rejudge the solution (so it becomes correct). We can't give you back the time that you have wasted on trying to figure out, why the solution was incorrect. The only thing we can do here is to apologize and make the round unrated for you, if you want it. So, if case number 3 is about you and you want the round to be unrated for you, contact me directly. We sincerely apologize for this happening. As you see, we did our best to solve this issue in a way suitable for everybody.
•  » » 4 years ago, # ^ |   +27 I am sorry if I am inconveniencing you, but I think it would be best if you pm those individuals. After all, some of them might not be following this thread.
•  » » » 4 years ago, # ^ |   -24 suppose I don't follow the thread . what does it mean --> I don't care about the contest :D
•  » » » » 4 years ago, # ^ |   +7 Not really. They may have gone to sleep, or to their school, or to do some errand. Not everybody has the time to stare idly at the computer screen, cross their fingers, and pray "please don't fail system test".
•  » » » » » 4 years ago, # ^ |   0 again :when they came back , if the contest is important for them , they will check the thread :D
•  » » 4 years ago, # ^ |   +19 That means system test is about to begin, right?
•  » » 4 years ago, # ^ |   +5 In point 4, not sure why case 2 people will be aggrieved? They are after all getting a chance to check their solutions again, which was anyway incorrect (albeit from a wrong hack). But their solutions were incorrect, so rather they should be happy :PI think the case 3 people would feel aggrieved, as they wasted time unnecessarily mulling over why they got hacked for a correct solution.
•  » » » 4 years ago, # ^ |   0 Sure thing it must be case number 3
•  » » » » 4 years ago, # ^ |   0 Cool :)I am none of these cases btw. Was simply analyzing the solution. Pretty elegant one. Should suit nearly everybody :)
 » 4 years ago, # |   +47 Please tell us when the system test gonna start :(
 » 4 years ago, # | ← Rev. 3 →   +3 Could someone please explain how can Java 8 use 0 KB memory for the problem C? It seems strange for me considering that in C++ I myself got MLE on it :( Edit: The solutions in Java 8 either use 100MB+ or 0.
 » 4 years ago, # |   +8 How to solve H?
•  » » 4 years ago, # ^ |   +10 The expected solution was using MO's Algorithm.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +8 I think that O(n * q) solution is OK. UPD. He got WA due to overflow. Now, it's OK, 4929 ms.
•  » » 4 years ago, # ^ |   0 If are being blocked from seeing accepted solutions before System tests. Find any user who accepted this problem, add him as a friend, go to friend standings, click on his submission, and you shall be able to see his/her solution.As for your question, It looks like Tourist solved it using Mo's Algorithm.
•  » » 4 years ago, # ^ |   +13 We can use Mo's algorithm to reduce the problem to the operations of adding or removing an integer to a set and update the sum. We can keep the set and sums in a range using a treap.To update Σi = 0nFj × aj when adding x at position j, we need to add Fj × x and "shift" Σj = inFj × aj to Σj = inFj + 1 × aj. To be able to "shift" sums like that, we store both Σj = inFj × aj and Σj = inFj + 1 × aj, as we can then easily compute all Σj = inFj + k × aj.My code (the important functions are push, update, insert and remove) : http://lpaste.net/8369132792918835200The complexity should be O(n sqrt(n) log(n))
 » 4 years ago, # |   +46 Come on, start these systests. We all want to get our TLEs and go to bed.
 » 4 years ago, # |   +9 It's almost 12 PM in my country. Am I going to know whether my solutions will pass before going to sleep? :(
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 3:15 AM in mine!
•  » » 4 years ago, # ^ |   +1 03:15 am in India!
•  » » 4 years ago, # ^ |   0 2pm for me!
•  » » 4 years ago, # ^ |   0 It depends on your mood :)
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 3:48 AM
•  » » 4 years ago, # ^ |   +5 5:48 AM
•  » » 4 years ago, # ^ |   0 5am...
•  » » 4 years ago, # ^ |   +35 5:50am in China
•  » » 4 years ago, # ^ |   0 From the comments replying you, it seems you're too lucky :D
•  » » 4 years ago, # ^ |   0 12:00 am. Interesting how TooDifficult's comment has more upvotes than others who wrote the similar content.
•  » » » 4 years ago, # ^ |   +13 Do you also find it interesting that say Cristiano Ronaldo eating breakfast has more likes on his picture than others who are doing the same?
•  » » » » 4 years ago, # ^ |   -36 I think you are just looking for upvotes. If you want to state that it's because he is red, then say so.
 » 4 years ago, # |   +4 Finally!
 » 4 years ago, # |   +12 At last our long desired system testing started !
 » 4 years ago, # |   +12 Hashing fails for C :(
•  » » 4 years ago, # ^ |   0 my hashing soluion for C passed
•  » » » 4 years ago, # ^ |   -8 Congrats for picking the right constants :p
•  » » » » 4 years ago, # ^ |   0 I picked the right constants and used double hashing, still got WA. Got Accepted after replacing one random prime with another. Also got WA in H just because of forgetting one MOD operation. What kind of hellish misfortune is this?
•  » » 4 years ago, # ^ |   +3 My hashing + dp passed :D
 » 4 years ago, # |   +3 Black day II?
 » 4 years ago, # |   +4 Why are the system tests stuck at 72% ?
 » 4 years ago, # |   0 Why and how every time the score of the problems in contest was changing? I noticed : 1. When contest started score of Problem E was 250, so I started doing that. 2. Then after a refresh, score of Problem A 750 and E was still 250. 3. Then A became of 500 then it became of 250 now at the time of systests it is of 500! 4. Score of other problems also changed.Is this legit during contest?Wrong validator/test cases can be accepted during contest but scores? During contest end scores of problems were different, during systests it is different, and I guess after systests it will be different.GlebsHP I understand validator can be wrong but what's with this Score issue?
•  » » 4 years ago, # ^ |   0 Dynamic Scoring. The score of each problem will decrease according to the amount of accepted solutions (pretest passed) it gets.
•  » » 4 years ago, # ^ |   0 It's called dynamic scoring. The maximum score of a problem is a function of the number of participants who correctly solved it. The higher the number of participants solving the question, the lower the score.
•  » » » 4 years ago, # ^ | ← Rev. 3 →   +19 Still he is right about situation at the beginning of the contest — for a first few minutes two problems in the middle of the problemset (probably E and F, but I'm not sure) had score equal to 500, while other tasks had 3000.P.S. And also I wasn't able to see list of contestants in my room for a few minutes at the beginning — it was simply displayed as empty :)
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 I was just one of the problem setters. I didn't handle the server side of things. Maybe GlebsHP can answer to you regarding this.
•  » » » 4 years ago, # ^ | ← Rev. 4 →   -8 mkrjn99 I am aware of dynamic scoring** of codeforces which decreases as times passes. But Full Score doesn't decreases or changes right?**Aware of fact that maximum achievable score by a user will decrease as time passes!
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Full score can also decrease. This is a special kind of dynamic scoring. Was used here also: http://codeforces.com/contest/550 , see how the maximum score for A became more than B in that case.
 » 4 years ago, # |   +7 Why and how every time the score of the problems in contest was changing? I noticed : When contest started score of Problem E was 250, so I started doing that. Then after a refresh, score of Problem A 750 and E was still 250. Then A became of 500 then it became of 250 now at the time of systests it is of 500! Score of other problems also changed. Is this legit during contest?Wrong validator/test cases can be accepted during contest but scores? During contest end scores of problems were different, during systests it is different, and I guess after systests it will be different.GlebsHP I understand validator can be wrong but what's with this Score issue?
 » 4 years ago, # |   -7 why is the system test totally stuck and the site are dying ?
 » 4 years ago, # |   +3
 » 4 years ago, # |   0 Codeforces back, System testing completed :D Backtracking optimized solutions passes for C: http://codeforces.com/contest/633/submission/16361771 Failed on D but ranking shifted just by 10, lot of fails on C/D
 » 4 years ago, # |   0 why this submission gets failed ?!?!?! 16362350
•  » » 4 years ago, # ^ |   0 i mean due to time limit :|
•  » » » 4 years ago, # ^ |   +10 Now you get WA.You should be able to figure it out by yourself now :) BTW, the probability of collision is very high in your solution.
 » 4 years ago, # |   0 The points for the 3rd question, right at the end of the contest, was maximum 1000. I guess by then all scores had to be static. However, at the end of sys-tests, the scores for C has gone to 1500.I am not sure if this fair, and as per rules, scores should depend on number of pretests passed, so why did they change post systests?GlebsHP — can you please check?
•  » » 4 years ago, # ^ |   0 Check it here — Assign the value of the task dynamically depending on the number who have solved this problem. During the main contest time here will be taken into account the submissions with verdict "Pretests passed", but after system test — "Accepted".So it is perfectly fine if points for some problem will increase after a system testing (because of people passing pretests but failing final testing).
•  » » » 4 years ago, # ^ |   0 Had no idea about this. I have never seen this till now to be honest. This was an experiment it seems. Did it stick?
•  » » » » 4 years ago, # ^ |   0 This is not an experiment. I have seen this before in another contest also. Please check link: http://codeforces.com/contest/550
•  » » » » » 4 years ago, # ^ |   0 That link doesn't really help as there is no way to know whether the scores were processed due to number of pretests passed or systests passed. It could well be that A had fewer pretests passing, hence the scores were low. Not saying that you are right or wrong, just that the example makes no sense.More importantly, why weren't any announcements made before the contest about the dynamic scoring? This seems to be a rare event, and it would have been fair if everybody knew the rules. In every other contest, the scoring distribution is mentioned just before the contest starts.
•  » » » » » » 4 years ago, # ^ |   0 I participated in the contest myself and that's how I remember that the scoring was decided on the basis of system tests and not pretests.Regarding the announcement about the scoring, yes I agree, this was a mistake from our side.
 » 4 years ago, # |   -6 Really strict and annoying final tests for C and D :(
 » 4 years ago, # |   +1 After the contest, I'm sure that my solution for D will be judged WA, but in the end, my ABC is WA while D is AC. I'm sure it will fail at a test has 500 0's and 500 1's, but there's no such test in the final test.
 » 4 years ago, # |   0 Any editorial? No? Why? Oh, OK....![ ]()
•  » » 4 years ago, # ^ |   +3 Don't be sad: http://codeforces.com/blog/entry/43392
 » 4 years ago, # |   -50 Для tourist easy VK Cup 2016, Codefest 16, Марафон VeeRoute. Easy три приза.
 » 4 years ago, # |   +5 Where is an editorial?
•  » » 4 years ago, # ^ |   +6 Bottom of the ocean
•  » » 4 years ago, # ^ |   +4 Editorials are out now.
 » 4 years ago, # |   0 hello why my problem is Skipped in the cantest Manthan, Codefest 16??......................
•  » » 4 years ago, # ^ |   0 because u cheated for good !
•  » » » 4 years ago, # ^ |   -10 منظورت چیه؟؟
 » 4 years ago, # |   +9 Gaddammit. I failed E and lost 80 places because of an uncommented debug output.
•  » » 4 years ago, # ^ |   0 Very sad indeed!
•  » » 4 years ago, # ^ |   +5 Use cerr
•  » » » 4 years ago, # ^ |   0 I use vigilance and check such things everytime (to me, programming is more like self-programming). I missed it this time... but it's quite surprising that it wasn't caught by pretests.
•  » » » » 4 years ago, # ^ |   +14 There are more advantages to cerr other than the fact that it's a different stream than cout, e.g. the fact that cerr output isn't buffered — if you print debug info using cout and your program crashes the buffered output might not get printed, but with cerr` this is never the case.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   +8 That's why I use endl with debug outputs. Further vigilance.It's not a good approach to programming — I'm aware, but that's not why I do it.
 » 4 years ago, # | ← Rev. 2 →   0 TLE in D in 99 testcase!Is std::map that slow ?? using std::unordered_map gives TLE on 69 testcase ..Are there some other alternatives of using hash in c++?
•  » » 4 years ago, # ^ |   +5 Same thing happened with me, TLE in D on 99th testcase :(
 » 4 years ago, # |   +39 Can someone answer on this questions, please: Why ML in E is so strict? Why this solution (16364814) get ML on Java 8 and get AC on Java 7? Does 32-bit Java version exist on Codeforces?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +14 +1 to this question.I also have a question to MikeMirzayanov. Do you run java programs with -Xmx512m even if memory limit is 256 megabytes?