By BledDest, 2 years ago, translation,

Hello, Codeforces!

On June 27, 17:35 MSK Educational Codeforces Round 46 will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

As usual, the round will be rated for the participants with rating lower than 2100. It will be held on extented ACM ICPC rules. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were prepared by Adilbek adedalic Dalabaev, Roman Ajosteen Glazov, Mikhail PikMike Piklyaev and me.

Good luck to all participants!

UPD. The editorial is here.

I also have a message from our partner, Harbour.Space University:

Hi Codeforces!

For our programming boot camp’s next iteration of Hello Barcelona Programming Bootcamp, Harbour.Space University in collaboration with Moscow Workshops ICPC, ITMO University, Moscow Institute of Physics and Technology, Saint Petersburg State University and Codeforces is bringing the best training practices and coaches to Barcelona to prepare 150 students for winning medals in the next ICPC World Finals.

It's extraordinary to see the entire cultural spectrum meet at the boot camp over a common love of programming and learning, and this autumn, we will be doing it again.

Our boot camp will once again feature the all-time greats Mike MikeMirzayanov Mirzayanov, Andrey andrewzta Stankevich, Michael Endagorion Tikhomirov, Gleb GlebsHP Evstropov, Artem VArtem Vasilyev, Ivan ifsmirnov Smirnov and other world renowned Russian coaches to train the participants.

Expect the most challenging problems, surprise guests and speakers, a branded hackathon, and finally the online round held on Codeforces, so everyone can join the onsite participants, at the finale of the event.

During the nine days of the event from Sept 26 to Oct 4, 2018 in Barcelona, teams will be participating in practice contests, problem discussion sessions and lectures.

You can ask any questions by email: hello@harbour.space

UPD: The contest is over.

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Farhod_Farmon 7 353
2 MrDindows 7 362
3 tzuyu_chou 6 205
4 Wild_Hamster 6 248
5 spj_29 6 252

Congratulations to the best hackers:

Rank Competitor Hack Count
1 halyavin 225:-5
2 Marcosk 22:-3
3 sfialok98 5
4 Rhouma 4
5 FakeGuy 3
307 successful hacks and 245 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A 300iq 0:01
B HIT_Zero 0:13
C Dalgerok 0:07
D ruhan.habib39 0:08
E Dalgerok 0:14
F MrDindows 0:17
G chemthan 1:13

• +182

 » 2 years ago, # |   +25 Will hacking phase be just 12 hours from now on?
 » 2 years ago, # |   +8 Hope we won't wait till the next morning of the contest to know the result and rating changes :D
•  » » 2 years ago, # ^ |   +9 We will, hacking lasts 12 hours
•  » » » 2 years ago, # ^ |   +8 But usually we wait for along time after hack phase ends.
•  » » » » 2 years ago, # ^ |   +3 i hope we won't wait :(
•  » » 2 years ago, # ^ |   0 But I have to wait until the next afternoon (or the next evening, for the poor speed of system testing and rating changing) as a Chinese. I just want to have a good sleep (instead of staying up late) and can see the rating changes as soon as I get up.
 » 2 years ago, # | ← Rev. 2 →   +20 What does Codeforces have against Mexicans? That's two rounds at the same time as Mexico's matches in the World Cup :'(.
•  » » 2 years ago, # ^ |   -33 luckily for you they never make it past the fourth game.
•  » » » 2 years ago, # ^ |   -27 Just like you'll never make it to Candidate Master
•  » » » » 2 years ago, # ^ |   +2 Yikes... -1
•  » » » » » 2 years ago, # ^ |   +12 I guess he'll make it to Candidate Master lol
•  » » » » » » 2 years ago, # ^ |   0 I guess I will.
•  » » » » » » » 2 years ago, # ^ |   0 I guess he did. Well done.
 » 2 years ago, # |   +54 Hope to see good problems,not just implementations.
•  » » 2 years ago, # ^ |   0 Yeah true. Problem A and B should be implementation then after all problems must concentrate only on logic.
 » 2 years ago, # |   +55 1000th contest
•  » » 2 years ago, # ^ |   0
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 yeah,how time flies!
 » 2 years ago, # |   +11 I expected special round for anniversary contest :(
•  » » 2 years ago, # ^ |   +57 To me, all rounds are special :)
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Maybe it is a special round? Maybe there will be fast syste... Oh no, fast systests won't help, there is 12 hours long hacking phase...
 » 2 years ago, # |   +6 can i hack which problem i have not solved?
•  » » 2 years ago, # ^ |   +9 yes! you can.
•  » » 2 years ago, # ^ |   0 And you can copy anyone's solution before you hack others.
 » 2 years ago, # |   +74 Most of the hacking is done in first 2-3 hours. Mininize hacking phase to only 6 hours
•  » » 2 years ago, # ^ |   0 thanks bro...
•  » » » 2 years ago, # ^ |   0 welcome & all the best for contest
•  » » 2 years ago, # ^ |   +35 I agree. It is annoying to wait 12 hours
•  » » » 2 years ago, # ^ |   -29 still less annoying than ur annyoing comments
•  » » » » 2 years ago, # ^ |   +17 Mock him all you want, he is Numb
•  » » » 2 years ago, # ^ |   +22 Still less annoying than ur usual comment
•  » » 2 years ago, # ^ |   0 Couldn't agree more.
•  » » 2 years ago, # ^ |   0 But then Chinese will have to not only stay up to participate in contests, but also keep staying up after the contests to hack.
•  » » 2 years ago, # ^ |   +8 Mmm... I made 16 hacks in the last 4 hours of hacking phase, and only 6 in the first 2 hours. I think 24 hours was too much, but 12 hours is not that bad!
 » 2 years ago, # |   +15 12 hours to hack is toooooooooo long.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +3 I agree with you. The rating changes are always come out at the second day when we have an Educational or Div. 3 round.
 » 2 years ago, # |   -25 Messi Is back xD
 » 2 years ago, # |   0 What does one mean by hacking problems? This would be my first contest of this type. Can someone please guide regarding the rules and terms ?
•  » » 2 years ago, # ^ |   +4 After The Contest ended.....everyone Can See your solution and if he found anything wrong he can hack you and the problem won't be Accepted
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 If my solution gets hacked, it will not be accepted and I will lose points, what will the hacker get ? Thanks for the reply.
•  » » » » 2 years ago, # ^ |   0 nothing
•  » » » » 2 years ago, # ^ |   +6 in Educational Contest He Won't Get Any Thing Except if he made a lot of hacks he will became from most hackers of Contest But Also he won't Get any Points.But in Usual Contests He Can Hack participants in his room in Codeforces after locking his problem and if he hacked any one he will get 100 points and if he make Hack But it was unsuccessful He will lost 50 points
•  » » » » 2 years ago, # ^ |   +7 pleasure.
 » 2 years ago, # | ← Rev. 4 →   -10 The 12 hour hacking seems to be useless as no one will waste that long time once they comes up with some hacks they tries them and leaves the site.I can't understand why i am getting this many downvotes
•  » » 2 years ago, # ^ |   +8 Some people just want to watch the world burn!!
 » 2 years ago, # |   +28 Seems people are agreeing on minimizing the hacking phase...
 » 2 years ago, # |   -27 i thinks educational hacks shoud give some (points) (reduce time)
•  » » 2 years ago, # ^ |   -28 so it will encorage people to hack (like me)
•  » » » 2 years ago, # ^ |   0 *encourage :P
•  » » » » 2 years ago, # ^ |   0 You hacked his comment.
•  » » 2 years ago, # ^ |   +6 Educational rounds are created to solve problems and not to hack
•  » » » 2 years ago, # ^ |   0 This is a reason why the hacking phase should be minimized.
•  » » » 2 years ago, # ^ |   +2 so why rating changes .. ?!
 » 2 years ago, # | ← Rev. 3 →   -136 now he is dead
•  » » 2 years ago, # ^ |   +4 how can codeforces community help you?
•  » » 2 years ago, # ^ |   +4 keep this fb thing there itself :|
 » 2 years ago, # | ← Rev. 2 →   -6 Problem A fucked me deep....
•  » » 2 years ago, # ^ |   +30 The weird thing is you commented this in the middle of the contest!! Man, during the contest you should concentrate only on solving problems.
 » 2 years ago, # |   +14 problem E is not clear at all and explanation for the sample input/output is also missing.
 » 2 years ago, # |   -83 code force is retarded. edu round is dumb. your all dumb
 » 2 years ago, # |   0 What happened to 300iq ???
•  » » 2 years ago, # ^ |   0 Left a record in the standings of contest 1000 and plunged into problem preparation. (I guess)
 » 2 years ago, # |   +2 Nice contest, thanks, problems B, D and E are really nice. Problem A kinda awful though.
 » 2 years ago, # |   0 TASK F looks for wavelet tree or persistent segtree's.
•  » » 2 years ago, # ^ | ← Rev. 3 →   +36 You can do F with regular segment tree.The idea is to sort queries by start-index, and only keep indexes i, such that index i is the first time number V[i] appears in [start-index, n).For each such number, store where the next same number is.Now, you just want to find the maximum element in an interval. If it's not large enough, answer is 0. Otherwise, its value is the answer.When moving to the next query, loop from last-start-index to start-index — 1, deactivate those indexes, and activate indexes of their values's next appearances. ExampleLet's keep pairs in the segment tree to easily get what is the number with maximum index of next appearance.Say our array is [1, 2, 1, 3, 2, 2, 3, 1], and we have the queries 1 3, 2 6 and 3 8.Next-array: [3, 5, 8, 7, 6, 9, 9, 9] (one-indexed)Initial state (start-index = 1): Active-array: [1, 1, 0, 1, 0, 0, 0, 0] Values in segtree: [{3, 1}, {5, 2}, {0, 1}, {7, 3}, {0, 2}, {0, 2}, {0, 3}, {0, 1}] To answer query 1 3, we find the maximum in the interval [1, 3]. It is {5, 2}. 5 is larger than the endpoint of the query, so we output 2.Now we have to move start-index from 1 to 2. To do this, we activate the next appearance of the number at index 1, and deactivate the number at index 1.State with start-index = 2: Active-array: [0, 1, 1, 1, 0, 0, 0, 0] Values in segtree: [{0, 1}, {5, 2}, {8, 1}, {7, 3}, {0, 2}, {0, 2}, {0, 3}, {0, 1}] To answer query 2 6, we find the maximum in the interval [2, 6]. It is {8, 1}. 8 is larger than the endpoint of the query, so we output 1.State with start-index = 3: Active-array: [0, 0, 1, 1, 1, 0, 0, 0] Values in segtree: [{0, 1}, {0, 2}, {8, 1}, {7, 3}, {6, 2}, {0, 2}, {0, 3}, {0, 1}] To answer query 3 8, we find the maximum in the interval [3, 8]. It is {8, 1}. But since 8 <= 8, no number appears only once in the interval, and we output 0.
•  » » » 2 years ago, # ^ |   +3 thanks.
•  » » » 2 years ago, # ^ |   0 A very nice solution!
 » 2 years ago, # |   +7 A & B & C are mostly implementation problems. Is this really Educational round? Educational rounds used to be different.
•  » » 2 years ago, # ^ |   +43 I think you haven't read D, E, F, G. These problems are just like what you would expect to find in a usual Educational round.Also, I don't think the implementation in C is too heavy. A has an elegant and short implementation.
 » 2 years ago, # |   0 How to solve G?
•  » » 2 years ago, # ^ |   +41 What is the story behind your username mango_lassi? You don't seem Indian to me.
•  » » 2 years ago, # ^ |   0 Key idea, in my opinion, is to calculate for each i dpi — maximal profit of 2-path starting at i and finishing at i. If i is a root of tree, then dpi is just pretty standard dp for subtrees. To calculate dp for each vertex as if this vertex is root — it's possible with technique of "rerooting" (actually, I don't know it's real name as I don't know where to find materials to this quite standart technique).
 » 2 years ago, # |   +2 How to solve C?
•  » » 2 years ago, # ^ |   +8 Classical scanline problem.
•  » » » 2 years ago, # ^ |   +1 Explain pls. I know its easy (got that by seeing the number of solves) but I couldn't figure it out.
•  » » » » 2 years ago, # ^ | ← Rev. 3 →   +3 What would we do if constraints were small? Use partial sums!So now we can do similar thing just using map instead of arrays for partial sums.How to solve D though?P.S : I think there is even a way of doing it without using maps. I am unaware of that sorry!
•  » » » » » 2 years ago, # ^ |   +4 Let dp[i] denote number of good subsequences ending at i. So a subsequence will be divided into parts which are good. Now look at the last part of the subsequences which end at i. Let the start of the last part of that subsequence be j. So dp[i] = sum(((pref[j-1]+1)*ncr[i-j-1][a[j]-1])) because we have to choose a[j]-1 elements between i and j to complete that part and the subsequence can be completed by the rest of the parts ending before j.
•  » » » » » » 2 years ago, # ^ |   0 Why are you adding +1 to pref[j-1] when taking the summation?
•  » » » » » » » 2 years ago, # ^ |   0 Suppose you have m queries with l and r.(Array of size n)Now you can traverse the array 10 times incrementing values between l and r.It take Time Complexity O(n*m). OR u can put +1 on l position and -1 on r+1 position.After inserting u can just traverse the array a single time to get the final array.O(m+n)
•  » » » » » » » » 2 years ago, # ^ |   0 No i got how to solve C. I was talking about D and T1duS's method as to why we are adding +1 to pref[j-1]. I got it though. It's because one of the subsequences would be starting at j and ending at i and we ignore the subsequences before that. Add those many subsequences to the number of subsequences starting at j and ending at i multiplied to the number of ways of ending subsequences at j-1. That will be the ans for dp[i].
•  » » » » 2 years ago, # ^ |   +5 You can read about it here.
•  » » » » 2 years ago, # ^ |   +1 For a given segment say [x y] mark x with +1 and y+1 with -1 and store it. Now just visit these points and check the running sum,and update the running sum on a array with the number of coordinates in between,i.e a[running sum]+=numberofcoordinates,print this array from 1 to n as given.
•  » » » » » 2 years ago, # ^ |   0 Thanks
•  » » » » 2 years ago, # ^ |   0 What I did was create a map with the # of the segments that started and ended at a certain point. Then I traversed the points in order, keeping a variable that kept track of the current number of segments. I treated the intervals (spaces between points) and the endpoints separately. Make sure to use long longs.
•  » » 2 years ago, # ^ |   0 keep a map of indices of segments and use it as partial sum. Though it struck me a little late. Solution(Easy to understand)->http://codeforces.com/contest/1000/submission/39725149
 » 2 years ago, # |   -51 Codeforces contest is not as good as it was before .
 » 2 years ago, # |   +11 Wanna ask a question:What should a person do after finishing problems he can do in an Educational Round?(As for me, only problem G left, and I have about 20 minute, then I know how to solve G but I know I can't finish in 20 minutes.Then I have nothing to do in these 20 minutes: sitting there pushing F5 and seeing my rank falling.So guys, how do you handle these time ? :) (One may hack in a normal round)
•  » » 2 years ago, # ^ | ← Rev. 2 →   +16 I would do nothing, but enjoy looking at standings (because you solved 6 problems).
•  » » » 2 years ago, # ^ | ← Rev. 2 →   +13 But you didn't...... Edit: Oh I see what you mean, never mind
•  » » » 2 years ago, # ^ | ← Rev. 2 →   -10 Well bro, I didn't find you in the standing ???I don't know, maybe you are an accurate one, so waiting won't be a bad choice.But almost every contest I participated, I "die from" penalties(wrong submition). So even if I finished early, many who finished after me will have a higher rank than me.How should I deal with that? (Yeah, yeah, yeah, control my hands)
•  » » » » 2 years ago, # ^ |   +14 Here I meant you solved 6 problems.But almost every contest I participated, I "die from" penalties(wrong submition). So even if I finished early, many who finished after me will have a higher rank than me.Yeah, you're right, but if they add feature that allows to hack solutions during the contest there is no need to hold special educational rounds, so I still recommend you to enjoy from your results XD
•  » » » » » 2 years ago, # ^ |   +5 Sorry I misunderstood you.And feel guilty that I downvoted you yesterday. :(Please forgive me.P.S.: But still, I didn't solve 6 problems... :(
•  » » » » » » 2 years ago, # ^ |   +14 But still, I didn't solve 6 problems I'm sorry for that :(
•  » » 2 years ago, # ^ |   +56 try to find bugs in your own solutions so they don't get hacked
•  » » » 2 years ago, # ^ |   +74 You are right!
 » 2 years ago, # | ← Rev. 2 →   +8 For E does this work?1) Find all cycles, and mark each edge in a cycle with 0 (and keep all other edges marked 1)2) Start at a random node, and find the farthest node from it through a DFS, but by "farthest" i mean weighted distance where the markings denote weight. Denote this farthest node X3) Similarly find the farthest node from X (with weighted distance, where edges in cycles are distance 0 and edges not in cycles are distance 1), denote this node Y.Y is the answer
•  » » 2 years ago, # ^ | ← Rev. 2 →   +32 Yes. Though an easier way to think about it is diameter of bridge tree.
•  » » » 2 years ago, # ^ |   +6 Never thought an E problem could be explained in a single line, beautiful!
 » 2 years ago, # | ← Rev. 4 →   0 Never mind, it is indeed diameter
 » 2 years ago, # |   0 Hacking page is not loading..!!
 » 2 years ago, # |   0 Can Problem C be solved using Mo's algorithm?
•  » » 2 years ago, # ^ |   +10 C? I don't think so. Doesn't even look like a Mo problem.Though F definitely has a Mo solution :D Our model implementation works a bit over TL (like 3.4 seconds) but couple of participants actually squeezed it.
•  » » » 2 years ago, # ^ |   +3 Can you please explain how to keep answer? I used unordered set, but I still getting TL
•  » » » » 2 years ago, # ^ |   +7 You can store not the hashset but the whole array of number counts. Then you do sqrt decomposition over this array, you make updates in O(1) and then ask in . I believe, the code is pretty much self-explainatory.
•  » » » » » 2 years ago, # ^ |   +3 Isn't this Mo's Algorithm?
•  » » » » » » 2 years ago, # ^ | ← Rev. 3 →   +4 There are both Mo's algorithm and sqrt decomposition)
•  » » » » » 2 years ago, # ^ |   0 What is the time complexity of such a solution, wouldn't using a set reduce it (despite large constants)?
•  » » » » » » 2 years ago, # ^ |   +1 It's , I believe. No idea how to make a good use of set in that case.
•  » » » » » » 2 years ago, # ^ |   +6 More precisely, In this task, using Mo's Algorithm, you will need to move left and right borders times, but asking for any element you will make no more than m times, so using sqrt-decomposition gives you slow asking operation (), but fast move operation (O(1)). In result you will get .On the other hand, using set will give you same complexity for asking and move operation, so result complexity will be .
•  » » » » » 2 years ago, # ^ | ← Rev. 3 →   +11 I tried to implement this idea but I got TLE, it seems that the comparator you used is the key to get Accepted, the solution passed in under 2 seconds after I tried it, can you explain how it works ?Update: I figured it out, this is a very clever trick :D The parity thing makes a block continue working from the index that the previous block finished working. This means that inside some block, the right index of mo's algorithm will keep increasing until it reaches the end, for the next block, it will keep decreasing while answering queries in the opposite direction instead of removing all the elements then increasing the right index from the beginning.
 » 2 years ago, # |   +5 in problem C it happened for the first time that PYPY gave TLE and python 2 passed in 2345ms. When I saw the accepted solutions in pypy, there were only three and their time was also quite borderline. How can pypy be slower than python 2
•  » » 2 years ago, # ^ |   0 I would like to know the same. My submission got TLE during contest: 39712202. Fearing that the time limit is too strict I switched to C++. And here's my practice submission with an AC: 39725290
•  » » » 2 years ago, # ^ |   0 cases are too harsh I guess. I guess during main test cases after the 12 hours hacking period python solutions might also fail
•  » » » » 2 years ago, # ^ |   0 Our python3 implementation of it works in 2137ms, we dicided that about 1 second off TL is fine for this.
•  » » » » » 2 years ago, # ^ |   0 yeah even python 2 solution worked well within TL. It's just that how come pypy gave a slower output than python. This rarely happens.
•  » » » » » » 2 years ago, # ^ |   0 Yeah, we didn't really expect that. Unfortunately, we had no way to test it as polygon doesn't support pypy.
 » 2 years ago, # |   +42 I thought implementation for A is too heavy (for usual A in educational) until I see this submission...
•  » » 2 years ago, # ^ |   0 This is better, http://codeforces.com/contest/1000/submission/39704314
 » 2 years ago, # |   +20 if only the round would be extended for 1 minute, I would solve Е :(
 » 2 years ago, # |   0 E is about finding the diameter of the tree of cycles, right?But how do you find and isolate each cycle? Tarjan's algorithm only works in directed graphs and I couldn't figure out how to apply it on undirected ones..
•  » » 2 years ago, # ^ |   0 You can find the bridges of a graph with Tarjan's like this. With them, you will then be able to combine all the nodes that share some cycle. And you will end up with a tree.
 » 2 years ago, # |   +1 maybe i should be saying sorry for this question , but can someone please explain to me A and why n — (all the sizes that are the same in old and new t-shirts sizes) is an logical answer ?
•  » » 2 years ago, # ^ |   +1 Because you need only 1 second to change one size to another if they have equal length. The answer can't be less because you need to change at least this number of strings.
•  » » » 2 years ago, # ^ |   0 and if there a test case where input is1XSXXXLhow can a code like the one i described be good ?((sorry if i just misread or didn't understand the problem))
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +1 this one is invalid test case .
•  » » » » 2 years ago, # ^ |   +1 1) You can only change letters, not add or remove2) It is guaranteed that you can get one list from another So this test is incorrect
•  » » » » » 2 years ago, # ^ |   0 Thanks Numb and annosorry if i wasted your time with my -3 IQ.
•  » » 2 years ago, # ^ |   0 lets take all the t-shirt name of lenght 3 that is xx_ so in old t-shirt either it will be present or absent so if it is absent so we only need to change the last character but if it is present we can use that and we cannot reduce or increase the length of the names so we will only consider length 3 similarly for all.
 » 2 years ago, # |   0 can anyone help me to understand the problem statement of E problem and the output of the given test cases?
•  » » 2 years ago, # ^ |   +12 You need to find two vertices s and t such that the number of bridges on the way from s to t is maximized.
•  » » » 2 years ago, # ^ |   0 how the answer of first test case is 2 ?
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +1 pick s = 4 and t = 5, then you have two bridges (4, 1) and (5, 2) on the way from s to t.
•  » » » » » 2 years ago, # ^ | ← Rev. 3 →   0 Thank You @numb , @jakube
 » 2 years ago, # |   0 May someone please tell me why my solution for A 39724005 is wrong?
•  » » 2 years ago, # ^ |   +3 Consider this test case:2 M S L MYour output = 2; Answer = 1;
•  » » 2 years ago, # ^ |   +3 your code is failing for this 6 L L L M M M L L M M M S output should be 1
•  » » » 2 years ago, # ^ |   0 Thanks! I was looking for cause of failure of my code.
•  » » 2 years ago, # ^ |   +3 try this testcase: 2 M L M S 
•  » » 2 years ago, # ^ |   +3 I have also done same mistake in my code Now understood flaw. Thanks for the test cases.
•  » » » 2 years ago, # ^ |   0 ٧_٧
•  » » 2 years ago, # ^ |   0 Thank you all IIIIIIIIIIIIIIIIIIIII, anno and lazyc97, now I get it.I worked during the contest on coming up with such tests, but failed with it :(.
 » 2 years ago, # |   0 Can anyone explain the approach to B? Thanks!
•  » » 2 years ago, # ^ |   +1 Basically you should notice that the best is to insert the new number just next to some a[i] or just before it.So you can try all possibilites. To do that, could be a good idea to have an accmuluate array that tells how many time is on from number i to the end. Then you can go from left to right and get the answer for every possible insertion and take maximun.
 » 2 years ago, # |   0 Can Anyone please explain D and E.
•  » » 2 years ago, # ^ | ← Rev. 5 →   +28 Let's denote with dp[i] the number of good subsequences of the array a[i...n-1], and define dp[n] = 0.The good subsequences of dp[i] either use the element a[i] or they don't. There are dp[i+1] good subsequences that don't contain a[i]. So we only need to count those that do.These subsequences might contain multiple good arrays. Let's focus on the first one. Its size is exactly a[i] + 1. If a[i] <= 0 then there are obviously no good array starting with a[i]. So assume that a[i] > 0 iterate over the last element in this good array. It can be any element a[j] with i + a[i] <= j <= n-1, and there are nCr(j - i - 1, a[i] - 1) possibilities to pick the middle elements of this good array. We count this sequence alone, and we can also combine it with each good subsequence in dp[j+1].Therefore we get the recursion: And the solution to the problem is dp[0].
•  » » » 2 years ago, # ^ |   0 Hi, I followed your solution, however the recurrence relation gave me 1 more than the answer and I don't quite understand why. Could you explain this?
•  » » » » 2 years ago, # ^ | ← Rev. 3 →   0 Do you mean my implementation? I used a slightly different definition. I defined the empty array as a good subsequence, so at the end I have to subtract this one.This is a submission that corresponds directly to the explanation: 39734194Btw, there was a little error my comment above. I forgot the  + 1. But now it is fixed.
•  » » » » » 2 years ago, # ^ |   0 Why you added +1 to dp[j+1] before multiplying to that nCr formulae. I didn't got that.
•  » » » » » » 2 years ago, # ^ |   0 Look 2/3 comments below.
•  » » » » » » » 2 years ago, # ^ |   0 Ohh got that thanks .
•  » » » 2 years ago, # ^ |   +1 That was a very pretty solution. Thanks a ton. I got that
•  » » » 2 years ago, # ^ |   0 Why have you added 1 in your formlula? I know that simply dp[j+1] won't give the right answer but (dp[j+1]+1) will give but I am not able to get the idea behind adding 1. Sorry for such a silly question
•  » » » » 2 years ago, # ^ |   +1 You can either combine the good array starting at i and ending at j with any of the good subsequences in a[j+1...n-1] => multiply by dp[j+1]Or you can only use the subsequence alone (without combining it with other subsequences) => + 1
•  » » » » » 2 years ago, # ^ |   0 Oh okay! Completely missed that! Btw thanks for providing such a nice explanation!
 » 2 years ago, # | ← Rev. 2 →   0 Any one solved F using MO's Algo within TL ? UPD: 39735901
•  » » 2 years ago, # ^ | ← Rev. 2 →   +8 After contest:39725241 Hacked :D
•  » » » 2 years ago, # ^ |   +8 Rofl Was unrolling these loops really necessary?
•  » » » » 2 years ago, # ^ |   0 One unrolling helped to pass the time limit.
•  » » » 2 years ago, # ^ |   0 Too close TL,resubmission may get TLE!!
•  » » 2 years ago, # ^ |   0 See this submission 39747523
 » 2 years ago, # |   0 Can someone please help out with Problem C?Thanks! I don't see a way to start. The tag said "SORTING," but I am not sure how to even apply it here.
•  » » 2 years ago, # ^ | ← Rev. 3 →   +4 The keyword is "Sweep line algorithm".Basically you convert each segment [l, r] into two events (l, begin), (r, end), sort all those events and compute the answer by iterating over the events. At each event point you can compute the answer for the last interval [last_event + 1, current_event - 1] in constant time, since the number of segments doesn't change in this interval.
•  » » 2 years ago, # ^ |   +12 This is actually a classic geometry concept, which is called "Line Sweep". It's called that because we can imagine a vertical line moving from left to right, covering all the points lying on the x-axis one-by-one. What we do is, store all the segments(x, y) separated in an array, with each element being (val, isStart), where val is either x or y, and isStart is 1 if it's an x value, and 0 if it's a y value.After storing all the segments this way in an array, we sort them according to their value. Then, we perform the sweep while keeping a counter open for the number of segments that are currently open. When we come across a value where isStart is true, that means that a segment is starting at this point, so we increase our counter open. And when we come across a value whose isStart is false, we decrease the counter open.This way at any point we know exactly how many segments are covering it, and using this we can find how many points have open number of segments covering them.Here is a tutorial blog about the line sweep technique: linkAnd, here is my code for this question: linkIf you need any more explanation, do let me know!
•  » » » 2 years ago, # ^ |   0 Damn towards the end of the contest I had this idea but it was too late. Thanks for the explanation :)
 » 2 years ago, # | ← Rev. 2 →   +154 That moment when your script hacks your own solution
•  » » 2 years ago, # ^ |   0 Can I get the code for the script? Is it open source?
•  » » 2 years ago, # ^ |   0 Could he use it in an non-educational round?
•  » » » 2 years ago, # ^ |   0 No, you cant copy solutions, and it is forbidden by rules.
•  » » 2 years ago, # ^ |   +68 And it is the first test I tried to use for hacking. If only I checked this corner case during the contest...
•  » » 2 years ago, # ^ |   +15 Ironic. He could save others from hacks, but not himself.
 » 2 years ago, # |   +4 Do all hacks run against all submissions at the end of hacking phase?
•  » » 2 years ago, # ^ |   +3 of course
•  » » » 2 years ago, # ^ |   0 I was doubtful because I checked the contest page after 5 minutes of end of hacking phase and it said 'Final standings'. I wonder how they managed to run all the codes on all the hacks so quickly!
•  » » » » 2 years ago, # ^ |   +4 We need to wait for final testing. 'Final standing' is not final standing yet.
•  » » » » 2 years ago, # ^ |   +3 Yeah it is not the true 'Final Standing'。Maybe System will rejudge soon
 » 2 years ago, # |   +3 Come on ! Rating changes ?
•  » » 2 years ago, # ^ |   +5 Time taken to update rating is directly proportional to the amount of rating you are going to gain xD
 » 2 years ago, # |   +10 truly a hacker...
•  » » 2 years ago, # ^ |   0 I'm scared about systests now :(
•  » » » 2 years ago, # ^ |   0 Yes, by this time I think they should've been updated the ratings no? Or educational rounds take this much time usually?
 » 2 years ago, # |   0 when can I get the solution and the rating changes?
•  » » 2 years ago, # ^ |   +1 urge..
 » 2 years ago, # |   +6 I found two pairs of people, which have one solution — 39722722 and 39716743; 39723479 and 39714675.
•  » » 2 years ago, # ^ |   +3 i think first one from practice another from official contest
 » 2 years ago, # |   +2 One of the best educational round I could see on codeforces, in terms of quality problems. Though I couldn't participate in the round.
 » 2 years ago, # |   0 The systest is really fast, but the rating changing is too slow... Maybe make it faster?
•  » » 2 years ago, # ^ |   -8 Systests were faster because they only need to check for the hack tests.
 » 2 years ago, # |   +4 When will you publish the Editorial ?
 » 2 years ago, # |   0 Eagerly waiting for the editorials..when will they come?
 » 2 years ago, # |   0 Can F be solved with a mergesort tree? ( By keeping all the elements which occur once in the nodes. Also, merging is easy. )
 » 2 years ago, # |   0 Why is this code for problem C giving run time error on testcase 4?
•  » » 2 years ago, # ^ |   0 You compare operator doesn't make any sense. sort expects that the compare operator cmp(p, q) returns true, if p should appear before q in the sorted order.But with you implementation, and using two element p = {1, 'l'} and q = {1, 'l'}, both cmp(p, q) == true and cmp(q, p) == true. So of course C++ is confused. How can an element p appear before q and behind q at the same time?
•  » » » 2 years ago, # ^ |   0 Thanks, finally got it accepted :)
•  » » » 2 years ago, # ^ |   0 But why did it work for testcase 1, 2, 3?
•  » » » » 2 years ago, # ^ |   +1 Probably because there are not identical elements in those cases.
 » 2 years ago, # |   0 Your crafting.oj.uz ratings are updated!
 » 2 years ago, # |   0 When will you publish the editorial? I'm eager to read it :-)
 » 2 years ago, # |   0 Editorial?
 » 2 years ago, # |   0 I am new to codeforces. Can someone tell when we can expect editorial for this round?
 » 2 years ago, # |   +9
 » 2 years ago, # |   -17 It's expected a tutorial about how to solve the problems?
 » 2 years ago, # |   0 I tried to do problem E by compressing the cycles to a single node.My solution is running on my computer compiled with command g++ -std=c++14 but on submitting it is giving an error. Diagnostics detected issues [cpp.clang++-diagnose]: ================================================================= ==3384==ERROR: AddressSanitizer: heap-use-after-free on address 0x00f015dd at pc 0x010bb4ad bp 0x1179f0d4 sp 0x1179f0d0 READ of size 1 at 0x00f015dd thread T0 ==3384==AddressSanitizer CHECK failed: C:\src\llvm_package_600-final\llvm\projects\compiler-rt\lib\sanitizer_common\sanitizer_symbolizer_win.cc:64 "((dbghelp && "failed to load dbghelp.dll")) != (0)" (0x0, 0x0) ==3384==AddressSanitizer CHECK failed: C:\src\llvm_package_600-final\llvm\projects\compiler-rt\lib\sanitizer_common\sanitizer_win.cc:795 "((owner_)) == ((LOCK_READY))" (0x4ac, 0xffffffff) ==3384==AddressSanitizer CHECK failed: C:\src\llvm_package_600-final\llvm\projects\compiler-rt\lib\sanitizer_common\sanitizer_win.cc:795 "((owner_)) == ((LOCK_READY))" (0x4ac, 0xffffffff) ==3384==AddressSanitizer CHECK failed: C:\src\llvm_package_600-final\llvm\projects\compiler-rt\lib\sanitizer_common\sanitizer_win.cc:795 "((owner_)) == ((LOCK_READY))" (0x4ac, 0xffffffff) ==3384==AddressSanitizer CHECK failed: C:\src\llvm_package_600-final\llvm\projects\compiler-rt\lib\sanitizer_common\sanitizer_win.cc:795 "((owner_)) == ((LOCK_READY))" (0x4ac, 0xffffffff) ==3384==AddressSanitizer CHECK failed: C:\src\llvm_package_600-final\llvm\projects\compiler-rt\lib\sanitizer_common\sanitizer_win.cc:795 "((owner_)) == ((LOCK_READY))" (0x4ac, 0xffffffff) ==3384==AddressSanitizer CHECK failed: C:\src\llvm_package_600-final\llvm\projects\compiler-rt\lib\sanitizer_common\sanitizer_win.cc:795 "((owner_)) == ((LOCK_READY))" (0x4ac, 0xffffffff) ==3384==AddressSanitizer CHECK failed: C:\src\llvm_package_600-final\llvm\projects\compiler-rt\lib\sanitizer_common\sanitizer_win.cc:795 "((owner_)) == ((LOCK_READY))" (0x4ac, 0xffffffff) ==3384==AddressSanitizer CHECK failed: C:\src\llvm_package_600-final\llvm\projects\compiler-rt\lib\sanitizer_common\sanitizer_win.cc:795 "((owner_)) == ((LOCK_READY))" (0x4ac, 0xffffffff) ==3384==AddressSanitizer CHECK failed: C:\src\llvm_package_600-final\llvm\projects\compiler-rt\lib\sanitizer_common\sanitizer_win.cc:795 "((owner_)) == ((LOCK_READY))" (0x4ac, 0xffffffff) ==3384==AddressSanitizer CHECK failed: C:\src\llvm_package_600-final\llvm\projects\compiler-rt\lib\sanitizer_common\sanitizer_win.cc:795 "((owner_)) == ((LOCK_READY))" (0x4ac, 0xffffffff) Here is my solution. Any help ?
 » 2 years ago, # | ← Rev. 2 →   0 I have a strange behavior for my solution for Problem 1000G - Two-Paths. If I read integers with cin my solution (39859090) is Accepted. If I use scanf (39859098) or getchar (39859106) I receive "Wrong answer on test 9". How is that possible? In getchar-version I even checked whether input is fine, which seems to be the case (otherwise I would have received a Runtime Error). Can somebody figure out the reason?Update: Found a small bug (using index outside of range of vector) and now it works (39861715). But the question remains: How can it make a difference whether I read with cin or scanf??