By RDDCCD, 17 months ago,

This weekend, on Nov/24/2019 11:05 (Moscow time) we will hold Codeforces Round 602. It is based on problems of Technocup 2020 Elimination Round 3 that will be held at the same time.

Technocup is a major olympiad for Russian-speaking high-school students, so if you fit into this category, please register at Technocup 2020 website and take part in Technocup 2020 - Elimination Round 3.

Problem authors are me, nocriz, BledDest, adedalic and MikeMirzayanov. Many thanks to the testers: KAN, Supermagzzz, Stepavly, AdvancerMan and unreal.eugene!

Div. 1 and Div.2 editions are open and rated for everyone. As usual, the statements will be provided in English and in Russian. Register and enjoy the contests!

Have fun!

Scoring distribution:

Technocup: 500 1000 1250 (500+1500) 2500 (1000+2000) 3250

D1: 500 (500+750) 1500 (1000+1000) 2250 2500

D2: 500 1000 1250 (500+1500) 2500 (1000+2000)

UPD: Div1 Top5

1.sunset

2.tourist

3.WZYYN

5.djq_cpp

And congratulations for djq_cpp to be the youngest Legendary GrandMaster in the age of 14!

Div2 Top5

3.nehnait

4.Fuyuki

And also the Editorial is out.

• +202

 » 17 months ago, # |   -49 Is it rated?!?!?1
•  » » 17 months ago, # ^ |   0 Quoting from the post : "Div. 1 and Div.2 editions are open and rated for everyone."
 » 17 months ago, # |   +13 Please fix the Codeforces Round #number in the title! Looks like a by-product of Technocup Elimination Round 2 and 3 :p
•  » » 17 months ago, # ^ |   -23 No its not wrong its technocup for both divisiors
•  » » » 17 months ago, # ^ |   +1 I meant it should be #602 instead of #596. #596 was for Technocup Elimination Round 2.
•  » » » » 17 months ago, # ^ |   0 Understood
•  » » 17 months ago, # ^ |   +20 Fixed. Sorry for the stupid mistake while copying.
•  » » » 17 months ago, # ^ |   +3 How many problems will be?
•  » » » » 17 months ago, # ^ |   +5 Eight in total.
•  » » » » » 17 months ago, # ^ |   0 Perfect!!! Thanks a lot!
•  » » » » » 17 months ago, # ^ |   -25 But with 2 problems split into subtasks, so 6 in total.
•  » » » » » » 17 months ago, # ^ |   +13 for both divisions we have 8 in total :)
•  » » » » » » » 17 months ago, # ^ |   -48 Hmm, so the question and answer is more undefined than it seems. A div2 user is asking, so it could mean "just in div2", or it could mean in total. It could also mean "just in div1", with/without subtasks, or "just in the official contest".
 » 17 months ago, # |   0 Great!!!!.
 » 17 months ago, # |   0 Hope the Chinese problems are not in div2 ABC, math boys will downvote :P
 » 17 months ago, # |   0 It's time to participate in the great contest.
 » 17 months ago, # |   +51 When I saw 2020 I thought my time machine leaped to the wrong date
•  » » 17 months ago, # ^ |   +21 Can I borrow your time machine. I would like to retake my math (yes MATH) test from last week. Thank you!
•  » » » 17 months ago, # ^ |   +97 Nope, time travel is not for trivial tasks. Plutonium is very precious, I use it only to fight the organization.
 » 17 months ago, # |   -25 Hopping to get some great problems more focused on logic and Algorithms rather than language of problem statements.
•  » » 17 months ago, # ^ |   +29 Why do you write this? Just curious
•  » » » 17 months ago, # ^ |   0 Sometimes problem statements were too long and takes lots of time to understand the problem, So this is the reason. Sorry if anyone has offended :(
 » 17 months ago, # |   -6 Ehhh... It's the middle of the night in Poland. Hope it'll be ok :/
•  » » 17 months ago, # ^ |   +8 9 am to be precise... you guys have no mercy :/ Can you al least tell us the number of problems and scoring?
•  » » » 17 months ago, # ^ |   +12 We have eight problems in total. Scoring will be announced before the contest.
•  » » » » 17 months ago, # ^ |   -10 "in total", so some of them for div2 and some of them for div1?
•  » » » » » 17 months ago, # ^ |   +3 Yes.
•  » » » 17 months ago, # ^ |   +15 Every time is going to be in the middle of the night somewhere...
•  » » » » 17 months ago, # ^ |   +147 I know, I just wanted to joke about 9 am being the middle of the night...
•  » » » » » 17 months ago, # ^ |   +219 I didn't get the joke because 9am is obviously the middle of the night, right? :P
•  » » 17 months ago, # ^ |   +95 It's OK! You will win!
•  » » » 17 months ago, # ^ |   +161 :P Sometimes I think that it'd be much easier for some people to overtake Gennady while he's not competing so often. It's much harder as we are behaving like zombies in "World War Z". Whenever somebody is close, the rest grab his legs and pull him backward xd So he just stays at the top and laughs.
•  » » » » 17 months ago, # ^ |   -48 You should put that picture in spoiler, it's not a good thing for me to see that thing right before a contest, it makes me vomit.And another thing... What's exactly funny about 9am being the middle of the night?
•  » » » » » 17 months ago, # ^ |   +32 Go have some sleep buddy
•  » » » » » » 17 months ago, # ^ | ← Rev. 2 →   +184 History won't remember the ones who went to sleep.
•  » » » » 17 months ago, # ^ |   +58 But in the film zombies got in...
•  » » 17 months ago, # ^ |   +17 Where I live, the contest runs from 12:05am to 2:05 am! And I still will be writing the contest :DCompetitive Programming >>>> Sleep >>>> School
 » 17 months ago, # |   0 Scoring Distribution?
•  » » 17 months ago, # ^ |   0 the same question
 » 17 months ago, # |   0 Cannot expect the contest to have any lesser implementation, with so many authors. :(
 » 17 months ago, # | ← Rev. 2 →   +1 Great Problems and especially Div.2 D2(Div.1 B2) is interesting.
 » 17 months ago, # |   +8 How to solve Div 1 D2?
•  » » 17 months ago, # ^ | ← Rev. 2 →   +21 you can calculate the suits that points change is zero, and substract it,than it's double the answer
 » 17 months ago, # |   0 Is there any data structure in java which can give the nth element in a sortedList? For problem D2, I was stuck in thinking of something which can be maintained sorted and also give me the nth element.
•  » » 17 months ago, # ^ |   0 Do not know about java, but in c++ I have heard there is PBDS for this purpose.
•  » » 17 months ago, # ^ |   0 This task can be done using Binary Lifting
•  » » 17 months ago, # ^ |   +1 I used one segment tree, with finding the kth in the query, but it is not implemented in java :/
•  » » 17 months ago, # ^ |   0 I think there is no such thing in Java. You need to do Binary Search and Segment Tree query to get the nth element.
•  » » » 17 months ago, # ^ |   +6 Simply segment tree will suffice, It involves binary search itself.
•  » » 17 months ago, # ^ |   +6 You can use segment tree with operations: add 1 in point, find nth element. It's quite simple to find nth element. You just run from node v = 1 in tree and check whether the sum of subtree of left son is bigger than n. If it is then you look for (n-sum[left_son])th element in subtree of rightson. Otherwise you look for nth element in subtree of leftson.
•  » » 17 months ago, # ^ |   0 i solved it using ordered_set in pbds in c++,but in java you can use binary lifting technique,follow this, you can use this type of method
•  » » » 17 months ago, # ^ |   0 how to use it with pair . I am getting some compilation error, don't know how to fix, if you have done this before could you give me the link to your implementation.
•  » » » » 17 months ago, # ^ |   +1 In the Template of ordered_set write pair instead of int. For ref.65652180
•  » » » » » 17 months ago, # ^ |   0 I was doing that forgot to write for less function.
 » 17 months ago, # | ← Rev. 2 →   +47 >tfw I'm not fast enough for speedforces
•  » » 17 months ago, # ^ |   +16 I think that it was also a lot of "implementation-forces" too?
•  » » » 17 months ago, # ^ |   -7 Yeah, but mostly about fast implementation, not about ideas that simplify implementation.
•  » » » » 17 months ago, # ^ |   +5 Right!
 » 17 months ago, # |   0 How to access an element in c++ set with it's position?
•  » » 17 months ago, # ^ |   0 It is not possible to access the set elements by index, although you can iterate through all set elements using a loop.
•  » » 17 months ago, # ^ |   +22 You can't. C++ set is not addressable.
•  » » 17 months ago, # ^ | ← Rev. 4 →   -26 you can have an iterator and then use advance(). set st; int position = 4; // fill up the set auto iter = st.begin(); advance(iter, position); // iter is now on 5th position. 
•  » » » 17 months ago, # ^ |   0 If iter is not a random-access iterator (as the case with C++ set), this has linear complexity. It's not better than just iterating (which is what it does behind the curtain anyway)
•  » » » » 17 months ago, # ^ |   0 Thanks, I was not aware of the complexity.
•  » » 17 months ago, # ^ |   +2 Can't do that in set since it's complexity will be O(n) which is not optimal in most of the required cases.Use find_by_order from the Policy based data structure.link
•  » » » 17 months ago, # ^ |   0 Thanks!
•  » » 17 months ago, # ^ |   0 I do not think you can. Try to use __pbds or write a segment-tree/BST instead.
•  » » » 17 months ago, # ^ |   0 Can you explain what exactly pbds is and how can we use it? I couldn't find a relative article on pbds. Also, is it possible to use pdbs everywhere without getting compilation error?
•  » » » » 17 months ago, # ^ | ← Rev. 2 →   +3 HereAnd if you can understand Chinese, This is also a great article.You can use 'custom test' to test if it results compilation error.
•  » » » » » 17 months ago, # ^ |   0 Thank you very much. But from compilation I mean, there are some function that run in my pc but give compilation error in codeforces, like pow64. How to tackle this type of error?
•  » » » » » » 17 months ago, # ^ |   +3 Maybe it differs from compiler to compiler. I'm using g++ 8.3.0 on Ubuntu x64, without any problems when using __pbds.
 » 17 months ago, # |   0 I keep failing pretest 2 in problem AAny ideas?
•  » » 17 months ago, # ^ |   0 1 3 1 3 2 2 6 7 answer 4
•  » » » 17 months ago, # ^ |   0 My output is 4 too I can't figure out where my solution fails
•  » » » » 17 months ago, # ^ |   0 I think mine failed on pretest 2 when I first submitted because of something like: 1 2 1 10 2 9
•  » » » » » 17 months ago, # ^ |   0 Isn't the result 0?
•  » » » » » » 17 months ago, # ^ |   0 Yes.In short, Div.2 A can be solved by this:In each Testcase, we can find the maximum of li(I'll call this a) and the minimum of ri(I'll call this b). If n==1||a<=b the answer is 0, and if n>2&&a>b the answer is a-b. Can you find what's wrong with your algorithm?
•  » » » » » » » 17 months ago, # ^ |   +8 You're son of a math teacher, aren't you?
•  » » » » » » » » 17 months ago, # ^ |   0 :) You are witty.
•  » » » » » » » 17 months ago, # ^ |   0 Thanks, bro I've fixed my error
•  » » 17 months ago, # ^ | ← Rev. 4 →   0 1 3 1 5 1 4 7 9 answer is 7-4=3 and this 1 3 1 5 2 3 7 9 answer is 7-3=4 
•  » » 17 months ago, # ^ | ← Rev. 2 →   0 try this : 1 3 1 5 2 3 4 7 answer >>> 1
•  » » » 17 months ago, # ^ |   0 Thanks!
•  » » » 17 months ago, # ^ |   0 my idea is that after sorting segments if the second segment is in the first segment you should choose the max first point, res = max((segments[n-1].first — first_point),0);
 » 17 months ago, # |   +32 Did you guys happen to find the 2 seconds TL on Div1C a bit tight? I couldn't manage to get a solution accepted that simulated with bfs, and ended up replacing the simulation with partial sums, even though it should still be $O(n * m * log(min(n, m)))$. Is there a quadratic solution that should have passed here, or what is the reason of such tight TL? (reading $10^6$ strings in itself takes quite some time itself)
•  » » 17 months ago, # ^ |   +10 It is. With super cache-efficient binsearch, it wouldn't be a problem, but both BFS and partial sums on such huge arrays are costly simply because we need to jump between rows.Did you try BFS with a custom queue (static buffer + pointer to front)? In my experience, it can be really damn faster than std::queue.
•  » » » 17 months ago, # ^ | ← Rev. 2 →   +10 I usually use std::vector for my queues, mostly because I find it convenient most of the times to keep the topological sort with no extra hassle. This should be cache friendly. However, one possibly bad thing that I did is I allocated the matrices inside the check function, so I allocate more than necessary. I usually do this for the sake of clean code, and I never know when/whether this makes a difference, but I’m always a bit more anxious when I have to preallocate (and I usually don’t think I have to). code
•  » » » » 17 months ago, # ^ |   0 Generally, it's not the allocation size that matters (unless you're asking for too much and torturing the heap allocator), but the number of allocations, so that shouldn't be a problem.Regular queue is probably slower because it does extra checks, not because of cache inefficiency. On the other hand, a lot of pushing = a lot of moving data in reallocations = worse constant also due to updating cache. Back in IOI 2012, I got 20 points instead of maybe 60+ with inexplicable BFS TLE on one problem — in the end, turns out I was creating and destroying a queue N times instead of working with one instance. It probably isn't that extreme here, but there's a lot of factors that matter with such large inputs.
•  » » 17 months ago, # ^ | ← Rev. 2 →   +2 I got AC (~500ms) 65655948 using prefix sums, without any optimization.
•  » » » 17 months ago, # ^ |   0 Me too, but I had to change the code from BFS to prefix sums, which was a bit annoying for a fast-paced contest.
•  » » » » 17 months ago, # ^ | ← Rev. 2 →   +10 65657404 your code runs on ~600 ms, if you call check $~log2(min(n, m))$ times. Look at the two lines before for (int step...
•  » » » » » 17 months ago, # ^ | ← Rev. 3 →   0 Alright, the condition inside the for loop should have been || instead of &&. This got me really confused for a bit there, as I was almost sure your modification should be a no-op. In this case, it was not the BFS that was the issue, it was the memory allocations. Mystery solved.
•  » » 17 months ago, # ^ |   0 Weird... I just did binary search + bfs with the same complexity without consciously optimizing anything and it passed in 343ms.
•  » » » 17 months ago, # ^ |   +10 Nothing weird about that, there's a lot of hidden factors in implementation that are abstracted away in algorithmic thinking. You can speed up a solution 2x by replacing "if (x & 1) then sum += y" by "sum += y * (x & 1)" sometimes, branch delay and speculative execution is a bitch.
•  » » 17 months ago, # ^ | ← Rev. 2 →   +3 Let's put aside the question about tight limits for now. The problem in your solution is next: Instead of $O(n \cdot m \cdot \log(\min(n, m)))$, your solution is actually $O(n \cdot m \cdot \log(\max(n, m)))$, because checking if (ans + step > n && ans + step > m) continue; is wrong.P.S.: Sorry for being a slowpoke.
 » 17 months ago, # |   0 Could anyone figure out test 2 of Div2 C?
 » 17 months ago, # |   0 oh my room is very strange :)
 » 17 months ago, # |   0 How to solve Div.2 F1(Div.1 D1)?
•  » » 17 months ago, # ^ |   +3 It can be solved using dp with n^2 states. If the adjacent two values are equal then whatever value you give to the current index it won't affect your answer. If they are not equal then we have 3 cases 1. Difference between next suite and current suite added by 1 2. Subtracted by 1 3. Remains same.
 » 17 months ago, # |   +23 My solution to F ended up with MLE because of O((100*log(10^18))^2) memory. Is this intended? Or didn't you noticed solutions like this?
•  » » 17 months ago, # ^ | ← Rev. 3 →   +14 Such solution is quite obvious, so I guess it was intended to get MLE.It seems we can optimize one of logs by processing bits one by one, so instead of storing all result ranges in form $[X, X+2^K)$, we should generate and process them iterating over K.
•  » » » 17 months ago, # ^ |   0 I see.By the way, this quite obvious solution passed if I maintain the set of ranges dynamically. (my submission)
•  » » 17 months ago, # ^ | ← Rev. 3 →   0 The memory limit indeed seems too tight. Naively writing the obvious solution uses around $(100 \cdot 2 \cdot \log(10^{18}))^{2} \approx 1.4 \cdot 10^{8}$ memory so the limits could be much higher. I had to do memory optimization on my correct solution (65667891) with memory usage around $4 \cdot 100^{2} \log(10^{18})$ to get it to pass (65668033)The trick to optimise from $100^{2} \log(10^{18})^{2}$ to $100^{2} \log(10^{18})$ is just to notice that you don't have to check all pairs of dyadic intervals, you can just loop dyadic intervals formed from the first list and regular intervals from the second list, then do the same the other way around. For every pair you have to add at most 4 intervals.This also shows that maintaining the intervals dynamically doesn't use too much memory.
 » 17 months ago, # |   0  int n; cin >> n; int left = -mod; int right = mod; for(int i = 0; i < n; i++) { int l, r; cin >> l >> r; left = max(left, l); right = min(right, r); } if(n == 1) { cout << 0 << endl; } else { cout << abs(left - right) << endl; } what is wrong in this code for DIV 2 A
•  » » 17 months ago, # ^ | ← Rev. 2 →   0 3 1 3 1 3 1 3 ans = 0 
•  » » » 17 months ago, # ^ |   +5 i solved D1 and D2 in around 30 minutes A took my 40 minutes(still unsolved) which spoils my whole contest.... R.I.P
•  » » » » 17 months ago, # ^ |   0 When "minr >= maxl" you can find a common segment shared by all, so only need one point (length 0) to cover all segments. conclusion if (minr >= maxl) { cout << 0 << endl; } else { cout << maxl - minr << endl; } 
•  » » 17 months ago, # ^ |   0 If left
• »
»
17 months ago, # ^ |
-30

# include<bits/stdc++.h>

using namespace std;

int main() { int i,n,j,ara[100000],ara2[100000]; int T;

cin>>T;
while(T--)
{

int p,k;
cin>>n;

for(i=0; i<n; i++)
{

cin>>p>>k;
ara[i]=p;
ara2[i]=k;

}

sort(ara,ara+n);
sort(ara2,ara2+n);

cout<<max(ara[n-1]-ara2[0],0)<<endl;

}

return 0;

}

•  » » 17 months ago, # ^ |   -14 TRY MY CODE!!
 » 17 months ago, # |   0 How to solve Div2 D2 ?
•  » » 17 months ago, # ^ |   0 Answer the queries offline. Sort all the queries on the basis of k first. Then use PBDS or BIT to find the value at index j in sorted array for prefix.
•  » » 17 months ago, # ^ |   +9 For D1, sort the array in increasing order values and decreasing order of indexes so that we can get the lexicographically smallest subsequence from the end of array for each query.For D2, I solved it offline Sort queries by their increasing length Since length of queries is sorted, we can keep inserting elements into a treap/policy based data structure(pbds) such that it has number of elements equal to the length of given query. Give kth smallest element from the treap. Solution
•  » » » 17 months ago, # ^ |   0 Is there any alternative for policy based data structure in Java? If not then do you know anyone has implemented PBDS or similar in Java?
•  » » » » 17 months ago, # ^ |   +3 I am not sure what PBDS is, but you can write a generic treap which you can modify immediately according to your needs during contest. You can check my solution of D2 for it.
•  » » » » 17 months ago, # ^ |   0 You can use Segment tree to do order statistics in some cases.
•  » » » » 17 months ago, # ^ |   +3 I solved it by creating a custom ordered set like Data Structure in Java using Segment tree for kth order statistics. You can check my solution 65750497
•  » » » » » 17 months ago, # ^ |   0 Thanks a lot!! But I have found an implementation for order statistics. You can see my submissions.
•  » » » » » » 17 months ago, # ^ |   0 Nice one. RB trees are actually better for kth order statistics as they consume less space than Segment/Fenwick tree, and I think PBDS in C++ is also implemented using RB tree.
•  » » 17 months ago, # ^ |   0 Even though I failed to submit, but this will work.First we store the index of all input of array in map Create another vector> and insert the value from input array. Sort the above vector using stable_sort. Store the last k values in the resultant array in the order of there pos.(Use map for it)
 » 17 months ago, # |   +27 Lacked 1 minute to submit D T_TE is really nice though...
 » 17 months ago, # |   +9 hope that I can get +1 rating :P
 » 17 months ago, # |   +6 How to solve Div2 C?
•  » » 17 months ago, # ^ | ← Rev. 2 →   +4 I'm not sure this is best way but...You shouldn't minimize number of operations so as first step you can just sort your array: ()()(()) -> (((()))) Second step is to change array to satisfy number of k: one of easy ways is to swap second element with first opposite: first swap: (((()))) -> () ((())) k=2, second swap: () ((())) -> ()() (()) k=3, etc...
•  » » » 17 months ago, # ^ |   +11 You can construct a string like ()()...()((((...()...)))) to achieve the requirement:You can decide this string a bit by a bit.Like: After locating the before character, you want a proper character str[l]. (like you want a ')' to make pair with the previous '(' ) You can search the rest of the string to find it (marked as str[r]). Then reverse the whole substring str[l,...,r].Like this->(you are focusing on position 2 pairing with position 1)(((()()())))You can work out that l=2, r=5.Reverse(2,5). Then it becomes...()(((()())))And you succeeded in making the first two brackets into a pair.It can be proved that you need at most n executions. (Each time after you decide a position (execute once) it will never change again, while you only have n positions. )(sorry for my bad English.)
•  » » 17 months ago, # ^ |   +1 I solved the question the following way. 12 1 ))())()()(((  First convert the string into a string with maximum possible prefixes. ()()()()()() The above conversion can be performed with n / 2 operations ( Not sure how to prove this yet. But I basically brute forced to match every element) Then depending on the value of k, one can start decreasing the prefixes one by one. The prefixes can be decreased by 1 in each step by swapping adjacent elements starting from 2nd index. Swapping 2, 3 gives (())()()()(). The number of prefixes decreases by 1. Then swapping 4, 5 gives (()())()()(). The number of prefixes decreases by 1. Similar operations can be continued until the number of prefixes becomes 1. The above operations are also n / 2. So we'll never exceed total operations n. Link to solution
•  » » » 17 months ago, # ^ |   0 I did — first create a sample final string. This will have k-1 strings of "()" and one string of "(((...)))" of whatever is left over. For example, for k = 3, n = 8 this is "()()(())" Now iterate through the given string. If our current character is equal to the final string's current character, then we have nothing to do, otherwise find the next final string character that is equal to this character, and bring it here (by reversing the string up to that character). Since for each element you do at most 1 reverse operation, you will at most do n operations.
 » 17 months ago, # |   0 Please someone explain me the solution of A . I was thinking to do a line sweep
•  » » 17 months ago, # ^ | ← Rev. 2 →   0 Take the interval between leftmost of endpoints and rightmost of start-points of intervals.
•  » » 17 months ago, # ^ |   0 main idea if (minr >= maxl) { cout << 0 << endl; } else { cout << maxl - minr << endl; } 
 » 17 months ago, # |   +101 Why do obviously wrong solutions like https://codeforces.com/contest/1261/submission/65640232 pass for D1C? Counterexample7 5 ..XXX ..XXX ..XXX .XXX. XXX.. XXX.. XXX.. 
 » 17 months ago, # |   +160 How many of you feel subtasks like in recent contests is shit. I know that adds more tactics to contest but still I feel old codeforces was great.
•  » » 17 months ago, # ^ |   +18 Same :(
•  » » 17 months ago, # ^ |   +31 I prefer it, what is your issue with them exactly? Seems like a nice way to give you some partial credit for working on a problem but failing to fully solve it. A trade-off between IOI and ACM style.
•  » » » 17 months ago, # ^ |   +38 Because it demotivates you from solving complete question ( As I said now it's more tactics than problem solving).Also point distribution is crazy. I feel everyone agree A > B1. And B overall having more than double of A is a joke.
•  » » » » 17 months ago, # ^ |   -23 True. I felt that too. I solved B in less than 10 mins after reading it while I was stuck at A for so long.
•  » » » » » 17 months ago, # ^ |   +5 He is talking about div1 not div2. Div1A = Div2C, Div1B1 = Div2D1
•  » » » » » » 17 months ago, # ^ |   +1 Ok
•  » » » » » 17 months ago, # ^ |   0 teja349 was talking about Div1A and Div1B1
•  » » » » 17 months ago, # ^ |   +23 I agree about point distribution, but not about subtasks overall. With better thought-out point distributions I think it can work just fine.
•  » » » » » 17 months ago, # ^ |   +10 Can you suggest a good point distribution for today's contest?
•  » » » » » » 17 months ago, # ^ |   0 I'm not really familiar with the CF decaying points formulas, so I wouldn't give any exact numbers.As you said B1 should be less than A, while B1+B2 > A. Also perhaps D doesn't need the subtask since I'm not sure if D1 has a significantly different solution from D2.I'm just saying the overall idea of subtasks shouldn't be bashed because it's not perfect in a given competition.
•  » » » » » » » 17 months ago, # ^ |   +8 I only said subtasks is crazy in current point distributions in codeforces contests. I think IOI format is no where close to codeforces format. So you should not argue subtasks make sense in codeforces because they make sense in IOI.Maybe I think people who support subtasks in cf need to say that "currently it is shit we agree, we are working on getting it better and hoping it will be better in near future and starts making sense. Since we need to start somewhere, we started it now."
•  » » » » » » » » 17 months ago, # ^ |   +16 Thing is, I wouldn't call it shit. Imo if you took B and squashed it into a 1250 problem and D into a 2000 problem, it would've been roughly the same competition for most. I don't think it ruins anything. I agree with feedback like "B1 shouldn't have been more than A1", but I disagree with feedback like "These subtasks are shit, go back to full ACM style".Also Codeforces format is ACM-style while subtasks are generally given in IOI-style contests, so my argument was that this is a trade-off between the two formats.
•  » » » » » » » » » 17 months ago, # ^ |   0 ACM and different points for questions are not close enough, I feel if all had same points then point distribution can be adjusted so that they are not crazy.
•  » » » 17 months ago, # ^ | ← Rev. 3 →   +24 I think that D1(considering Div_2 as standard) was so meaningless and F1 was helpful for me to think a solution for F2. But I think that for div_1 people, the subtasks are meaningless. In IOI, 5 hours is sufficient to try various solutions and penalty doesn't exist. So subtasks in IOI are ok. But in codeforces, 2 hours is too short to try various solutions. And because of penalty, order of solving problems is very important. So in cf, sometimes subtasks are obstacles to make an adequate contest tatics.
•  » » » » 17 months ago, # ^ |   +9 It’s interesting to learn that F1 helped you come up with solution for F2. In my case, it was the opposite because I did a completely different approach for F1 (using DP) and got stuck into optimizing that one for F2, which obviously didn’t work. Got the correct one 5 mins after the contest ended and I only had myself to blame for following a wrong strategy. Still, the subtask was nothing but counterproductive.
•  » » » » » 17 months ago, # ^ |   0 I found a solution on paper using sums of combinations. After D1, I found how to calculate these sums faster. You can compare my submissions 65652834 65650523I think this is first time the first subtask really helps me with second.
•  » » » » » » 17 months ago, # ^ |   +11 I just figured out right away that we have 3 options for each pair of consecutive different $H_i$: either +1 point for the non-shifted answer or +1 point for the shifted answer or +0 points for each.Then, it's clear that for each answer set that gives strictly more points when shifted, there's a reverse answer set that gives strictly less points when shifted — flip all answers of the first type to answers of the second type and vice versa. This is 1:1, so we just want the number of all answer sets that don't give the same number of points when shifted, divided by 2. Fairly straightforward reasoning.The number of these answer sets is then just the number of ways to choose exactly $k$ answers of the first type and $k$ of the second type — a sum with multinomial coefficients.
•  » » » 17 months ago, # ^ |   +11 The problem is that you can know how to solve the problem, but lose time when it's better to solve the easier subtask separately first. I don't mind subtask problems, but more than 1 per contest is too much.
•  » » 17 months ago, # ^ |   +37 The same here. Vote you up! Subtasks are also boring for me and make me upset.
•  » » 17 months ago, # ^ |   +23 I don't know if I agree with you or not because more often than not I just end up ignoring the smaller subtask, but it's weird for sure. I've seen 2 interesting subtasks in cf the rest feels like filler problems.
•  » » 17 months ago, # ^ |   -16 I think we should take a vote
•  » » 17 months ago, # ^ |   0 I think it makes more sense to add easier versions of tasks in Div 2 contest and harder version in Div 1 contest, or maybe something in between. Subtasks are necessary for Div 2 to make the difficulty gap smooth, especially when problems are shared between divisions.
 » 17 months ago, # |   0 Why this solution gets TL instead of RE? codeforces.com/contest/1261/submission/65650035The problem with line ~115. I wrote "j<=n" instead of "j<=m". Shouldnt it be smth like vector out of range error?I was trying to optimize algorithm and spent about 20 minutes for such a stupid mistake :(
•  » » 17 months ago, # ^ |   +21 Unfortunately undefined behaviour does not guarantee a RE, so the $O(N^2)$ loop triggered TL before the out-of-range managed to trigger RE.This is why undefined behaviour is annoying, you have no guarantees on what will happen.
 » 17 months ago, # |   +17 Is it error? His rating color is strange. See.
•  » » 17 months ago, # ^ |   +2 The color was updated but the rating wasn't after ratings were updated for this round. May be a caching issue.
•  » » 17 months ago, # ^ |   +8 qoqoqoqo did 2 contests at the same time today
•  » » » 17 months ago, # ^ |   0 OK. I see. :)
 » 17 months ago, # |   +13 Did anyone actually get WA on test case 233?
•  » » 17 months ago, # ^ |   +76 Used unnecessary hash, and the modulo is $998244353$
•  » » » 17 months ago, # ^ |   -12 for Div2 F
 » 17 months ago, # | ← Rev. 2 →   0 In problem C Div 2, why string "()((()))" has 3 prefix. I think it only has 2 prefix. Sorry for my bad English. I found my error sorry
•  » » 17 months ago, # ^ |   0 It has 2 regular prefixes. () and ()((()))
•  » » 17 months ago, # ^ |   +3 Probably you were using operation {i,i} and wanted to flip i'th character from '(' to ')' or vice versa. And came to the conclusion because of the checker's response.
•  » » » 17 months ago, # ^ |   0 Yeah! I found it and fix it. Thanks you!
 » 17 months ago, # |   +3 What's the $O(n\log n)$ FFT solution to D2?
•  » » 17 months ago, # ^ |   +26 It seems like FFT/NTT but it can be solved in an easier way...If you work out the formula in a mode like DPLet a[n+1]=a[1], dp[i][j] stands for the first i problems new solution has j points more than the previous one.You can work out such a formula: if(a[i]!=a[i-1])dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]+dp[i-1][j]*(k-2); else dp[i][j]=dp[i-1][j]*k You may realize this means...Let g=sum(1,...,n)[a[i]==a[i+1]], h=n-gYour answer is sum of (r[1],r[2],...,r[n]) in f(x)=(r[0]+r[1]x+r[2]x^2+...)+(r[-1]*(1/x)+r[-2]*(1/x^2)+...)And f(x)=k^g * (x+k-2+1/x)^h(This is really an NTT problem !)(deleted) :)It can be concluded that r[i]=r[-i]So the answer is (r[-inf]+...+r[-1]+r[1]+...+r[inf])/2 = (r[-inf]+...+r[-1] +r[0]+r[1]+...+r[inf])/2 — r[0]/2The highlighted area is obviously (k^n)/2 (let x=1, f(x)=(r[-inf]+...+r[-1]+r[1]+...+r[inf]) = k^(g+h) = k^n) , and we now only need to work out r[0].Then we can expand f(x) = k^g * (x+k-2+1/x)^hLet C(n,r) be combinatorial number:Then it is nothing but combination problems... r[0]=C(h,0)*C(h,0)*(k-2)^(h)+C(h,1)*C(h-1,1)*(k-2)^(h-2)+...+C(h,i)*C(h-i,i)*(k-2)^(h-i*2) This is my code and you might better understand my explanation after rreading it.65652697
•  » » » 17 months ago, # ^ |   0 Thank you very much. I don't think one has to go through building a polynomial or doing the dp to get to this solution but it is a different approach from what I had thought.Pretty nice!
 » 17 months ago, # | ← Rev. 2 →   0 If someone is interested in a Online soulution to Div2D or Div1B, here it is: https://codeforces.com/contest/1262/submission/65678852
•  » » 17 months ago, # ^ |   0 Great use of Persistent Segment Trees!!!
•  » » 17 months ago, # ^ |   +3 Hello Leonardo_Paes,Can you help with the logic you've used? Basically how you're dealing with the children nodes and how persistence helps here?
•  » » » 17 months ago, # ^ | ← Rev. 2 →   +3 Okay got it.Explanation: We're sorting the numbers given. The max elements first, if value is same, then the element with the minimal index is put first. Let's say this sorted array is A.Now we create an array of segtree roots of size n. Each element of A is inserted into the segtree, by creating another root node. (Persistent segtree). Now each Node of the segtree looks like this: Two pointers to left and right child. Two vars: val --> contains the max element's value in the subtree Qty: number of elements in the subtreeNow for each element in A, we insert it inside the new version of the segtree. When we do a query, we search inside the kth node, for the pos'th element. I.e, look inside the root[k], for the pos'th element. We're sure that the first "k" elements have the answer as they are the max elements. If someof them are equal, then the ones with the least index are put first. So yeah, everything is going to be fine.Search query is simple enough.Great solution Paes!
•  » » » » 17 months ago, # ^ |   +1 Thx, your explanation is great too!
 » 17 months ago, # | ← Rev. 2 →   0 Div2 B: Can anyone tell me why my first submission gets RTE. I cant find out any difference between those two submissions except the bool array part(bool vis[100000]) that I used in my RTE code but in AC code I just used mapvis. Thanks :)
 » 17 months ago, # |   +24 I wonder what's the chance of solving div1E with a wrong solution. Seems like there are a lot of possible outputs outside of extreme cases like N times N.I just made this (correct) solution: Sort everything. If the last (maximum) element is $x \le N-1$, solve recursively for all elements except the first (smallest) one — it's guaranteed that a solution exists and has between $x$ and $N$ operations. Then add the first element $y$ to the first $y$ operations. If the last element is $N$, we need $N$ operations that use the last element plus at most one that doesn't use it. If there's at least one other element $N$, that plus one operation can be "subtract 1 from all elements $N$ except the last one". Then, solve recursively for all elements except the last one — there are $N-1$ or $N$ operations, and just like before, add the last element to all these operations; if there are $N-1$, make another operation that's just subtracting from the last element. Otherwise, let's denote the second-to-last element by $1 \le x \le N-1$. Notice that the first branch of this algorithm will basically ignore the first $N-1-x$ elements and won't ever create an operation that subtracts just from one of them; also, the number of operations it will give us is actually $x$ or $x+1$. Therefore, we can first create $N-1-x$ operations that are subtracting from each of the first $N-1-x$ elements, solve recursively for everything except the last element and since we have $N-1$ or $N$ operations, add the last element to operations just like above. The fact that all elements are non-zero matters, since $(0, 0, 2)$ isn't solvable. The recursive calls don't perfectly satisfy that, but they satisfy a more specific condition: if the maximum is $x$, there are at least $x$ non-zero elements, which is sufficient (proof by this solution).
 » 17 months ago, # |   +80 When will editorial be published?
 » 17 months ago, # | ← Rev. 3 →   -10 For Div2E, My idea was the following: Spoiler Push into a queue, only those cells that form the boundary of a connected shape. Perform a BFS using that queue(like a multisource BFS) to find the source of the fire. Update my time=min(time, cnt) only when i am at a cell and unable to move anywhere during the BFS. After the BFS, I place an 'X' on all those cells whose BFS times>=mintime else '.' Finally display the answer Here is a link to my submission: 65692433 (It gives WA on Test Case 7) I am able to identify my mistake; But I am unaware of a possible fix. Please help if you feel there is a small fix to this issue, or let me know if my entire logic has to be altered :)
•  » » 17 months ago, # ^ |   +26 I don't know how it can be done using BFS only.But i can share my approach SpoilerApply a binary search on time because if forest can be damaged exactly in time t then it can be damaged in time t-1 as well by increasing the tree from where fire start.to check for particular t find all cell such that all tree are burnt in area covered by that cell after time t. after finding all such cell check that whether it doesn't left any cell that is burnt but not covered by any initial cell after time t.Hope it helps
•  » » » 17 months ago, # ^ |   0 Thanks a lot, I shall try and modify my approach with this :)
 » 17 months ago, # |   +33 Is there editorial?
•  » » 17 months ago, # ^ |   +18 Just means tutorial.
 » 17 months ago, # |   +12 editorial ?
 » 17 months ago, # |   0 E D I T O R I A L ?
 » 17 months ago, # | ← Rev. 2 →   +11 Can someone explain me how to solve the F2 (Div. 1 D2) problem?
•  » » 17 months ago, # ^ | ← Rev. 11 →   +34 First define $f(i, j)$ as the number of ways to choose the first $i$ answers so that $score(a') - score(a) = j$. Doing DP on this function will get an $O(n^2)$ solution, which is sufficient for the easier subtask, but not the harder one. Details of DP transition$f(0, 0) = 1; f(0, j) = 0 \text{ for } j \neq 0$If $h_i = h_{(i \text{ mod } n) + 1}$ (defined below as a fixedpoint), $f(i, j) = f(i-1, j) \cdot k$, as all $k$ answers won't change the score difference.If $h_i \neq h_{(i \text{ mod } n) + 1}$ (defined below as a movepoint), $f(i, j) = f(i-1, j-1) + (k-2) \cdot f(i-1, j) + f(i-1, j+1)$, as there is one answer ($h_{(i \text{ mod } n) + 1}$) that will increase the score difference by one, one answer ($h_i$) that will decrease it by one, and $k-2$ answers that won't change it.Final answer is $\displaystyle\sum_{j > 0} f(n, j)$; or in English, the sum of all terms $f(n, j)$ where $j > 0$To ease implementation, I opted to use a special wrapper class that allows an array to be addressed by a negative offset.Sample: 65653678To solve the harder subtask, the key insight is to notice that $f$ is symmetrical with respect to $j$ (i.e. $f(i, j) = f(i, -j)$). So we can derive$ans = \displaystyle\sum_{j > 0} f(n, j) = \displaystyle\frac { k^n - f(n, 0) }{2}$because we start with the total number of possible answer suits, $k^n$, subtract the suits where the score difference is $0$, and then divide by two to leave the suits with positive difference.The only thing left then is to calculate $f(n, 0)$ quickly. Define a movepoint to be an index $i$ where $h_i \neq h_{(i \text{ mod } n) + 1}$, and a fixedpoint to be otherwise. Let $m$ be the total number of movepoints; obviously the number of fixedpoints is $n - m$. Then$f(n, 0) = k^{n - m} \cdot \displaystyle\sum_{i = 0}^{\lfloor m / 2 \rfloor} \binom{m}{i} \binom{m-i}{i} (k-2)^{m - 2i}$Explanation is as follows: the fixedpoints do not affect the score difference, so you can choose any of the $k$ answers for all of them, thus the $k^{n-m}$ term. The summation term is for the movepoints; for each integer $i$ in $[0, \lfloor m / 2 \rfloor]$ we can choose $i$ movepoints to be increasing, $i$ movepoints to be decreasing, and the rest to not affect the score difference. There is only one answer that will make a movepoint increasing and decreasing each, and $k - 2$ answers to not affect the score difference.This can be now calculated in $O(n \log)$ with precalculated factorials and modular multiplicative inverse.Note that for the formula to work in all cases, it is important that $0^0 = 1$.Sample: 65689955
•  » » » 17 months ago, # ^ |   0 Thanks! I'll try it!
•  » » » 7 months ago, # ^ |   0 Amazing! Thanks mate :)
 » 17 months ago, # |   -17 hello
 » 17 months ago, # |   0 Why does this solution (65714794) fails on test #4? Is my idea wrong?My basic idea is to divide into 3 types according to the changes (positive, negative or no change at all) after the shifting.
 » 17 months ago, # |   0 How to solve div1E?
•  » » 17 months ago, # ^ |   +2
•  » » » 17 months ago, # ^ |   -8 SAVAGE :p :p
 » 17 months ago, # |   +12 Editorial?
 » 17 months ago, # |   0 Can someone explain the Approach Behind Div2 D2/ Div1 B2 ?? I have seen few subsimissions with Fenwick and I didn't understand the idea Thx :))
 » 17 months ago, # |   0 For me, only one problem (Xor-Set) is visible on the https://codeforces.com/problemset page. screenshotDoes anyone else have this issue / know if it'll be fixed?
•  » » 17 months ago, # ^ |   +8 these problem are on 2nd page Problemset with contest number 1227
 » 17 months ago, # |   +8 Where is editorial?
 » 17 months ago, # |   +19 These are two of my solutions for 1F:65727787 got RE on test 20, and 65727798 got WA on test 20.The only difference between them is the const size of an array. (In my code, it is const int M)But when I output the maximum lable used in the array in 65727941, it didn't violate any of the two.Then I #define int long long` in another submission 65728594, and it got RE on 20. But the const size I used is the larger one of the two submissions.I wonder why it got RE, and I'll appreciate your help!
 » 17 months ago, # |   0 still no editorial :(
 » 17 months ago, # | ← Rev. 2 →   -8 Editorial is published ok
 » 17 months ago, # |   0 Problem: 1262B - Box Submission: 65713954Silly question! But I am having trouble finding why this code gives duplicate elements in case 2-105. Can anyone help?
 » 17 months ago, # |   -8 You can always AK IOI!!!
•  » » 17 months ago, # ^ |   +2 Is anyone here?
 » 17 months ago, # |   +10 I think this contest is so great!
 » 17 months ago, # |   0 editorial: https://codeforces.com/blog/entry/71740
 » 17 months ago, # |   0 What is wrong with this solution for C (Messy): Dry run gives the right answer!! https://codeforces.com/contest/1262/submission/65926144
 » 17 months ago, # |   -8 Good luck!