Hello Codeforces!
I would like to invite you to Manthan, Codefest'19, which will take place on Sunday, August 25, 2019 at 8:05 PM IST. This is a combined Div. 1 + Div. 2 round and is rated for participants from both divisions.
The Department of Computer Science and Engineering, IIT (BHU) is conducting Codefest from 23rd August — 25th August. Manthan, the algorithmic programming contest under the banner of Codefest, is being held as a special Codeforces round. The round follows regular Codeforces rules.
All problems in this round were created and prepared by drastogi21, _shanky, Enigma27, _hiccup, KAN and me (hitman623).
A lot of thanks to KAN, 300iq, vintage_Vlad_Makeev, _overrated_, Rox for the testing and valuable comments, and to MikeMirzayanov for the awesome Codeforces and Polygon platforms!
Prizes -
1st place — INR 25,000
2nd place — INR 18,000
3rd place — INR 12,000
1st place in India — INR 6,000
1st place in IIT(BHU) — INR 3,000
1st place among freshers (1st/2nd Year) of IIT(BHU) — INR 1,000
Codeforces T-shirts to the participants who will be the first to solve each problem.
Participants will be offered 8 problems and 2 hours to solve them. As usual, the scoring distribution will be announced later.
Hope you guys enjoy the contest! See you on the leaderboard!
UPD: The scoring is 500 — 1000 — 1500 — 2000 — 2250 — 2500 — 3000 — 3750
UPD: The contest has ended. Congratulations to the winners.
1. tourist
2. Um_nik
3. EvenImage
First place in India: cerberus97
Following are the participants who were the first to solve each problem and have won a Codeforces T-shirt. Congrats!
A. IgorI
B. Geothermal
C. icecuber
D. ILoLy
E. nocriz
F. GoGooLi
G. EvenImage
H. tourist
UPD: We decided to give the 8th T-shirt to IgorI for problem A. Congrats!
The editorial has been published.
Hope to see you next year!
Finally some Indian Contest ..waited for it ..hoping for great problems.. last one was great
Waited for the whole year! Hope the legacy of greatness continues!
Lol, waited the whole year and didn't take part ....
Well, Such comments are only supposed to get upvotes. I am glad they both got downvoted.
Yeah lol, they "both" got downvoted.
Probably tourist will win the prize for 1st place ...
Probably? :)
Maby he doesn’t participate!
mani100011 ,he has been participating in Manthan since last two years :)
Maybe there will be surprises
It should be "must"!
You nailed it
The Legends battle are coming
Hope that I'll become a candidate master after this round! Div.1 + Div.2 is a great chance to promote my rating and I only need +8 rating to become a candidate master :D. And also, good luck to everyone!
Hope I'll become a grandmaster I need 65 rating and it is kinda impossible
Mr. Grandmaster orz
Mr. Grandmaster orz
https://codeforces.me/blog/entry/69261#comment-537171
tzc__wk wowowo
What is wrong with orz?
Nothing. Let's just orz. orz grandmaster who has 4 times the rating as me
If people spam something too much, it will become annoying. galaxybrain.jpg
I don't understand. Why this kind of comments should be downvoted...
"Codeforces T-shirts to the participants who will be the first to solve each problem.", well, this gonna be interesting
Yes,it will.And I think it doesn't matter if you do a great job or win a T-shirt or not,I think the
feeling during the contest is the most exciting thing！ And good luck to all of you!
Wow, an awesome contest ^_^
1st place is constant for tomorrow's contest if he participates.
Nothing is already played! wait for the leaderboard.
8 problems, 4 for div 2, 4 for div 1 or another?
Sorry for my bad english
There are 8 problems for all participants.
Div1 + Div2 means that everybody can participate. For example above 2100 can't participate in Div2. or the same for above 1600 and Div3.
Thank you very much
it mean that the contest for all participants. I think if you can achieved rank 1 in this contest, you will be +800 rating =)) good luck for u ^^
Thank you and good luck
Fan one piece :v
Please comment in English or Russian
I'm disappointed they scraped my e-mail from my profile and decided to send me spam.
It is an old e-mail, meaning that they did it some time ago and not just now near this contest, and I've never registered in their site.
The closest I got was participating in Codefest '18, here in Codeforces, but at that time, I used a different e-mail (a third one).
PS.: And even if they did it at that time (they didn't), nowhere it says they would send e-mails to registered participants.
Manthan, Codefest 18 (rated, Div. 1 + Div. 2) The Previous Manthan codefest contest .
last?
previous*
8 problems for 2 hours?? Isn't that too tight?
It's combined round (Div. 1 + Div. 2), the high rated coders will be bored if they solved all the problems quickly. you can see that tourist solved all the 8 problems of Good Bye 2018 in less than 2 hours, also few contestants solved all the 8 problems of last year Manthan, Codefest 18 in less than 2 hours.
i think tourist will continue to win
I hope that I will raise my rating to 1500-1600
Wow.... Such a big prize
$$$出题人家里有矿_{泉水}$$$
Any update on scoring distribution?
I relize that lots of people use anime avatar like me ^______________^
Wow, it's so InTeReStInG !1!! (No)
None of the other severs (m1.codeforces.com), (m2.codeforces.com), (m3.codeforces.com) seem to have the contest added in there?!
Have been participating regularly for the past 2 editions of this contest and had lots of fun.
Hope everyone has fun this time too :)
not able to register before 5 minutes of contest... why??
can someone submit? it keeps loading
It's legendary grandmaster battle. I can't wait to see that. All top 3 highest CF rating have already register, who will win???
let's guess who will win .. tourist ofcourse
He is on 1st place =))
R.I.P queue
VERY long queue
What was the pattern for 1208C - Magic Grid?
Use subsquares 4x4 of numbers 0-15 MOD 16 like (0, 1, 2, 3), (4, 5, 6, 7), (8, 9, 10, 11), (12, 13, 14, 15) — it has zero XORs and prefixes are repeated 4 times, thus their XOR is also 0.
Very nice solution bro, I also thought about that thing, I saw with n=4 and n=8 we can easily solve the problem, just write sequence 0..(n^2-1) from left to right and from top to bottom, but then I couldnt figure out how to use them for another multiple of 4 numbers and your solution helps me a lot. Thanks again!!!
0 1 2 3__________16 17 18 19
4 5 6 7__________20 21 22 23
8 9 10 11________24 25 26 27
12 13 14 15______28 29 30 31
32 33 34 35_____48 49 50 51
36 37 38 39_____52 53 54 55
40 41 42 43_____56 57 58 59
44 45 46 47_____60 61 62 63
Why not doing it in a nice order?
Everyone is giving example of 8x8, how to extend this to 12x12?
Edit: To extend, order doesnt matter, just place those new 4x4 matrices anywhere. All will be 0. Good god.
It is simple: every 4x4 subsquare has 0 XORs, so you can arrange them in any way.
Yeah, just realized.
B question was good. Took more than 1 and half hour to understand it what's it trying to say and implement it.
Thanks for this contest IIT BHU :) . Cheers!
It also took me 1 and a half hour. I am not even sure whether it is correct or not. Let's see the system testing results.
How to solve C, it seems much harder than D and E
Fill that array in increments of 4 like
0 4 8 121 5 9 132 6 10 143 7 11 15This way xor will always be zero of all rows and columns.
not necessarily zero. When n%8 equals 0 then it will be zero else it will be 13.
Some one here said that B was harder than C. And you say that C is harder than D and E. It took me more than one and a half hours to get the B pretests correct. I am thinking whether I should I have skipped B.
tourist achieved top 1 is really very normal =))
How to solve C?
I feel D was easier than C :(((
Oh dear, I got bug at D.
Dunno whether my C is correct. Btw I use the fact that I can construct a grid for numbers 0->15, then I could construct numbers for 16k->16k+15
U can find a pattern that if you break the given nxn matrix into 4x4 matrices with increasing values (For ex: 0 to 15, 16 to 31 etc) , you can make all the rows and columns have xor sum = 0.
Find my submission here :)
nice trick, thanks
Could you please share your idea for D? :)
Mine is Nlog^2(N)
basically binary search + segment tree
I start filling the answer array in reverse order, Binary search on all feasible values to check the following condition
I used pbds for convenience. thats not needed.
How did you find this pattern ?
They had emphasized that n is a multiple of 4. So I wrote down the binary representation of 0 to 3 ( i.e first 4 numbers, and realized their xor was 0).
That was the beginning of the idea, and developed the pattern.
Great! :D
This is my approach:
Divide the whole matrix into 4 * 4 matrices. Then fill every matrix with slight modification of a valid answer for a 4 * 4 matrix. I used the result of test case 1 of the problem statement. Keep a variable that tells us the number of matrices that has been processed. Left shift counter variable by 4 and then perform bitwise OR operation with the corresponding number of the initial matrix while assigning.
Will it be correct? Yes, because the XOR of each row and column of every 4 * 4 matrix will be the same. So, if you use test case 1, then the XOR of each row and column of the whole matrix will be 13 or 0.
Will any number repeat? No, because we are using counter variable. Every number has 4 initial bits with 2 ^ 4 possible combinations. These are covered by the initial matrix. We just need to cover the extra bits. The counter gives us new combinations of the extra bits, starting from the lowest. By performing bitwise OR, we are reaching each bitwise combination. So, we will hit each number once.
My submission can be found here.
How to solve D ?
I did it with a lazy segment tree, but there seems to be a way to do it with just a regular segtree/fenwick tree. In the sequence you get, the last 0 is always the 1 in the original. If you imagine that you remove the 1 you found and subtract 1 from every item after that you would get a similar sequence for 2..N. Then you find the last zero again, which now is the 2 and you subtract 2 from everything after etc. You use a lazy min segment tree to find the last zero (order by value and index) and to do the range subtractions.
I thought of this idea last 5 mins before contest end, indeed can't implement it.
Thank you anyway :)
Pretty much the same. Thought of it 15 mins before, but min segment tree + lazy, gave up there itself >.<
I also got the solution quite late, but I copy pasted the segment tree from kactl. It's a really nice repo with lots of standard CP things.
Try to recover the answer from the end of the array..
When $$$n\ =\ 4$$$, you can notice that when the last element of the given array is 0, 1, 3, 6, then the last element of the answer array is 1, 2, 3, 4. Depending on this info, the corresponding (value of the last element of the given array, value of the last element of the answer array) for prefixes change. Try to draw and think about that -- it's pretty easy from this point.
Probably, if you got here, you want to know how to compute that -- use Fenwick tree with range update and point query. You can search for an article on geeksforgeeks and check tourist's solution.
Oh dear, that's so simple. I don't know I have done.
Fenwick tree with range query and point update I think
most of the WA10 because of something like this :
My code passes this but fails on system test 50. 59469362
What is test #5 of D?
// 1 4 3 2
4
0 1 1 1
Are you sure? I failed on pretest 5 but my code gives correct answer here.
no it could not be that. My code gives the correct answer
//9 5 3 4 1 6 2 8 7
9
0 0 0 3 0 13 1 21 21
I was able to solve C but couldn't solve B. :( Was B more tough than it is supposed to be??
Thanks for the short statements
I must be crazy. I think the problem should be like ABEDCFGH...
Is there any way to solve D without converting it into a Segment tree RMQ problem? I saw the number of submissions and thought I probably need to think simpler.
You can use fenwick tree with range update and point query.
I only used std::priority_queue.
Could you explain your solution?
I break each range into two “operations” one is insertion and another one is deletion. Then I sort the operations in ascending order of position to solve it offline
Can it be done offline? Don't you need to update every range to know the next range to be updated?
I divided the array into 2k non overlapping interval, where k is the width of the bar. So we can update them in any order
When in the last 20 minutes of the contest you start doing problem D but in the last 9 seconds you submit it without any tests, because you just finished coding it, and you misstyped a -=, instead of typing +=. I've neve felt this bad before ;(
PS: Submission during the contest: https://codeforces.me/contest/1208/submission/59484539
Submission after the contest, after changing the signal: https://codeforces.me/contest/1208/submission/59486030
hard contest for me but I enjoy it very much. Thanks :)
How to solve E in time? I had a made a sparse table solution and then just iterated over all of the columns but I couldn't figure out the final optimization. At the end I tried to use a lazy seg tree to propogate the maximum over all columns where the the array can take all of it's values. Is this the right approach?
B and D are not good problems. C is nice
I love how tourist was able to get 500 on A (submision time 52s) :-)
Keep up to date (hipozhor)
3 miniutes for D and 2 minutes for C is unbelieveable
Guys, I know what happened. tourist obviously cheated. See for yourself:
How can he start coding at 17:33:16 if the contest started at 17:35:00? I knew something wasn't right about him, but now he gave himself away!
I would disqualify everybody whose handle starts with
tas a warning.majk Come on. It can be possible that he might have created pre template file for A problem before the contest. We all do a little preparation.
How would he know there's a problem A? You're only making this worse.
The best utilization of last ( extra ) five minutes : tourist submitting H at 2:03
How to solve 1208E - Let Them Slide?
Can someone give a quick editorial of B.
You can delete either:
You will be left with (respectively):
Basically, (1) and (2) are the same as (3) if you assume that there is an empty prefix/suffix.
So, what you can try to do is for each prefix (empty, too) find the largest suffix satisfying the conditions -- what is left between them is exactly what you delete, take the minimum of all such gaps.
The simplest way, according to the given constraints would be to add each element in the array to a set. Then for every index i starting from 0, we traverse j left to right from i, generating every subarray starting at i, and trying to remove each element from the set and check if size of the set at any point is N- (j-i+1). We stop the first time it happens and we've found the smallest subarray starting at i. Then we increment i again, but before doing that make sure you add back the i'th element to the set. It will be O(N^2 lgN) There's also an O(N) solution by the way, that I used.
N2logn is giving TLE
My solution passed with
358 mshaving the same complexity :)My solution got Accepted with the $$$O(n^2\ log\ n)$$$ complexity too
Yours is a $$$O(n^2 log^2 n)$$$ I think.
I also got a TLE in n^2logn.My submission
You are using a $$$map$$$ inside the binary search. That would make it $$$O(n^2 log^2n)$$$
you can try two pointers to solve that...i am not sure,but I have passed the pretest
Okay, why lot of
system test failon B?I solved C with something really easy: I print all even numbers first then I print what is left. For example for n=4 my output will be :
Incredible.
Definitely the best solution here :D.
It is also easy to prove that it is correct — lines have XOR of 0 trivially (split them by 4) and every consecutive even-odd pair in each column have XOR of 1. There is even number of such pairs, so the total XOR is also 0.
so sad I thought C xor will be zero because it looked impossible to guess some number but didn't know how :'(
you can solve it with xor equals zero, just look at my comment
At least 3 persons on my friend list who got F accepted fail this test:
Please look into this.
I got uphacked (59479538) by
Because I looped the number to or with up to the last number, instead of to the third-to-last. The tests were definitely pretty weak :P
why codeforces don't compare codes like this 59482093 and this 59481769
tihs is not fare
Can we solve B using Binary Search?
Yes. I solved it using binary search. Code Search space is the answer range i.e. [0,n]. isValid function checks if it's possible to delete 'mid' number of values such that rest of them are distinct. I used map to store the values and their frequencies in the 'undeleted' array. If the size of map is n-mid for some undeleted part, it means that all the undeleted elements are distinct.
I think you can.If deleting a large portion from a given position gives you a valid sequence then you can check for even smaller portion.
What id test 54 for B ?
Guys, I've found a really nice solution for C.
The Ideea is this: Put even numbers in increasing order on odd rows and odd numbers on even rows.
Ex: n=4 0 2 4 6 1 3 5 7 8 10 12 14 9 11 13 15 This is 100% correct and much easyer to implement. :)
How to solve F?
Could anyone explain why this solution 59478005 for F works?
My solution: We want to be able to fix a_i and compute the best (a_j&a_k) for that a_i quickly. To do so, we iterate through i from large to small, and maintain an array cnt[bit] which stores the number of elements among $$$a_{i+1}, a_{i+2}, ..., a_{n}$$$ that have bit as a submask. How to we update cnt? Note that we only need to know if cnt is >= 2 or not. Now, when we have a new element $$$x$$$ to be added, we do something like a dfs, starting by adding 1 to $$$cnt[x]$$$, and then recursing on all submasks of $$$x$$$ that are one bit away from $$$x$$$. If at any point of time we visited the same number or cnt[x]>=2, we can terminate because we know all submasks must also have cnt>=2. Thus, the complexity of updating cnt is amortized $$$O(n\log a_i)$$$. Finally, with the values of cnt you can also find the best answer for a fixed $$$i$$$ in $$$O(\log a_i)$$$ time.
thank you a lot!!
By the way is there any method which allows an update in sos dp?
can you tell, where my code for B fails?
My Solution
Check this test case: 8 1 2 3 4 1 6 5 4 The correct answer is 2.But your code gives 4 as the output. I guess most of the solutions got failed at system testing in these type of test cases.My solution got failed too.
Thanks, got your point.
I think we went wrong in trying to implement B in o(n).
Constraints are the real insights to the problems.
Try this one:
Why does solution for B in $$$n^2 \log^n$$$ give TLE? I used both binary search and sets (I know it's not the most efficient), and couldn't get it accepted. TLE on test 18. Can anyone help?
$$$n^2\log^2n$$$ is roughly 43587196 ops at n=2000 which should work in under 2secs imo.
Submission
You might have a miscalculation.
4million*log*log is around 400 million, which might not pass because of set constant.
You took the log to the base 10. Base 2 would be more realistic and then it's already $$$5*10^8$$$, also set::insert probably has some additional constant factors.
Can someone please point out the logic flaw in my solution for problem B?
PS: Found my mistake. Thanks everyone.
Same for me mine also getting wrong at testcase 54.
Check out my comment above
Try this one:
Можно ли как-то полностью посмотреть 85 тест в задаче B, так как на нем программа выдает неверный ответ?
Контртест к твоему решению: 6 3 3 1 4 3 3 Твоё решение дает ответ 3, правильный — 5
I didn't leak code to anyone but I receive system's message :'(. May be this is an accident
My Solution for B, fails on test 54 but I don't know why? Someone please help! LinkL: https://codeforces.me/contest/1208/submission/59459333
Edit: I found my mistake, Thanks
So tourist doesn't get two T-shirts? :sad:
It is totally unfair to me . I have solved the second problem completely with required time complexity even than your website is showing TLE . Why? Do something otherwise it is totally waste of time for me to participate in challenges on your website
Maps are not constant complexity. Expected complexity was O(n²log(n)), not O(n²log(n)log(n))
The CF judge is fair to everyone. It's just because your solution is too slow. Having a solution of intended time complexity does not necessarily mean it must pass.
No one cares if you participate or not. This platform is for everyone to learn and improve. If you have done a mistake try to accept it and learn from it, instead of complaining.
I was able to pass pretests with my too complicated solution for G, but I got TLE on one of the pretests during system testing. Moreover, after the contest I submitted the same code 10 times, 9 of those 10 attempts got AC. Maybe solutions should not be rerun on pretests during final testing, to prevent such disappointing situations in the future xD
1179 contestants solved segment tree problem. It seems like CF is "growing up" or I am "growing down".
I solved B in more than 13 minutes and solved D in less than 10 minutes.
I think I need more "IQ"...
I can't solve C because I'm not good at constructive problems. I think I should practise it more.
tourist returned to 3700+ in 31 months.
Can someone tell why my code 59471606 of B problem gave wrong answer on pretest 9? It gives same output as jury's output when I run it in my system.
How to solve D,I don't understand the editorial ?
If the input is valid, as the problem statements says, there is always an answer and it will be unique.
Let's build from the last element in the array to the first one. Also create a data structure that can query the sum of all values in range[0, r] and update a point in log.
Whenever you try to put some number into the answer, it will have sum of all the other unused numbers, because they will be somewhere before it in the answer. Initially, all numbers are available. So you can do N updates like:
update(i, +i).As you know the sum of all numbers before it in the array, just binary search what element have exactly the same sum as the input, then remove it from the answer like:
update(i, -i).Suppose that you initially have
1, 2, 3, 4, 5. So, your data structure will be:1, 3, 6, 10, 15.If you want to put an element with sum 6, you should put element
4as the last one, then your data structure will look like this:1, 3, 6, 6, 11.Keep doing this and you will end up with the answer.
It seems a same approach with mine (and different with the editorial).
However, I don't know how to deal with such condition:
n=5, the sequence is 0 4 0 1 1
0 1 3 6 10
(the last one is 2)
0 1 1 4 8
(the last one is 3)
0 1 1 1 5
Now, there are three 1 can be chosen (in fact, the third 1 is correct), and how can my program deal with such condition in appropriate complexity.
You should always try to find the last one element that have the same sum. If the data structure is like ... 0 1 1 1 1 2 ... And you are searching for 1, just get the last 1.
If you put another value except from the last, you can't build the answer.
Thx! I do exactly the same thing as you say and got WA on 9. However, it turned out to be that it is "long long" which made me get WA. QAQ
You can also improve your answer by removing the binary search, just traversing the segment tree.
If you are in a vertex searching for something with sum
x, then:if left node have
sum >= x, then call left vertex withxotherwise call right vertex with
x - left_sumHow is it possible to solve A in 52 secs if statement loads for half a minute xD?
I believe the writers of problems couldn't have beaten tourist for the first 7 problems if they implemented the solutions from scratch.
Read the statement in 6s, write the code in 13s and submit in 3s
You can open problem statements much faster using m1.codeforces.com
Tried to do it, didn't help at all :P
BTW, it took me less than 15 seconds to load the problems.
Tourist is such a monster！
I think we should swap problem C and problem D.....
I tried to solve the second question using binary search on the length of segment to be removed. The pretests passed but I got TLE in the final testing.
http://codeforces.me/contest/1208/submission/59462841
Can someone tell me what went wrong ?
why I dont see the prize for first solve of problem H in the list above while there is someone has solved this in the contest, can anyone explain this for me?
How to solve G? It seems like a math problem about divisors, and the AC code looks very simple. However, I did not understand the behind logic yet. Anyone can help?
Have you read the editorial?
I did not notice the editorial. Now I understand. Thanks!
Can someone help me with the code for B problem? Here is my code:
Can Any one explain Problem D ??
Request for future contests :: Please make large inputs downloadable
If you've solved problem D. And want to solve another interesting problem like this. Try Lightoj — Lining Up Students In Lightoj one need a account in case of view a problem. In case you don't have an account there you can read the problem here
asd
hello my fan
Codeforces is too easy to me
Can I get some help to solve B...This was my code https://codeforces.me/contest/1208/submission/59474361 ...Why am I getting TLE...As much as I can see, the solution will execute 6.4*10^7 instructions at max
Operations on
unordered_mapare often more than 1 instruction, and the $$$O(n^{2}logn * map)$$$ will probably have a bad constant and run for longer than expected.Some improvements:
The actual elements in the array don't matter, only that they're unique. Therefore, you can compress coordinates and use a boolean array (or bitset, if you really want) instead of a map. This alone should get you under TL.
The binary search doesn't actually help you. Since the
checkfunction is $$$O(n)$$$ anyway, you may as well get rid of the $$$logn$$$ factor by just finding the first location, iterating from the right tor, that creates a duplicate (of course, include the elements to the left oflfirst and account for duplicates there)And because three is a good number, even though this isn't necessary, your loop in
checkskips over a lot of elements. Eachcontinuecan cost you, and it will be better to splitcheckinto two loops.Thanks :-)
Was anyone able to get AC with binary search on B ? If yes can you share your solution ?
59512345
The problems are good.
Hmmm. Is the difficulty point of H right???
It seems to be fixed now, I've messaged Mike about this.