Блог пользователя Supermagzzz

Автор Supermagzzz, 4 года назад, По-русски

Привет, Codeforces!

<almost-copy-pasted-part>

Привет! Во 16.02.2021 17:35 (Московское время) начнётся Codeforces Round #702 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 7 задач. Задачи подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше, могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы будем расстроены, если у многих попадают решения после окончания контеста.

Вам будет предложено 7 задач и 2 часа на их решение.

Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
  • не иметь в рейтинге точку 1900 или выше. Независимо от того, являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Задачи на этот раунд были придуманы MikeMirzayanov, Supermagzzz, Stepavly и sodafago

Спасибо MikeMirzayanov за платформы и координацию нашей работы. Спасибо darkkcyan, Sho, sodafago, budalnik, kocko, akagami_no_shanks, bugdone, iankury, Gassa, infinitepro, bfs.07 за помощь в подготовке и тестировании раунда.

Удачи!

</almost-copy-pasted-part>

UPD: Разбор появился!

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

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

Every announcement of Div3 round from Supermagzzz, Stepavly and MikeMirzayanov makes me happy!

»
4 года назад, # |
  Проголосовать: нравится +87 Проголосовать: не нравится
As a
»
4 года назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

Good luck everyone !!!

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

Sick, I miss div 3 contests so much, looking forward to participating into this!

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

Excited

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

is div3 rated for someone with current rating < 1600 but his max rating >= 1900 ??

Edit : sorry i didn't see this Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

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

    It's based on current rating only. Max rating doesn't make a difference.

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

      so what about this point do not have a point of 1900 or higher in the rating. ?? what do they mean of trusted participants ?

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

        Accounts that have reached a rating >= 1900 at any point can safely be assumed to belong to the stages beyond amateur grade. Therefore, having them part of the "official standings table" that is published is likely to distort the actual standings list.

        Similarly, new accounts could be alts to high rated coders as well and including those would lead to similar results.

        Therefore, while the round will be rated for anyone below 1600 (at the time of the contest, I believe — or maybe registration, this is actually my doubt as well). The official standings list published simply won't contain the names of these "participants that may not be trusted as div 3 folk"

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

    I'm quite surprised that you had $$$203$$$ contests and you still didn't know.

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

Is the rated cap for rounds based on the user's rating at the time of the contest or at the time of the registration?

I tried searching for some relevant blog but couldn't find one.. Thanks in advance :)

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

    At the time of the contest rather.

    Calculation of rating, finalization of winners board logic happens after contest as well as validation of being trusted participant and/or below 1600 member.

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

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

Yah Codeforces Hey!

Yah hum coders hey

Yaha Cowding ho rahi hey!

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

Finally, a div3 round that I missed so much

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

Единственный раунд где я могу участвовать(

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

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

1

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

Previous rating change unrolled, will this contest be rated for me ?

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

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

Judging by my very poor performance of the last round(spoiler: never enter a round 40 minutes after it started:)) i think that this round should be rated for me. Are the new ratings coming until the start of this div3?

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

will the new ratings come before div3 or not ??

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

From the last contest there seems to be less participation because of busy schedules and lot of assignments of college.

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

As a participant, I wish no "Wrong Answer On Test x" situation.

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

This is my first time to compete in CF. good luck. 祝我好运!

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

Okay

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

Wait is over ❤ Finally div 3 after long time

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

Why there is a massive difference between last and this time DIV3 contest??

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

Thank you ! perfect time for div3

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

Wtfffff Muffinhead 6 problems in 9 minutes how is this even possible !!

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

    It seems that codeforces recognized him as a cheater because he is not on the scoreboard anymore.But I think that he his Benq with another account any ideas?

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

      Even for a legendary grandmaster that's too fast but that's weird why would he participate in unrated contest from another account

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

I am unable too see problems or register can someone help?

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

Positive delta YES!!!!

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

Is it just me or these div3 rounds have become wayy too easy.

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

is this a div4?

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

wrong answer using segment tree on g why? Here:107616153

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

    Seriously, how do you expect people to understand your solution just by hinting with some topic.

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

invented ! =discovered.

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

Supermagzzz's DIV 3 are easier as compared to vovuh's.

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

speedforces :(

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

I was not particularly quick today but still solved all problems and recorded a screencast with explanations

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

The difficulty from A-E is in decreasing order

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

Felt more like a Leetcode Contest without its final problem

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

Can't we solve problem f without using the concept of hashing? initially, I was thinking to declare an array of size 10^9. later realized that it would give any runtime error or memory limit exceed.

Is there any way other than hashing or map to solve f ?

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

    you can store the numbers in an array, sort it and then count how many there is for a given value but it's nlog n

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

    I solved it using Treemaps but Yes You can easily convert it to hashmap solution.

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

My solution for problem C outputs "NO" in my local device while outputs "YES" when I submit, for input 34. It tried with brackets also, but results are the same. It showing 'wrong answer for test 1'.

my solution is: https://codeforces.me/contest/1490/submission/107615310

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

Why this solution (for problem F) TLE on test 2. I think the time complexity is O(nlogn): https://codeforces.me/contest/1490/submission/107618301

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

Does someone know a test where this solution for G might fail? : https://codeforces.me/contest/1490/submission/107619800

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

is all problem of div 3 is of equal points or C(poihnts)>B

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

Spent 35 minutes on this bug. fml.

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

 What the heck is Unexpected verdict

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

    Inside the system there are solutions marked as correct solutions. If one of these solutions fail on a hack (maybe cause of WA, RTE, TLE, MLE, ...) then the hack is marked having "Unexpected verdict".

    When it happens, then just wait for a little while. Usually the problem setters fix it pretty quickly.

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

Problem C why my hacking verdict is 'Unexpected verdict'

Input :
100
1000000000000
1000000000000
1000000000000
1000000000000
1000000000000
...
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Different problem statements, but very similar question to E

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

Finally very good Div.**3** contest! All who are Div.2-level could solve almost all problems.

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

How to Solve G?

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

    if( prefix_sum[index_j] == xi ) ans = index_j — 1

    else if , for some positive integer k if prefix_sum[index_j] + k*prefix_sum[n] = xi or in other words prefix_sum[index_j] is congruent to x mod prefix_sum[n] then , ans = k*(xi-prefix_sum[index_j])/prefix_sum[index_j] + index_j-1; store prefix_sum and prefix_sum % prefix_sum[n] in map to query

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

    Create prefix sum $$$s_1,..,s_n$$$. The condition for which the result is -1 is $$$s_n\leq 0$$$ and $$$x > sm = max_{i=1..n}s_i$$$. Otherwise, if $$$x\leq sm$$$, find smallest index $$$i$$$ that $$$s_i\geq x$$$, the answer is $$$i-1$$$. For the last case where $$$x>sm$$$ and $$$s_n>0$$$. Let $$$p$$$ be the smallest value such that $$$p*s_n+sm \geq x$$$, the answer is $$$p*n + i'-1$$$ where $$$i'$$$ is the smallest value that $$$s_{i'} \geq x -p*s_n$$$. You can find $$$i$$$ by segment tree.

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

    link to my submission (obviously upsolved) without using Segment Tree. https://codeforces.me/contest/1490/submission/107636300

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

Easy round, but I found my mistake on G 3 minutes before the end :(

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

Can some one tell me where I am wrong in problem B.

Spoiler

I am just removing the extra part (present count — the equal number of c0,c1,c2 that shud be there) from maximuum of c0,c1,c2 and adding it to next one among them ..and then again removing the extra from that part and adding it to next part. But I ma getting WA on runtime error on tc 2. ples help Thanks in advance.

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

Easy round, but I found my mistake on G 3 minutes before the end :(

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

Bruteforces!!

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

Those who have just started reading Binary Search , they must try to solve problems C , E , G. All 3 of them decent problems to start with.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
if(c2>n/3)
	  {
	  	c0=c0+c2-n/3;
	  	cout<<(c2-n/3)+abs(c0-n/3)<<"\n";
	  }
	  else
	  {
	  	c1=c1-(n/3-c2);
	  	cout<<(n/3-c2)+abs(c1-n/3)<<"\n";
	  }

Why this approach is wrong in B

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

Here’s my attempt to screencast this Div3 contest, where I have explained the solutions to the problems later. It’s my first ever screencast, and any suggestions would be helpful.

https://www.youtube.com/watch?v=fbv5NKA9t9c

I hope you like it.

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

Is this round rated ? as it is showing in unrated contest in my performance graph in profile section

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

I felt that the problems were slightly easier than usual today but really enjoyed the contest! Thanks for the great round.

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

G is a harder version of this problem

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

I uploaded a screencast: https://youtu.be/InbURHKu_Lk

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

Is anyone here who solved F using Binary or ternary search?

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

    yeah, using lower bound and upper bound Solution Link

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

      I liked your approach, not sure if it's really binary search. Actually, I was expecting something similar to this:

      Code

      This code gives WA at case 3.

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

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!

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

Why unordered map gets tle in F?

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

    Because of anti-hash test. In these kind of tests unordered_map takes it's worst case complexity of O(n). You can check this blog on unordered_map.

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

      Thanks a lot for sharing this, TIL. I was completely stumped as to why unordered map didn't work!

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

How to approach problem F if instead of "either zero or C times" we consider "multiple of C times" in the problem statement? (I misread it during the contest).

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

    You can take frequency of frequency of elements as count. Each time just check whether number of elements of that particular frequency * frequency of frequency of elements is max.

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

      I am not sure if you understood what i asked. Or can you please elaborate your approach as to how is this possible without modulo arithmetics by just using frequencies.

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

        F solution. I hope my solution is much clearer. I have just used 2 maps to store frequency of elements and frequency of frequency. The product of this is the number of elements we can have include in our array.

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

          I asked how to solve an alternate version of F viz. "how to solve if we can take all frequencies in a multiple of C times instead of just C times or 0 times", not this! Leave it. Thanks.

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

My F got accepted in 100 ms but 2000 ms after hacking phase. Collision between values is the reason for this because of hash function?

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

good contest

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

Rating got changed again ? Something happened?

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

Hi, Guys! I am stucked on #F on 12 test with time limit. No ideas to fix it. May u help, please?

int t;
    cin >> t;

    while (t--)
    {
        ll n;
        cin >> n;
        vector<ll> a(n);
        unordered_map<ll, ll> m;
        for (auto& x : a)
        {
            cin >> x;
            ++m[x];
        }

        vector<ll> cnts;
        ll sum = 0;
        ll cnts_size = 0;
        for (auto x : m)
        {
            cnts.push_back(x.second);

            sum += x.second;
            ++cnts_size;
        }

        //countSort(cnts);
        sort(cnts.begin(), cnts.end());

        ll c_val = sum - cnts_size *cnts[0];
      
        for (ll i = 1; i < cnts_size; ++i)
        {
       
            if (cnts[i] == cnts[i - 1]) continue;
            ll val = sum - (cnts_size - i) * cnts[i];
            c_val = min(val, c_val);

        } 

        cout << c_val << endl;
        
    }
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why were solutions rejudged on uphacks?