Codeforces Round 602(Div.1, Div.2) and Technocup — Elimination Round 3
By RDDCCD, 5 years ago, In English

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

4.jqdai0815

5.djq_cpp

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

Div2 Top5

1.funtik

2.PureWhite

3.nehnait

4.Fuyuki

5.rama_pang

And also the Editorial is out.

  • Vote: I like it
  • +202
  • Vote: I do not like it

Comments Comments (196)
| Write comment?
»
5 years ago, # |
  Vote: I like it -49 Vote: I do not like it

Is it rated?!?!?1

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Quoting from the post : "Div. 1 and Div.2 editions are open and rated for everyone."

    → Reply
»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Please fix the Codeforces Round #number in the title! Looks like a by-product of Technocup Elimination Round 2 and 3 :p

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -23 Vote: I do not like it

    No its not wrong its technocup for both divisiors

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I meant it should be #602 instead of #596. #596 was for Technocup Elimination Round 2.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    Fixed. Sorry for the stupid mistake while copying.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      How many problems will be?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Eight in total.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Perfect!!! Thanks a lot!

          → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it -25 Vote: I do not like it

          But with 2 problems split into subtasks, so 6 in total.

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +13 Vote: I do not like it

            for both divisions we have 8 in total :)

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it -48 Vote: I do not like it

              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".

              → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's time to participate in the great contest.

→ Reply
»
5 years ago, # |
  Vote: I like it +51 Vote: I do not like it

When I saw 2020 I thought my time machine leaped to the wrong date

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Can I borrow your time machine. I would like to retake my math (yes MATH) test from last week. Thank you!

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +97 Vote: I do not like it

      Nope, time travel is not for trivial tasks. Plutonium is very precious, I use it only to fight the organization.

      → Reply
»
5 years ago, # |
  Vote: I like it -25 Vote: I do not like it

Hopping to get some great problems more focused on logic and Algorithms rather than language of problem statements.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    Why do you write this? Just curious

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 :(

      → Reply
»
5 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Ehhh... It's the middle of the night in Poland. Hope it'll be ok :/

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    9 am to be precise... you guys have no mercy :/ Can you al least tell us the number of problems and scoring?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      We have eight problems in total. Scoring will be announced before the contest.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it -10 Vote: I do not like it

        "in total", so some of them for div2 and some of them for div1?

        → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      Every time is going to be in the middle of the night somewhere...

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +147 Vote: I do not like it

        I know, I just wanted to joke about 9 am being the middle of the night...

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +219 Vote: I do not like it

          I didn't get the joke because 9am is obviously the middle of the night, right? :P

          → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +95 Vote: I do not like it

    It's OK! You will win!

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +161 Vote: I do not like it

      :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.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it -48 Vote: I do not like it

        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?

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +58 Vote: I do not like it

        But in the film zombies got in...

        → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Where I live, the contest runs from 12:05am to 2:05 am! And I still will be writing the contest :D

    Competitive Programming >>>> Sleep >>>> School

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Scoring Distribution?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Cannot expect the contest to have any lesser implementation, with so many authors. :(

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Great Problems and especially Div.2 D2(Div.1 B2) is interesting.

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve Div 1 D2?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +21 Vote: I do not like it

    you can calculate the suits that points change is zero, and substract it,than it's double the answer

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Do not know about java, but in c++ I have heard there is PBDS for this purpose.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This task can be done using Binary Lifting

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I used one segment tree, with finding the kth in the query, but it is not implemented in java :/

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think there is no such thing in Java. You need to do Binary Search and Segment Tree query to get the nth element.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Simply segment tree will suffice, It involves binary search itself.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how to use it with pair <int, int>. 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.

      → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +47 Vote: I do not like it

>tfw I'm not fast enough for speedforces

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    I think that it was also a lot of "implementation-forces" too?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      Yeah, but mostly about fast implementation, not about ideas that simplify implementation.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to access an element in c++ set with it's position?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    You can't. C++ set is not addressable.

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 4   Vote: I like it -26 Vote: I do not like it

    you can have an iterator and then use advance().

    set<ll> st;
int position = 4;
// fill up the set
auto iter = st.begin();
advance(iter, position);
// iter is now on 5th position.
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I do not think you can. Try to use __pbds or write a segment-tree/BST instead.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        Here

        And if you can understand Chinese, This is also a great article.

        You can use 'custom test' to test if it results compilation error.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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?

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            Maybe it differs from compiler to compiler. I'm using g++ 8.3.0 on Ubuntu x64, without any problems when using __pbds.

            → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I keep failing pretest 2 in problem A

Any ideas?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    1
3
1 3
2 2
6 7

    answer 4

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My output is 4 too

      I can't figure out where my solution fails

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think mine failed on pretest 2 when I first submitted because of something like: 1 2 1 10 2 9

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Isn't the result 0?

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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?

            → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it 
    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
    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    try this : 1 3 1 5 2 3 4 7

    answer >>> 1

    → Reply
»
5 years ago, # |
  Vote: I like it +32 Vote: I do not like it

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

Unable to parse markup [type=CF_MATHJAX]

. 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)
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +10 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

    I got AC (~500ms) 65655948 using prefix sums, without any optimization.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Me too, but I had to change the code from BFS to prefix sums, which was a bit annoying for a fast-paced contest.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it +10 Vote: I do not like it

        65657404 your code runs on ~600 ms, if you call check

        Unable to parse markup [type=CF_MATHJAX]

        times. Look at the two lines before for (int step...
        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Weird... I just did binary search + bfs with the same complexity without consciously optimizing anything and it passed in 343ms.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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.

      → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Let's put aside the question about tight limits for now. The problem in your solution is next: Instead of

    Unable to parse markup [type=CF_MATHJAX]

    , your solution is actually

    Unable to parse markup [type=CF_MATHJAX]

    , because checking 
    if (ans + step > n && ans + step > m) continue;

    is wrong.

    P.S.: Sorry for being a slowpoke.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone figure out test 2 of Div2 C?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div.2 F1(Div.1 D1)?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
»
5 years ago, # |
  Vote: I like it +23 Vote: I do not like it

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?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +14 Vote: I do not like it

    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

    Unable to parse markup [type=CF_MATHJAX]

    , we should generate and process them iterating over K.
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I see.

      By the way, this quite obvious solution passed if I maintain the set of ranges dynamically. (my submission)

      → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    The memory limit indeed seems too tight. Naively writing the obvious solution uses around

    Unable to parse markup [type=CF_MATHJAX]

    memory so the limits could be much higher. I had to do memory optimization on my correct solution (65667891) with memory usage around

    Unable to parse markup [type=CF_MATHJAX]

    to get it to pass (65668033)

    The trick to optimise from

    Unable to parse markup [type=CF_MATHJAX]

    to

    Unable to parse markup [type=CF_MATHJAX]

    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.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
        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

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
    3
1 3
1 3
1 3
ans = 0
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      i solved D1 and D2 in around 30 minutes A took my 40 minutes(still unsolved) which spoils my whole contest.... R.I.P

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        When "minr >= maxl" you can find a common segment shared by all, so only need one point (length 0) to cover all segments.

        conclusion
        → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If left<right, the answer is 0.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div2 D2 ?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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

    1. Sort queries by their increasing length
    2. 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.
    3. Give kth smallest element from the treap.

    Solution

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You can use Segment tree to do order statistics in some cases.

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks a lot!! But I have found an implementation for order statistics. You can see my submissions.

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
»
5 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Lacked 1 minute to submit D T_T

E is really nice though...

→ Reply
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

hope that I can get +1 rating :P

→ Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve Div2 C?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    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...

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      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.)

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please someone explain me the solution of A . I was thinking to do a line sweep

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Take the interval between leftmost of endpoints and rightmost of start-points of intervals.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    main idea
    → Reply
»
5 years ago, # |
  Vote: I like it +101 Vote: I do not like it

Why do obviously wrong solutions like https://codeforces.net/contest/1261/submission/65640232 pass for D1C?

Counterexample
→ Reply
»
5 years ago, # |
  Vote: I like it +160 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Same :(

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +38 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it -23 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          He is talking about div1 not div2. Div1A = Div2C, Div1B1 = Div2D1

          → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          teja349 was talking about Div1A and Div1B1

          → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +23 Vote: I do not like it

        I agree about point distribution, but not about subtasks overall. With better thought-out point distributions I think it can work just fine.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          Can you suggest a good point distribution for today's contest?

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it +8 Vote: I do not like it

              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."

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                5 years ago, # ^ |
                  Vote: I like it +16 Vote: I do not like it

                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.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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.

                  → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 3   Vote: I like it +24 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 65650523

          I think this is first time the first subtask really helps me with second.

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +11 Vote: I do not like it

            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.

            → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      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.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    The same here. Vote you up! Subtasks are also boring for me and make me upset.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    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.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -16 Vote: I do not like it

    I think we should take a vote

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why this solution gets TL instead of RE? codeforces.com/contest/1261/submission/65650035

The problem with line ~115. I wrote "j<=n" instead of "j<=m". Shouldn`t 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 :(

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    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.

    → Reply
»
5 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Is it error? His rating color is strange. See.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    The color was updated but the rating wasn't after ratings were updated for this round. May be a caching issue.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    qoqoqoqo did 2 contests at the same time today

    → Reply
»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Did anyone actually get WA on test case 233?

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It has 2 regular prefixes. () and ()((()))

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah! I found it and fix it. Thanks you!

      → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

What's the $$$O(n\log n)$$$ FFT solution to D2?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    It seems like FFT/NTT but it can be solved in an easier way...

    If you work out the formula in a mode like DP

    Let 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-g

    Your 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]/2

    The 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)^h

    Let 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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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!

      → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

If someone is interested in a Online soulution to Div2D or Div1B, here it is: https://codeforces.net/contest/1262/submission/65678852

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Great use of Persistent Segment Trees!!!

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      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 subtree

      Now 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!

      → Reply
»
5 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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

    Unable to parse markup [type=CF_MATHJAX]

    , 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

      Unable to parse markup [type=CF_MATHJAX]

      . Notice that the first branch of this algorithm will basically ignore the first

      Unable to parse markup [type=CF_MATHJAX]

      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

      Unable to parse markup [type=CF_MATHJAX]

      operations that are subtracting from each of the first

      Unable to parse markup [type=CF_MATHJAX]

      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

    Unable to parse markup [type=CF_MATHJAX]

    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).
→ Reply
»
5 years ago, # |
  Vote: I like it +80 Vote: I do not like it

When will editorial be published?

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -10 Vote: I do not like it

For Div2E, My idea was the following:

Spoiler

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 :)

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    I don't know how it can be done using BFS only.

    But i can share my approach

    Spoiler
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot, I shall try and modify my approach with this :)

      → Reply
»
5 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Is there editorial?

→ Reply
»
5 years ago, # |
  Vote: I like it +12 Vote: I do not like it

editorial ?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

E D I T O R I A L ?

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

Can someone explain me how to solve the F2 (Div. 1 D2) problem?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 11   Vote: I like it +34 Vote: I do not like it

    First define $$$f(i, j)$$$ as the number of ways to choose the first $$$i$$$ answers so that

    Unable to parse markup [type=CF_MATHJAX]

    . 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

    To solve the harder subtask, the key insight is to notice that $$$f$$$ is symmetrical with respect to $$$j$$$ (i.e.

    Unable to parse markup [type=CF_MATHJAX]

    ). So we can derive

    Unable to parse markup [type=CF_MATHJAX]

    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

    Unable to parse markup [type=CF_MATHJAX]

    , and a fixedpoint to be otherwise. Let $$$m$$$ be the total number of movepoints; obviously the number of fixedpoints is $$$n - m$$$. Then

    Unable to parse markup [type=CF_MATHJAX]

    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

    Unable to parse markup [type=CF_MATHJAX]

    term. The summation term is for the movepoints; for each integer $$$i$$$ in

    Unable to parse markup [type=CF_MATHJAX]

    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

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve div1E?

→ Reply
»
5 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Editorial?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For me, only one problem (Xor-Set) is visible on the https://codeforces.net/problemset page.

screenshot

Does anyone else have this issue / know if it'll be fixed?

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Where is editorial?

→ Reply
»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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!

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

still no editorial :(

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

Editorial is published ok

→ Reply
»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

You can always AK IOI!!!

→ Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I think this contest is so great!

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

editorial: https://codeforces.net/blog/entry/71740

→ Reply
»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Good luck!

→ Reply