Автор RDDCCD, 5 лет назад, перевод, По-русски

Добрый день!

В 24.11.2019 11:05 (Московское время) состоится Отборочный Раунд 3 олимпиады для школьников Технокубок 2020. Раунд будет длиться два часа. По его результатам лучшие участники (но не более 45% от общего числа участников раунда) будут приглашены на финальный этап в Москву. Для регистрации на раунд и участия перейдите по ссылке. Не забудьте заранее зарегистрироваться на раунд! Для опоздавших будет открыта дополнительная регистрация.

Зарегистрироваться на Отборочный Раунд 3 →
Соревнование открыто для всех в виде отдельных раундов для первого и второго дивизионов.
Для всех участников всех трех редакций этого соревнования будет пересчитан рейтинг.

Параллельно с Отборочным Раундом будут проведены открытые рейтинговые раунды для обоих дивизионов, в них могут принять участие все желающие.

Напомним, что согласно правилам раундов Codeforces во время соревнования ваши решения будут тестироваться только на претестах (предварительном и неполном наборе тестов), а системное тестирование состоится после окончания раунда. Обратите внимание, что претесты не покрывают все возможные случаи входных данных, поэтому тщательно тестируйте свои программы! После прохождения претестов у вас будет возможность заблокировать решение, тем самым получив привилегию искать ошибки и взламывать чужие решения, но отказавшись от возможности перепослать ваше решение при каких-либо обстоятельствах (например, даже если вы найдете ошибку или вас взломают). Со временем задачи падают в стоимости. После системного тестирования учитываются только полные решения. Подробнее про правила соревнований можно прочитать по ссылкам:

Регистрация на олимпиаду Технокубок еще открыта. Победителей и призеров олимпиады ждут значительные квоты при поступлении в престижные технические вузы России и ценные призы! Если вы — школьник 8-11 классов и пока не зарегистрировались на Технокубок, то самое время сделать это:

Зарегистрироваться на олимпиаду →
После регистрации на олимпиаду не забудьте зарегистрироваться на Отборочный Раунд!

В финал соревнования будут приглашены лучшие участники каждого из отборочных раундов (но не более 45% от общего числа участников раунда).

Авторы отборочного раунда — я, nocriz, BledDest, adedalic и MikeMirzayanov. Кроме того, хочу выразить благодарность тестерам: KAN, Supermagzzz, Stepavly, AdvancerMan и unreal.eugene!

Для тех, кто впервые на Codeforces: в таблице ниже вы можете найти примеры решений на всех поддерживаемых языках:

Группа языков Языки программирования / компиляторы Примеры
C GNU C, GNU C11 10903473, 17029870
C++ GNU C++, GNU C++11, GNU C++14, GNU C++17, MS C++, etc. 23794425, 5456501
C# Mono C#, MS C# 3195513, 3794163
D D 5482410, 2060057
Go Go 7114082, 21366098
Haskell Haskell 455333, 1668418
Java Java 8 25491359, 23678167
JavaScript V8 35963909, 35681818
Kotlin Kotlin 25779271, 25204556
OCaml OCaml 6157159, 1281252
Pascal Delphi, FPC, Pascal.NET 1275798, 1259434
Perl Perl 2519448, 1277556
PHP PHP 413942, 35875300
Python Python 2, Python 3, PyPy2, PyPy3 35883730 (Py2), 36179112 (Py3)
Ruby Ruby 1837970, 1289551
Rust Rust 25180002, 35652442
Scala Scala 35847980, 2456025

Удачи!

Разбалловка:

Технокубок: 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)

  • Проголосовать: нравится
  • +202
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится -49 Проголосовать: не нравится

Is it rated?!?!?1

»
5 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

У меня есть вопрос если ты зарегистрировано в технокубке почему несможешь в див.2

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    А зачем тебе див2, если ты и так участвуешь в Технокубке?

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

У меня возникла проблема

Я уже прошел на финал технокубка по второму раунду, в личном кабинете об этом написано. Теперь я хочу поучаствовать в раунде, но при попытке зарегистрироваться появляется окно с надписью, что мне следует зарегистрироваться на отборочный раунд и регистрация на него проходит успешно. Так же не должно быть, MikeMirzayanov?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    В самом деле, была ошибка с конфигурацией. Исправил, спасибо.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It's time to participate in the great contest.

»
5 лет назад, # |
  Проголосовать: нравится +51 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +97 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

В русском интерфейсе раунд #602 не показывается в окне "Обратите внимание" ни на главной странице, ни в "прямом эфире", ни на (этой) странице с объявлением раунда.

В английской версии на этой странице тоже нет, но по крайней мере есть на главной и в прямом эфире.

»
5 лет назад, # |
  Проголосовать: нравится -25 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +29 Проголосовать: не нравится

    Why do you write this? Just curious

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 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 :(

»
5 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +95 Проголосовать: не нравится

    It's OK! You will win!

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

    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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Scoring Distribution?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

How to solve Div 1 D2?

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 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.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +47 Проголосовать: не нравится

>tfw I'm not fast enough for speedforces

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +22 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится -26 Проголосовать: не нравится

    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.
    
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 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)

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 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?

      • »
        »
        »
        »
        5 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 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?

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I keep failing pretest 2 in problem A

Any ideas?

»
5 лет назад, # |
  Проголосовать: нравится +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)

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      5 лет назад, # ^ |
      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

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 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.

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 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.

      • »
        »
        »
        »
        5 лет назад, # ^ |
        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...

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
          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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +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.

  • »
    »
    5 лет назад, # ^ |
    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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Could anyone figure out test 2 of Div2 C?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +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.

»
5 лет назад, # |
  Проголосовать: нравится +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?

  • »
    »
    5 лет назад, # ^ |
    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.

  • »
    »
    5 лет назад, # ^ |
    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.

»
5 лет назад, # |
  Проголосовать: нравится 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

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    3
    1 3
    1 3
    1 3
    ans = 0
    
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +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

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 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
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    If left<right, the answer is 0.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve Div2 D2 ?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +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

    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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 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?

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +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.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +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

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится 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.

»
5 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

Lacked 1 minute to submit D T_T

E is really nice though...

»
5 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

hope that I can get +1 rating :P

»
5 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

How to solve Div2 C?

  • »
    »
    5 лет назад, # ^ |
    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...

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +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.)

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +101 Проголосовать: не нравится

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

Counterexample
»
5 лет назад, # |
  Проголосовать: нравится +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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    Same :(

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +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.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится -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.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +23 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +10 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится 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.

            • »
              »
              »
              »
              »
              »
              »
              5 лет назад, # ^ |
                Проголосовать: нравится +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."

              • »
                »
                »
                »
                »
                »
                »
                »
                5 лет назад, # ^ |
                  Проголосовать: нравится +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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 лет назад, # ^ |
                    Проголосовать: нравится 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.

    • »
      »
      »
      5 лет назад, # ^ |
      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.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +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.

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 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 65650523

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

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится +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.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +37 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится -16 Проголосовать: не нравится

    I think we should take a vote

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 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.

»
5 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Очень класный контест, задачи супер.

Все прошло абсолютно без багов, лагов да и рейтинг очень быстро изменился!

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +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.

»
5 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Did anyone actually get WA on test case 233?

»
5 лет назад, # |
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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +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.

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +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 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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 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!

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Great use of Persistent Segment Trees!!!

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +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?

    • »
      »
      »
      5 лет назад, # ^ |
      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 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!

»
5 лет назад, # |
  Проголосовать: нравится +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).
»
5 лет назад, # |
  Проголосовать: нравится +80 Проголосовать: не нравится

When will editorial be published?

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится -10 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

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

    But i can share my approach

    Spoiler
»
5 лет назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

Is there editorial?

»
5 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

editorial ?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

E D I T O R I A L ?

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
    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

    To 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

»
5 лет назад, # |
  Проголосовать: нравится 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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve div1E?

»
5 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Editorial?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

screenshot

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

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Where is editorial?

»
5 лет назад, # |
  Проголосовать: нравится +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!

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

still no editorial :(

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

Editorial is published ok

»
5 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

You can always AK IOI!!!

»
5 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

I think this contest is so great!

»
5 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Good luck!