Автор PikMike, история, 4 месяца назад, По-русски,

Привет, Codeforces!

В 30.06.2019 17:45 (Московское время) состоится Educational Codeforces Round 67 (рейтинговый для Див. 2).

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир Vovuh Петров, Иван BledDest Андросов и Максим Ne0n25 Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.

Удачи в раунде! Успешных решений!

Поздравляем победителей:

Место Участник Задач решено Штраф
1 Radewoosh 7 220
2 kefaa2 7 346
3 wxhtxdy 6 120
4 square1001 6 136
5 HIR180 6 153

Поздравляем лучших взломщиков:

Место Участник Число взломов
1 2014CAIS01 76:-1
2 prateek2112 50:-1
3 takumi152 32:-2
4 Holland_Pig 28
5 sysjuruo 37:-24
Было сделано 1268 успешных и 1683 неудачных взломов.

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

Задача Участник Штраф
A Geothermal 0:01
B arknave 0:02
C HIR180 0:06
D RUSH_D_CAT 0:22
E Noam527 0:06
F zhoutb 0:28
G Luma 0:46

UPD: Разбор опубликован

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

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

The problems gonna be high-level because it's @PikeMike

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

This group of people have held many educational rounds.Thanks a lot!

And I hope that the problems will be as nice as the past educational rounds'.

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

[DELETED]

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

I'm looking forward to this round, cause I hope to turn blue:) Good luck to you all!

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

Just please prove your solutions :))))

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

I'm hoping to learn something new again in this contest. Because of the last educational round, I learnt the sparse table and binary lifting. Thank you, problem setters for nice educational rounds.

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

Is there any proof why my contribution is negative ? (without your upvote / downvote to this comment)

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

    If a comment has rating between 0 and -5, it's shown that its rating is 0. Your previous comments had rating 0, but maybe they were like -1 or -2 so, after some time, your contribution became -1. I guess that's the reason.

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

      I think this is may be curse of last contest..

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

Do successful hacks add upto your total score?

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

    No,in educational rounds,you can only hack after the round ends for 12 hours.This will not effect your score.

    But if you hack others' solution successfully,and their ranks are higher than yours,your rank may become higher.

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

      But the possibility of that is quite low .. the hack must include a case the testers didnt notice ..
      I think it's for educational purpose only

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

12hrs System test will be like

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

hope to have a contest !!

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

    hope to have a rated contest.

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

      I hope, too. Moreover, it is important that this contest become rated even to prevent the contest from being unrated twice in a row.

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

All the misery was necessary

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

Educational Rounds and PikMike.

Still a better love story than Twilight.
»
4 месяца назад, # |
Rev. 3   Проголосовать: нравится +16 Проголосовать: не нравится

I hope everyone gets what he deserves.

Good luck everyone!

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

When it clashes with India's batting.

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

if( Educational Round == PikMike || Div 3 == Vovuh ){ print("Contest gonna be lit."); }

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

Sure about timings ? :p

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

Hope this one's rated :)

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

I can not believe we do not have that internet issue again ;)

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

The contest start has been delayed for 10 minutes. I think these days so many contests are delayed.

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

Why did the time suddenly extend?

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

What's with all the delays nowadays?

Not to say that I don't appreciate this site, but why not just schedule it 10 minutes later beforehand so we can work on other stuff? Is something unexpected coming up?

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

    Exactly I am yet to take my dinner today. And I delayed it for two hours for contest. If i knew it was 10 mins later then I could have managed taking my dinner as well before contest :(.

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

    They are waiting for 10k registrations.

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

    This 10 minutes is the most boring time of day :3

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

again timming has be changed!!! :((

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

again a delay ? ! great !

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

Finally codeforces scheduled delay takes its place

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

expecting nice problems!!

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

Every contest delayed for 10-15 minute . So , why contest time fixed 10-15 minute earlier rather than starting time ?

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

Delay by 10 minutes and CF rounds! better love story than Twilight :P

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

oh my god!

last contest was delayed too!

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

I wanted to say thanks for not having a delay, after contest :\

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

Delayforces

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

I hope this round is perfect.:)

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

Fantastic!Looking forward to it

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

arisjo hacked pikmike's account and made this contest

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

The contest "codeforced" again.

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

Test case 3

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

If anyone needs help in E question.You can refer to F. Tree with Maximum Cost question. They both are quite similar :)

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

In my opinion, C harder than D and E.

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

    D was definitely harder, it was hacked left and right.

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

    I agree. In my opinion hard ad-hoc problems are always harder than problems that need a general algorithm or paradigm to be solved.

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

What is the 6th testcase for problem C?

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

A and B super easy. C, D, E, F need some "trick". I do not see the educational point.

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

    C, D and E needed some trick? I didn't use a single data structure, well known algorithm or "trick" in them and in fact I think that C and D were quite interesting.

    Edit: fuck my life.

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

      I got an AC with an horrible brute force, I expect this to be hacked. Worked about two hours on it and I have no real idea of how the solution should look like. Thats what I call "you need a trick".

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

    E did not need a "trick" in my opinion, it was an interesting DP on Trees problem.

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

      Maybe E was to hard for me. But, it is obvious that one need to find the "correct" first node. If you see how to find it, you found the trick.

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

What is the approach of Problem E?

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

what the fuck was test case 6 of que 3

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

E is very similar to 1092F - Tree with Maximum Cost. (I know being original is not a priority, I'm just saying in case it benefits some people).

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

    I solved that F problem without any help,but couldn't solve E now...

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

    I did E using sliding through nodes only(Sliding Window??)

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

      I read your solution could you explain in bit detail please.How are you managing window on tree, heard it first time,seems interesting!!

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

        Not actually windowing but if I find answer for any node say, 1 then for its children it will be just addition of a quantity a-b

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

    Oh,I solved it,They are REALLY similar problem... interesting,of course...

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

What is "Unexpected verdict" for hacks?

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

How to solve D?

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

    int n; cin >> n;

    int a[n];
        int b[n];
    
        vsi dp;
        si tmp;
        dp.assign(n, tmp);
    
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            a[i]--;
            dp[a[i]].insert(i);
        }
        for (int i = 0; i < n; i++) {
            cin >> b[i];
            b[i]--;
        }
    
        SegTree st(a);
        bool fl = true;
        for (int i = 0; i < n && fl; i++) {
            if (dp[b[i]].size() != 0) {
                int ind = *(dp[b[i]].begin());
                dp[b[i]].erase(dp[b[i]].begin());
                if(ind == 0){
                    a[ind]=(1<<30);// is not necessary
                    st.update(ind , (1<<30));
                    continue;
                }
                int min = st.rmq(0 , ind-1);
                if(a[min] < a[ind])
                    fl = false;
                else{
                    //update segment tree and with INF value instead of delete
                    a[ind]=(1<<30); // is not necessary
                    st.update(ind , (1<<30));
                }
            } else fl = false;
    
        }
    
        if(fl) cout << "YES\n";
        else cout << "NO\n";
»
4 месяца назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Hacks for C and D?

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

Testcase #6 for C. My approach : all segment of type 1 is increasing order. initial value = 1e7.(value greater than 1000) fill rest in decreasing order staring from 1000. Check if it violates type 0 segment rule. what is the problem?

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

idk how but this code gives me correct output on terminal for test case 1, but I get wrong answer on test case 1 on codeforces, https://codeforces.com/contest/1187/submission/56341353. Can someone please tell me why this is happening, it happened to me so many times before.

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

Hackforces?

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

Problem E, in first test sapmle, why answer is 36? I think i even didn't understand the problem(

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

How to solve C?? what I did was 1st checked whether if there exists an unsorted array b/w some sorted one then answer would be no otherwise yes. To print the array I replaced the non-sorted last index with the min(value int the given range) -1 .. got WA

can anyone provide me the test case(smaller one) where it will be wrong and the correct approach to do it.

code

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

C -> whats wrong with my approach ? My approach : sort all pairs of type 1; take a initial value greater than 1000. for first segment of type 1 fill the segment with increasing value starting from initial value. for each segment except first. if starting point<=ending point of previous segment then do not reset previous value. continue increasing from there.

else if starting point>previous ending point reset to initial value.

fill rest in decreasing order staring from 1000. Check if it violates type 0 segment rule. what is the problem?

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

    Overlapping ranges... I think you need to check every single index, if index and index+1 must be sorted, or must be unsorted. Then you can build the array easyly.

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

      that is great thinking but I thought I handled overlapping segments. For type 1 segments I merged the segments . and for type 0 I checked is they are ok after building the array: 56343410 Can You give me a small hack..please?

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

        You might have ranges like

        1 1 10
        1 2 4
        1 6 12
        

        If you sort for 1, 2, 6, you will loose the 10 while checking if 6 is gt 4. So you decrease the counter on segment (6, 12), which violates rule for segment (1, 10).

        ... But I am not really sure about that... just a guess ;)

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

Today Problem A was a night mare to me . Got AC on 6th attempt.

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

There was DP on tree in E, isn't it?

P.S. Great contest!!!! Wish every contest gonna be like that.

UPD: C dropped

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

Lol what are all the hacks in D?

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

Hack case for D:
1
5
5 4 1 2 3
1 2 3 5 4

answer must be YES

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

HACKFORCES at its best.

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

C. Maybe someone could help me? I don't understand, why my solution didn't work. What criterium to say "NO"? (In my sol I sort all conditions on left bound, connect them(conditions {1 2 5}, {1 3 6} will be {1 2 6}) and build for O(n) answer). Solution.

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

    After you build the array using the "1" facts, loop through all of the "0" facts to see if any of them are sorted.

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

Can anyone tell how to solve B? Tried for like whole contest but Everytime time limit exceeded on test case 4.

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

    Build a pref matrix: matrix[letters][index], then use it to find the least indice that for each letter in the name, matrix[letter][index] >= frequency[letter] in the given string.

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

    First pre-compute the given string by taking a vector of vector of size 26 and insert there indexes . Then for each query make a frequency array for all 26 letters and iterate frequency array and if frequency is not 0 check for the minimum index needed for given frequency in pre-computed array . Here is my solution

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

    Your solution is probably $$$O(N\sum{t_i})$$$. You need to pre-process the string in order to quickly answer the farthest position needed for each name. You can do this by storing the $$$k$$$th occurrence of each letter. Then you just have to use this lookup table to find the answer for each name. Then the runtime is $$$O(N+\sum{t_i})$$$ (plus a constant factor for the size of the alphabet).

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

I am generating a large Test case for hacking for Problem D. I am generating Test cases in which n is of the order of $$${300000}$$$ and $$${t = 1}$$$. But when I try to hack someone it says Test Cases cannot be longer than 256KB. Why it is happening, In question it is mentioned that $$${n}$$$ can go upto $$${300000}$$$. Can anyone Tell me the reason.

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

How to solve D? Some people suggested the answer was to count inversions of each individual number and check those, but then they got hacked.

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

    The key idea is the following: you need to sort subsegments of length 2, i.e. swap pair of consecutive elements if the first one is larger.

    Let's suggest that the element $$$b[1]$$$ is in the position $$$a[pos]$$$. If $$$min(a[1..pos]) < a[pos]$$$ then there is no way to move $$$a[pos]$$$ to $$$a[1]$$$. Otherwise, we can move it and, moreover, relative order of $$$a[1..(pos - 1)]$$$ doesn't change. So we "delete" $$$a[pos]$$$ and $$$b[1]$$$ and solve recursively.

    Of course, you need to write it in an efficient way.

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

      but how can i get index "pos"?? will u pls share yur solution !!

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

        Considering that solution as correct, you can make an array of vector of size 3*(1e5)+1 and store the indices of the input elements inside the vector. That way you can always obtain pos in O(1) time

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

      Consider this : 1 5 3 1 2 4 1 1 2 1 3 4 According to your solution, first element 3 can move to a maximum of 3rd index (consider 1-based indexing). But it can go till 4th index if we swap indexes 4 and 5. Also in that case relative order changes. Answer to this test shall be "YES". If I didn't get your code correctly please elaborate

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

        You should move not $$$a[1] = 3$$$ to the right, but $$$a[2] = b[1] = 1$$$ to the left. Then you get array $$$a = [1, 3, 2, 4, 1]$$$ and $$$b = [1, 2, 1, 3, 4]$$$. Next step is to move $$$a[3] = b[2] = 2$$$ to the position $$$2$$$, $$$a[5] = b[3] = 1$$$ to the position $$$3$$$ and that's all.

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

    Match indices of a to corresponding indices of b (this matching is unique if equal elements aren't reordered). Create an array pos where pos[i] = j means that a[i] is matched to b[j]. Then, if there is some pair (i, j) such that i < j, a[i] < a[j] and pos[i] > pos[j], then the answer is NO. So this gives a necessary condition that no such pairs exist. I didn't prove it's sufficient though :(

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

    Keffa2's solution this might help...

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

    First check that arrays are permutations, and get the map fuction $$$p$$$ such that if the $$$k$$$-th occurrence of value $$$v$$$ in $$$A$$$ is in position $$$i$$$, and the $$$k$$$-th occurrence of value $$$v$$$ in $$$B$$$ is in position $$$j$$$, then $$$p(i) = j$$$.

    Then, instead of "sorting a range", think of your operation as "swapping consecutive elements $$$A_i$$$ and $$$A_{i+1}$$$ if $$$A_i > A_{i+1}$$$", if you can get to an array by sorting ranges, you can also get to it by swapping consecutive elements, like that.

    You can notice that your operation allows you to "remove" already existing inversions, but you definitely can't create new ones. Then, finding a single "new" inversion present in $$$B$$$ is enough to answer NO, and, I haven't proved this yet, but I think that if you don't have any "new" inversion, then you can safely answer YES.

    You can check that you are not creating new inversions by going through the array $$$A$$$, and maintaining a segment tree that answers the maximum in a range.

    The idea is that $$$ST[v]$$$ is the maximum index (in $$$B$$$) in which an already seen value of $$$v$$$ (in $$$A$$$) ends up. When you are at position $$$i$$$, check if there was a previous smaller value $$$v$$$ ($$$v \leq A_i$$$) that ends up after $$$A_i$$$, if this happens, you can already say NO. Otherwise, just update the $$$ST$$$ accordingly.

    The code snippet might be easier to understand:

    for(int i = 0; i < n; ++i){
      int mx = ST.query(0, A[i]);
      if(mx > p[i]){
        ok = false;
        break;
      }
      ST.upd(A[i], p[i]);
    }
    

    You can also check my code: 56332559.

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

      Your claim about inversions can be proven by induction on $$$n$$$, the length of the given arrays. In the step you just have to notice that first $$$n-1$$$ values of the first array, on which we swap adjacent elements, can be sorted in the same way they are sorted in the second array, if we neglect $$$a_n$$$ (the arrays are indexed from 1). That is true by the hypothesis. And now it just remains to somehow deal with the $$$a_n$$$. But it is not hard to prove that it can go to its appropriate position. All you need to do is to notice that if there was an inversion that consists of $$$a_n$$$ in the first array before the change of the order of its first $$$n-1$$$ elements, then the same inversion exists after that change and vice versa.

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

    int n; cin >> n;

    int a[n];
        int b[n];
    
        vsi dp;
        si tmp;
        dp.assign(n, tmp);
    
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            a[i]--;
            dp[a[i]].insert(i);
        }
        for (int i = 0; i < n; i++) {
            cin >> b[i];
            b[i]--;
        }
    
        SegTree st(a);
        bool fl = true;
        for (int i = 0; i < n && fl; i++) {
            if (dp[b[i]].size() != 0) {
                int ind = *(dp[b[i]].begin());
                dp[b[i]].erase(dp[b[i]].begin());
                if(ind == 0){
                    a[ind]=(1<<30);// is not necessary
                    st.update(ind , (1<<30));
                    continue;
                }
                int min = st.rmq(0 , ind-1);
                if(a[min] < a[ind])
                    fl = false;
                else{
                    //update segment tree and with INF value instead of delete
                    a[ind]=(1<<30); // is not necessary
                    st.update(ind , (1<<30));
                }
            } else fl = false;
    
        }
    
        if(fl) cout << "YES\n";
        else cout << "NO\n";
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

56341660 56338689

These submissions are very similar

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

    That's what happen when someone shares his solution with one friend, and don't share it with the other lol

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

please anyone explain B ?

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

So this is what happened today:

  • I solved A, B, C, D, E and was finally about to be master *_*
  • Plot twist 1: 5 mins after the contest, my D got hacked. No master for me :(
  • Plot twist 2: A lot of people had their D hacked. I was going to be a master after all *_*
  • Plot twist 3: My C got hacked. Oops, not going to be a master :(

Requesting all hackers to add another plot twist here (By hacking other people's solutions, not mine :P)

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

    at the end, the editorial get hacked and the contest becomes unrated...

    happy ending for every hacked person :-)

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

    How was the answer for E =36? for 1st testcase?

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

The people who end hacking D starts hacking C. XD

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

    What should be the condition for printing NO in problem C?

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

      An unsorted fact is fully contained in a range that has to be sorted which is the union of overlapping sorted facts. You make the all the sorted ranges were non-decreasing and everything in between decreasing and check if it satisfies the unsorted facts.

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

        Thanks , earlier I was considering that even a partial overlapping will lead to answering NO, Also I have another question. The Problem statement mentions that some range will be sorted and some won't, but if the ranges does not cover the entire array , what can be said about the range which is not covered in the queries. Should that be sorted or unsorted. eg:- if array size is 6 and the ranges are (1-indexed) 3-4 4-6 what about 1-2 ?

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

          Make them anything you want, it doesn't matter. You could just make anything outside of a sorted range unsorted so that you satisfy as many unsorted facts as possible, and then check if all the unsatisfied facts are true. If one of the facts aren't true, there's no solution since you're already making as much of the array unsorted as possible.

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

simple test hack for D -_-:

1 3 3 2 1 1 3 2

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

Before start hacking, the number of a test case of Problem D was 18, and there are 74 now. :O

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

Many people have been hacked on D, including me.. We should use data structure to solve.

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

Any hint for F?

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

    Answer is $$$E[(1+\sum_{i = 1}^{i = n-1}(x_{i} != x_{i+1}))^2]$$$ = $$$E[(1 + \sum_{i=1}^{i=n-1}(x_{i} != x_{i+1})^{2} + 2\times \sum_{i=1}^{i=n-1}(x_{i} != x_{i+1}) + 2 \times \sum_{i!=j}(x_{i} != x_{i+1})(x_{j} != x_{j+1})]$$$.
    Now use linearity of expectations to calculate it.

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

shrpy

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

Can anyone explain the idea of Problem F ?
Thanks in advance.

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

C and D — R.I.P. It's gonna be very nice system testing))0)

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

Do upvotes increase contribution points? If yes, can I get some upvotes just to get some contribution points? I currently have none :(

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

After system testing no one has solved problem D ^^

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

why so many hacks on C? whats the tc?

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

what is the hack in C? so many purples have been hacked

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

Wow, more than 600 solutions on problem D passed on pretests and now it's only slightly more than a 100. What's so wrong with this problem, did everyone try to do something greedy? My solution is stupid, what could possibly go wrong.

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

I was rank bout 200 at the end of contest.But now,I am rank74. That's hackforces.

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

This round's D will like this problem,which has 588 tests

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

7 7 2 3 6 5 4 1 1 2 3 6 4 5 7

problem D, i excute some ac codes, result is YES, and unsuccessful hack

anyone can help explain? i think it is NO.

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

    Apply the operation to [5, 6] to swap them, [1, 2], [2, 3], [3, 4]... to move 7 to the end, and [5, 6], [4, 5], [3, 4]... to move 1 to the beginning. (numbers in brackets are indices, 1 indexed)

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

    7 7 2 3 6 5 4 1 1 2 3 6 4 5 7

    first sort [5,4,1] then it'll be 7 2 3 6 1 4 5 then [7,2,3,6,1] it'll be 1 2 3 6 7 4 5 then [7,4,5] it'll be 1 2 3 6 4 5 7 which is equal to B

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

Weak test cases for C and D

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

How to solve B? I think I have overcomplicated using the precomputation and binary search.

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

Okay, so I think you gave such weak tests on purpose.

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

Another 2 solve contest lol im gonnna drink some beer

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

When you go from -65 to -13

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

What is the idea behind C?

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

    Greedy. Lets make unsorted all the subarrays that don't required to be sorted. Note that if we have to intervals $$$[i_1,i_2]$$$ and $$$[j_1,j_2]$$$ that needs to be sorted, and if $$$i_2 >= j_1$$$ then the interval $$$[i_1,j_2]$$$ needs to be sorted as well. So lets find all actual intervals that needs to be sorted using the rule above. Suppose that those intervals are $$$[l_1, r_1],[l_2, r_2],...,[l_k, r_k]$$$. We can fill in them starting from the first one by assigning the $$$n$$$ to all the positions within the $$$[l_1, r_1]$$$, $$$n-1$$$ within the $$$[l_2, r_2]$$$ and so on. Finally check wherther all condition with $$$t==0$$$ holds. If not, there is no answer, otherwise you have already found one.
    It may seem that we need to fill in the segmends between sorted intervals somehow but actually they can be handled as a sorted intervals with length 1.

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      • Thank You But How we fill other that sorted intervals?
      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Imagine that we need to produce an unsorted array of length 4. Its clear that intervals $$$[1;1],[2;2],[3;3],[4;4]$$$ needs to be sorted (yep, array of length 1 is allways sorted, but the goal is to see how the algorithm above will handle them). If we run an algo on this intervals we will get the following array: $$$[4,3,2,1]$$$. As you can see, all the subarrays of this array with $$$length > 1$$$ are unsorted.

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

    I use the Disjoint set to make the interval of sorted, then i test the unsorted case in it.

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

problems are good,but pretests are too weak

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

Hey PikMike, Editorials please !!

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

whats wrong in my code????? please someone tell me...

include <bits/stdc++.h>

using namespace std;

int main() { int t; cin>>t; string str; getline(cin,str); int n; cin>>n; string p; getline(cin,p); vector a(t); for(int j=0;j<n;j++) {for(int k=0;k<t;k++) { if(p[j] == str[k]) {a.push_back(k); } }} double max = *max_element(a.begin(), a.end()); cout<<"Max value: "<<max<<endl;

return 0;

}

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

What is the logic of D?

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

Is there any simple solution for D which does not use segment tree?

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

Could someone check out my submission and tell me what do the diagnostics mean. I am not able to interpret it. Submission no — 56381811 Thanks in advance.

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

    The actual error is:

    Error: attempt to subscript container with out-of-bounds index 161, but container only holds 161 elements

    This is saying that you are trying to access element number 161 in a container (a vector, I think) that contains only 161 elements. This is an error because, in such a vector, the elements are numbered from 0 to 160.

    Looking at your code this might be in merge(), where you index with j+1:

                 for(;j<one.size();j++){
                      if(one[j+1].first <= one[j].second)
    
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

for(int i=0;i<n;i++) { cout << cur << " \n"[i==n-1]; cur+=arr[i]; } can someone explain [i==n-1]; in above and for (i = 0; i < n; i++) cc[i] = (i % 2 == 0) == (s[i] == '(') ? '0' : '1' what does that == after (i%2==0) does?

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    • " \n"[i==n-1] is a way to print a space when i<n-1 and a newline for i==n-1, because " \n" is a string with two characters : " \n"[0] is ' ' and " \n"[1] is '\n'
    • the "==" tests if both conditions have the same result, so (i % 2 == 0) == (s[i] == '(') is equivalent to ((i % 2 == 0) && (s[i] == '(')) || ((i % 2 != 0) && (s[i] != '('))
»
4 месяца назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

So where is the Editorials?

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

Was not able to solve any question but will try next time Wish me luck

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

Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).

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

In problem C, for sorted subarrays, most of the solutions are doing +1 for L[i] to R[i] — 1. Why not L[i] to R[i]? Why is R[i] not being taken into consideration?

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

Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).

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

It would be so helpful if we could get a brief tutorial/solution guide.. :)