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://mirror.codeforces.com/blog/entry/43392
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.
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 :)
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.
Related: see Egor's comment about ByteCode 2016, which just happens to be another Indian contest.
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:
Unfortunately, you seem to be wrong :(
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.
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 :)
Also, just to mention, I have finished 3rd on Code Monk (Segment Tree,RMQ,Lazy Propagation) and haven't received the T-shirt yet.
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
Just checked and I haven't received one.
I finished 3rd in https://www.hackerearth.com/code-monk-number-theory-iii/hof/
Didn't get the T shirt :(
I got mine within 3 weeks.. I guess it is an issue only for non-Indian participants..
Last year EvenImage,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.
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. :)
Well, better luck to the organizers this time! Let's hope they really know what they are doing.
It definitely is a common issue for "Superpower by 2020".
Can't agree more :)
What are you talking about?
It looks like this contest's results also going to like it :D
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.
you have participated in just 2 contests till now . how can you say that ?
you just can't make such a statement about Indian contests!
have u tried the questions they were worth trying
XD
Yup. Its going to be rated. (Mentioned in blog)
thx!
are you familiar with Find option in your browser?
it's easy to find "rated" in blog
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.
Your mother was a hamster.
Oh fuck! I have predicted that! You tough little shit! Muahahahahahahaha!
The standard question for every round......
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...
2.5 hrs for 8 problems ? I don't know, seems a little though for Div.2 competitors.
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 !
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
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 ;)
what will be the scoring distribution ?
We must register at codefest.tech?
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. :)
Question from blind: russian texts?
Are the problems suitable for both divisions?
How can I get the ".tech" domain? I'm quite interested because it's not common to give out such things.
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.
Is the contest rated?
oh boy not again
"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 post
It's literally on the second line of the announcement.
Is it rated?
oh boy not again
Yeah it is colorism... :D
Register and get a .tech domain for free? that simple ? :P
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. :)
brb, registering hundreds of .tech domains and scamming people by selling the domain access to them :D
Why no upvotes? Its technically not illegal.
will this round be rated ?
Let's forbid using words "rated" and "unrated" in comments.
U, sir, just used them twice. :p
If we consider substrings thn actually thrice :P
I'd prefer to forbid the word "scoring". As for me, it's the most useless and annoying kind of comments.
Why not both? :D
getting to know whether it is dynamic or static may be useful
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?
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.
Перенесите соревнование, я пожрать не успел!
вот давайте без этого, мне вставать через 6 часов
Seriously? Delay? -_-
After a long time We are facing delays again :)
Because there were less than 5000 participants
They prolly found a mistake in testsuite huehuehue
why the delay??? the site didn't break just before the contest start???
10 mins delay, seriously? F*ck this shit, I'm going to sleep :\
10 mins delay, seriously?
I have my exams coming up :/ !
Seriously, 10 minutes is dramatic enough to mess up your exams?
Yes and these 10 minutes are gonna make you fail your exams. Bad Codeforces.
(sarcasm)
u don't say :/
before contest start: 3:12
one hour later
before contest start: 2:24
When I was at hacking ...
I think that he was not sure to include all of libraries.
You just made his solution public, during contest. Are you nuts?
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?
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.O
And when I saw the problem I was 'Hey' :v =D
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
Yeah =D
Though I broke them using panadora and dark slayer style :p =D
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.
I used backtracking too :) hope it will pass :D
I hacked 2 backtracking solutions with this generator.
What's the reason for the wrong answer for your testcase in backtracking solution?
Unefficient solutions using backtracking will time out.
Can you check my solution : http://ideone.com/mfEKvy
737 ms.
I don't how was my solution hacked.
Try this.
I think that is not acceptable input. The only word in dictionary having "b" has 100 consecutive and the input string requires just ab.
Hi!
I used Trie.
And again tourist in the last moment, awesome! :D
Good Game!
TooSimple ;)
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.
EvenImage you should learn how to hack :D
What was the pretest 4 of D ?
hacks on B,C,D in 15 minutes before end... Why are you doing this to me :(
Can anyone tell why this test case is invalid for C?
Maybe you forgot to output newline at the end?
No linebreaks.
" 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
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 ????
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.
your memory = 262100 KB > memory limit per test: 256 megabytes
Ya I even wrote a question to the moderators asking them to increase the ML to 512 mbs out of desparation...Lol...
How can I post pictures?
Step 1:
Step 2:
Result:
Thanks!
How to solve C?
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
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.
of course mine is n * 1000 :) but couldnt add another log n
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<string, int> which keep the vector index of every original word.
You can see my solution here: 16366352 For further query post your comment.
Unfortunately, this solution will not work for some cases like:
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.
Затупил в D, но зато от души взламывал B и C.
Обидно только, что А не получилось взломать... Видите ли:
оптимизируется компилятором и работает менее 200 мс...
Чему там оптимизироваться-то? 10^8 операций всего
10^8 простых арифметических операций и так должны укладываться в 2 секунды. XXI век на дворе.
Why were the constraints so tight in C,D,E? :|
Especially D. Submitted because of my experience with fast CF servers :P
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.
I used trie and greedy to solve problem C.
In C, I think you need to use trie.
Please elaborate.
If I had solved it then I could tell the process. That's why I said "I think".
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 formsentence[i:j]). That is essentially DP.Running time is O(N2)
I got MLE using Trie!!! MLE of all??
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.
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)
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.
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<string, int> which keep the vector index of every original word.
You can see my solution here: 16366352 For further query post your comment.
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.
Why this solution (for problem A) http://mirror.codeforces.com/contest/633/submission/16351079 is hacked? I really can't get it.
what is the input used to hack ?
how can I know that, lol
sorry , i was so dumb
I did the same, seems like mine will get WA too :(
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.
Wow, thanks :)
Do whatever you see necessary just don't make it unrated. Please.
Don't worry you must get 1900 today! :)
Good Luck!
So that's why the system testing has been pending for so long...
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
I'm wrong :((
but a <= 100 and b <= 100
But that number fits in signed integer right?
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).
Pretests for D seem to be strong enough.
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).
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.
x -x
You are wrong. x, ( - x), 0, ( - x), ( - x), ( - 2x), ( - 3x), ( - 5x), ( - 8x), ....
Sorry, I'm stupid :)
I'm blue and I find saying that you're stupid offensive.
One can prove a bound of
for the length of the sequence different from constant zero.
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.
- 1 + 0 ≠ 0.
Good point, in retrospect its obvious no sequence that starts with a nonzero value converges to zero.
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.
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.
Converges ≠ approaches.
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.
Takes 8 seconds if I do that, so would get TLE.
That's evil! They should've added that test to pretests.
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.
What is "Unexpected verdict"? I get it when I'm using a large random test case (http://ideone.com/oRhDoe) to hack C.
We are investigating this issue, I will reply you as soon we will find out the problem.
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?
Then the verdict should be "invalid input", not "unexpected".
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?
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.
Does that mean you will run the system test now or what :'D
Ironically, this case becomes the only one that cause my program WA (by hash collide).
So I got -1200 points by this successful hack.
When will the Editorials come?
Editorials are out now.
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).
Why pending so long?
Why so much delay in System Testing? :(
Look at this
There are problems with the correction system, it seems that we are going to wait more than expected ;(
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. :P
EDIT2 : fixed
i think this will be unrated because of unexpected behaviour during hacks
Surely not for everyone
How will they undo this ? he could have hacked many
Only 14 hacks. You can't make such contest unrated for only 14 casualties.
-_- thats not the one with 14 casualties, open the link please
What's the problem? They will just re-run all hacks :)
It`s possible that someone lost a lot of time fixing bug, that cannot exist
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 :)
http://mirror.codeforces.com/profile/Antoniuk and http://mirror.codeforces.com/profile/ngochai94 ? They spent a lot of time and organisators will ask them to be unrated????? time=money
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.
Did anyone say that this contest become unrated?
not unrated.. please...
Don't worry, it's not going to be unrated
Then it will be fair for all
in 12 mins lol
btw resize the picture a little bit!
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
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.
I agreed with you
Not sure if I should go to sleep and see the result tomorrow or wait for system test. . .
What is wrong with my submission ? http://mirror.codeforces.com/contest/633/submission/16358059
try 100000
answer is:
5 400005 400006 400007 400008 400009not 0
i <= 100000should bei <= 400010try to get the answer for m = 100000
<= 400009 :)
Why downvotes?
Am I wrong?
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.
your code doesn't work for n>=23000
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!
Editorials are out now.
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 :(
Well, none of us have ever seen "Pending system testing" and a lock on the same page have we :)
A few days ago, I wished the rating changes was announced fast. Today I am tired of waiting for the system testing
Plz just say when system tesing is running?? TIME LIMIT EXCEEDED!
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.
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.
suppose I don't follow the thread . what does it mean --> I don't care about the contest :D
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".
again :
when they came back , if the contest is important for them , they will check the thread :D
That means system test is about to begin, right?
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 :P
I think the case 3 people would feel aggrieved, as they wasted time unnecessarily mulling over why they got hacked for a correct solution.
Sure thing it must be case number 3
Cool :)
I am none of these cases btw. Was simply analyzing the solution. Pretty elegant one. Should suit nearly everybody :)
Please tell us when the system test gonna start :(
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.
How to solve H?
The expected solution was using MO's Algorithm.
I think that O(n * q) solution is OK.
UPD. He got WA due to overflow. Now, it's OK, 4929 ms.
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.
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/8369132792918835200
The complexity should be O(n sqrt(n) log(n))
Come on, start these systests. We all want to get our TLEs and go to bed.
It's almost 12 PM in my country. Am I going to know whether my solutions will pass before going to sleep? :(
3:15 AM in mine!
03:15 am in India!
2pm for me!
It depends on your mood :)
3:48 AM
5:48 AM
5am...
5:50am in China
From the comments replying you, it seems you're too lucky :D
12:00 am. Interesting how TooDifficult's comment has more upvotes than others who wrote the similar content.
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?
Finally!
At last our long desired system testing started !
Hashing fails for C :(
my hashing soluion for C passed
Congrats for picking the right constants :p
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?
My hashing + dp passed :D
Black day II?
Why are the system tests stuck at 72% ?
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?
Dynamic Scoring. The score of each problem will decrease according to the amount of accepted solutions (pretest passed) it gets.
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.
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 :)
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.
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!
Full score can also decrease. This is a special kind of dynamic scoring. Was used here also: http://mirror.codeforces.com/contest/550 , see how the maximum score for A became more than B in that case.
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?
why is the system test totally stuck and the site are dying ?
Codeforces back, System testing completed :D Backtracking optimized solutions passes for C: http://mirror.codeforces.com/contest/633/submission/16361771
Failed on D but ranking shifted just by 10, lot of fails on C/D
why this submission gets failed ?!?!?! 16362350
i mean due to time limit :|
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.
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?
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).
Had no idea about this. I have never seen this till now to be honest. This was an experiment it seems. Did it stick?
This is not an experiment. I have seen this before in another contest also. Please check link: http://mirror.codeforces.com/contest/550
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.
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.
Really strict and annoying final tests for C and D :(
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.
Any editorial? No? Why? Oh, OK....
)
Don't be sad: http://mirror.codeforces.com/blog/entry/43392
Where is an editorial?
Bottom of the ocean
Editorials are out now.
hello why my problem is Skipped in the cantest Manthan, Codefest 16??
......................
because u cheated for good !
Gaddammit. I failed E and lost 80 places because of an uncommented debug output.
Very sad indeed!
Use cerr
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.
There are more advantages to
cerrother than the fact that it's a different stream thancout, e.g. the fact thatcerroutput isn't buffered — if you print debug info usingcoutand your program crashes the buffered output might not get printed, but withcerrthis is never the case.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.
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++?
Same thing happened with me, TLE in D on 99th testcase :(
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?
+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?
My solution for A problem (http://mirror.codeforces.com/contest/633/submission/16362922) was hacked during the contest and the same solution is now accepted when i submitted it again (http://mirror.codeforces.com/contest/633/submission/16377008).
Infact the test case on which i was hacked is not itself valid.(1 1 100000) since range of cwas less than 10000.
HOW IS THIS POSSIBLE??
This might interest you. :)
Interesting, the editorial got hidden... You need to click this to see it — http://mirror.codeforces.com/blog/entry/43392 :) Well, it wasn't very pithy so it's not a big deal.
It was bad and buggy night for me :-(
Somehow upsolved C with regex'es (built-in backtracking), 1.1 sec. Perl — 16382698
Why my submission gets wrong answer in problem C ?!?!?! 16369028