By awoo, history, 6 years ago, translation, In English

Hello Codeforces!

On December 28, 17:05 MSK Educational Codeforces Round 35 will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for Div. 2. It will be held on extented ACM ICPC rules. After the end of the contest you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were prepared by Ivan BledDest Androsov, Vladimir vovuh Petrov, Alexey Perforator Ripinen and me.

Thanks Mike MikeMirzayanov Mirzayanov for great system Polygon!

Good luck to all participants!

We also have a message from our partners, Harbour.Space University:

Hello everyone!

Registration is open for our upcoming 1st Hello India x Russia Programming Bootcamp, with 20 teams signed up and counting, and we are looking forward to seeing you and your teammates in India this March!

More information

Register here

UPD: There will be 7 problems!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 bmerry 7 212
2 uwi 7 216
3 halyavin 7 287
4 hesihesiwujiuwu 7 314
5 voidmax 7 337

Congratulations to the best hackers:

Rank Competitor Hack Count
1 halyavin 328:-26
2 Kilani 107:-6
3 Aemon 91:-33
4 algmyr 57:-4
5 Yazdanra 29:-9

1761 successful hacks and 1237 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A IHaveInt 0:01
B Benq 0:03
C WZYYN 0:06
D PrashantM 0:08
E perchema 0:15
F pekempey 0:38
G chemthan 0:21

UPD2: Editorial is out

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

| Write comment?
»
6 years ago, # |
  Vote: I like it +41 Vote: I do not like it

We are having too many rated contest at the end of 2017. We hope that we'll have such opportunities in coming year! Thanks for organizers and competitors. Good Luck to all.

»
6 years ago, # |
Rev. 2   Vote: I like it +20 Vote: I do not like it

I really like rated Educational Rounds! Thank you guys! Good luck everyone!!

»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +73 Vote: I do not like it

Did you think about Codeforces div 1.5 round — something liek CS academy?

For me it looks as good experiment and chances to make some interesting contest for guys with rating around 2000 ( we can not be at the top of div 1 and can not participe in div 2).

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it +33 Vote: I do not like it

    The idea is really nice! I think here on CF problem sets and groups for which rating is calculated are bound too tight. We could have several groups(Div 1.2, Div 1.4, Div 1.6 etc) competing on same problemset. Currently getting to div.1 you most likely will be back in div.2 after one of next contests. Only Div1+Div2 is ok for 1900-2000 people :)

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

      I think if we have too level in the contests . It is too pressure for writers , and it will be too complex. But I think , If people which rating are in 1900 ~ 2000 can choose to join Div1 or Div2 by itself , It will be great ?

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

        I thought that we can make some only div 2 rounds to be div 1.5. I didn't think about adding one more division on each contest.

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

Again no one thank MikeMirzayanov .

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

35 = 7 x 5 and No of Hours = 2

So, Problems = (7 + 5) / 2 = 6

I wonder why authors mention number of problems! :/

»
6 years ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

Why is nobody thanking MikeMirzayanov

UPD: fixed

»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Does hacking fetches you points in Educational rounds as well?

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

    From the past contests, no.

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

    Nope.

    But you still can rank up by hacking people higher than you. :D

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

      So, is it that the majority of the system tests are from hacks only in Educational rounds?

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

        Yeah, for easier problems it's usually the case

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Guys i will be giving Educational rated round for the first time so i just wanted to ask whether difficulty level of educational rated round is less than Div2, equal to Div2 or greater than it.

»
6 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Another rated Educational Round? I love them. Good luck, guys.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a negative score for a failed hacking attempt in Educational Rounds?.

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

    Hacking doesn't affect your score in any way.

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

      Does it affect our rank?

      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 2   Vote: I like it +9 Vote: I do not like it

        If only you or somebody above you is getting hacked. Like, rank is still determined by number of solved problems and your penalty.

»
6 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Just curious, but with a tight schedule like this, how could system-rejudging process of this round work?

I mean, without any changes, the rejudge (after the hacking phase) will start in 23:05 (UTC+7), right in the middle of the Good Bye 2017.

Two issues may occur due to this:

1 — Rating changes for Div.2 members will be available very late, perhaps even after system tests of GB2017 (wow this is unexpected xD )

2 — As the judging machines have to work with a huge load of submissions from the previous contest, entirely; long waiting queues may be expected...

(I'm quite new here, and I haven't seen any tight schedule like this before. If it had happened, then I guess I've worried too much ;) )

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it +42 Vote: I do not like it
    1. Testing of Educational round (after the end of Goodbye)
    2. Testing of Goodbye round
    3. Rating for Educational (probably somewhere during the testing)
    4. Rating for Goodbye
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It will be better, if it had scoring distribution.

P.S. Sorry for my English.

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

    It is ACM style contest, so problem A worth same as F.

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

      If style has changed, It will be better.

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

        I understand you, but every Codeforces round #X has style like you said and we have enough of them.

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

      When I solve F ... -without knowing that it's ACM style-

»
6 years ago, # |
  Vote: I like it -31 Vote: I do not like it

I like the rated Educational rounds (for Div.2), but this means that for Div.2 coders, there is rarely an unrated round (of suitable difficulty) for us to have a relaxing contest without a lot of stress. Perhaps this could be changed so that only some of the Educationals are rated?

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

    Isn't that what virtual is for?

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

Is it going to be the editorial for this contest?

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

Contest ID — 911. Coincidence? I think not.

»
6 years ago, # |
  Vote: I like it +32 Vote: I do not like it

I've made temporal fix of the CF-Predictor for educational round (calculates rating changes only for div2 participants), so I suppose actual rating change should be close to predicted:)

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Sorry but Mishka sounds like a Girl's Name ..

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

    :(

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

      Atleast Here in India

      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 2   Vote: I like it +6 Vote: I do not like it

        Yeah, I know. I even saw this name as female one in some round here, I believe. In Russia it's some form of name Mikhail (Mike).

»
6 years ago, # |
  Vote: I like it -13 Vote: I do not like it

I officially announce that this contest was shit.

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

    Why is that? :( I think it is educational

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

problem_C

What do you mean by "LIT Garlands "

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

    We have "question to jury" option btw. Right below the problem list in the main page of the contest.

»
6 years ago, # |
  Vote: I like it +22 Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I didn't participated in the round. If I hack someone's solution successfully or unsuccessfully, would it affect my rating?

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

    Hacks don't affect anyone's rating, whether they've participated or not.

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

how to solve D

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

    Inversion number parity always changes whenever you swap two arbitrary elements in a permutation.

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

      thanks.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      Proof?

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

        let x be the total number of inversions before reversing the segment and y be the number of inversions between the range l &r. Then the total no of inversions after reversing the segment wiil be ( x-y+(d*(d-1))/2-y) =(x+(d*(d-1))/2-2*y) where d is the length of segment. Hence parity of inversions does not depend on number of inversions in between the range

»
6 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Contest is now. How to solve D?

Edit: Meant "now over"

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

    swapping any two numbers changes the parity of number of inversions.. so just calc the initial number of inversions and how many pairs are being swapped in every query

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

    The parity of the number of inversions of a composition of two permutations is the sum of the parities of the permutations, mod 2. A permutation that reverses a segment of length d has inversions, hence it suffices to add this after each query and consider the amount mod 2.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone else getting run time error in test 30 of E ?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

"The round is over"

refreshes

"System Testing: 99% Done*

So fast!

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

What is pretest 9 of E?

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What is the test 6 of problem C..?? :|

»
6 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Anyone has any idea regarding the test case 9 of problem E?

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I literally did it .. today and couldn't find the mistake for 1hrs.45min. for the problem C.LOL

if(a==b==c and b==3)
   cout << "YES" << endl;
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    warning: suggest parentheses around comparison in operand of '==' [-Wparentheses] if (N==a==b)

    that's what -Wall, -Wextra etc is for

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to do problem D??

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

    You can count the initial number of inversions (we will call it x thenceforth) through brute force.

    For each query, it is certain that inside the segment, the inverse pair will become non-inverse and vice-versa. Therefore, the oddity of x after each query is decided by the oddity of nC2 (the number of distinct pair in the query's segment).

    If nC2 is odd, then if x was even back then, it will be odd, and vice-versa. Simply because the numbers of non-inverse and inverse pairs are not both odd or both even, therefore, the state of x will be changed.

    Similarly, if nC2 is even, x keeps the same state it was before the query.

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

      "If nC2 is odd, then if x was even back" doesn't the x means the number of inverses back in this segment? And if so then how to calculate inversion for a particular segment online?

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

        x is the number of inverses in the entire array.

        The idea here is to find out if x is odd or even. We don't have to (and in fact, to my experience, cannot within time) calculate the exact value of x.

        P/s: Maybe the ambiguity was caused by the "n" variable. By that I meant r-l+1 in each query actually.

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          inverting a segment [l, r] will inverse all the pairs within it or will change entire array? I am thinking it change only that segment and if so then the extra number we have to add or remove from our count of inversion will depends on the previous value of inversion in [l,r].

          I know i am missing something please correct me!

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

            The pairs within it. It means only (r-l+1)C2 pairs are toggled.

            You don't need to update the permutation though. (well but you do need to update your count on the entire array, modulo 2).

            Let's assume that C = (r-l+1)C2 — the number of pairs in the current segment.

            Each pair among those C pairs are toggled — non-inverse will become inverse and vice versa.

            If we have z as the number of non-inverse pairs before applying the query, therefore we will have (C-z) inversions.

            After the query, as all pairs are toggled, we will have (C-z) non-inverse pairs and z inversions.

            Therefore, the difference of inversion count will be: abs(z - (C-z)) or abs(2*z-C).

            It's easy to see from there that, only the state of C (odd or even) affect the answer in each query.

            If C is even, then the difference will be even. Therefore, the state of the inversion count is unchanged; i.e. if it was odd, then it is still odd — same goes if it was even.

            If C is odd, then the difference will be odd. As a result, the state of the count is changed — from odd to even or from even to odd.

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

              Now it is crystal clear! Thanks a lot mate :)

              Happy new year!

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

                Thanks :) Happy new year to you too ;)

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

              Thanks a lot for the explanation

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

How're you going to start a rated round before calculating rating for previous one?

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

    You can check out this comment.

    Also, since Good Bye 2017 seems to have no rating restrictions (Div.1 and Div.2 users can join equally), then I guess there is no need to calculate rating before this round.

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How to find number of current permutation?

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

    I think you mean inversions, in problem D you could have just done two loops to check for one, and for an better algorithm read this.

    And if by any chance you wanted the number of permutations, there are n! of them and you can read more about them here.

    Or you are trolling (no offence).

    edit : no trolling.

»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

The solution of E is guessable from sample cases..

»
6 years ago, # |
  Vote: I like it +38 Vote: I do not like it

r/UnexpectedFactorial

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Whats the solution for 2B? I tried DP by updating

DP[i]= floor(DP[x]/2), DP[x] = DP[x] — DP[i]

Where x is the index of the maximum element at each iteration but getting WA on T#3

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

    no need to use dp its just a simple math

    int n, a, b;
    cin >> n >> a >> b;
    
    int sm = min(a, b);
    int mxs = max(a, b);
    int ct = 1,mx = 0;
    while (ct < n) {
    	int cx = n - ct;
    	int smc = sm/ct;
    	int mxc = mxs/cx;
    	mx = max(mx,min(smc,mxc));
    	ct++;
    }
    
    cout << mx;
    
    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Can you please explain the logic of these two lines:

      int smc = sm/ct;
      int mxc = mxs/cx;
      
      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it
        i will explain using the second example 
        4 7 10
        ct is number of plates for the smallest cake 
        loop from 1 to n &mdash; 1 as ct
        for first round ct = 1
        then i will put all the smallest cake in 1 plate and the remain plates for the big cake
        its like 7/1 = 7 and 10 / (4 &mdash; 1) = (int)3.333 = 3 
        so 3 is the lowest value 
        do it for ct = 2
        7/2 = (int)3.5 = 3 and 10/(4-2) = 5
        so 3 is the lowest value
        ct = 3
        7/3 = (int)2.3 = 2 and 10 / (4-3) = 10
        so 2 is the lowest value
        ct = 4 = n
        7 / 4 = (int)1.75 = 1 and 10/(4-4) = infinity
        
         
        
        
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I tried to distribute the cakes according to the ratios a/(a+b) and b/(a+b). So the person with more cakes gets more plates to fill and so on. It got hacked. Could anyone please suggest what is wrong in this logic of assigning plates to cakes?

          Here's my code https://ideone.com/cNB2Ly

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

            i generated 1 million testcase and compare with my solution you got tooo many WA for example for this testcases 4 11 18 your output is 5 my output 6 4 13 21 your output is 6 my output 7 4 15 24 your output is 7 my output 8

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

              Thanks a lot for the cases! The issue was not in the logic, but in the implementation. Instead of using the round() function, checking the max of the answers for ceil and floor suffices IMO.

              Here's my final code: https://ideone.com/jeAaa2

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

    Some of the n plates are going to be of type 1 and the others of type 2. If you know how much plates of each type you will have it's easy to get the optimal answer, Then just try every possible distribution of the number of plates, there are only O(n) of them.

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

how to solve E?? Thanks in advance

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

loading...loading...RIP Hacking

»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve F?

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I have a question. Will the rating be updated before GoodBye 2017?I remember the distance between the ending time of this round and the beginning time of GoodBye 2017 is 23.5 hours. When GoodBye 2017 begins, this education round's hacking process haven't ended. Shall we decrease the hacking time of this round or postpone the beginning time of GoodBye 2017 to let us know the rating change before GoodBye 2017?

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

    awoo's words

    1.Testing of Educational round (after the end of Goodbye)

    2.Testing of Goodbye round

    3.Rating for Educational (probably somewhere during the testing)

    4.Rating for Goodbye

    that's the order

»
6 years ago, # |
  Vote: I like it +23 Vote: I do not like it

The problems were very good, especially problem F but I couldn't solve it.

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

    if you understand the solution now then please explain it. It will be a great help :)

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will (un)successful hacking attempt cause increase/decrease in penalty?

»
6 years ago, # |
Rev. 2   Vote: I like it -7 Vote: I do not like it

I 'm sorry for this troubles make. Sorry! See you in Goodbye 2017

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will hacking change the rank list ?

»
6 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Does hacking help in increasing the rank other than the people which is not hacking? Your text to link here...

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

    NO

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

      So why do people waste time on hacking? the fault will eventually occur in system testing

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +32 Vote: I do not like it
        1. You can add your test to system testset;
        2. You can appear at main page of codeforces by getting to top-5 hackers of the contest;
        3. You can have your friends to see that sweet "+k" near your handle in standings;
        4. You can just enjoy it!
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D if the question is modified as :- there will be Q queries and type 1 and 2 type 1 l r — reverse the segment from l to r type 2 l r — give the number of inversions from l to r

Then how would we solve it ? . using a segment tree or something i guess

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

    I am not sure if it can be solved in something under .

    Here is such a problem but with swaps instead of segment reversals.

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

      do that fit time limit?

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

      If n=1500, then we can find all the pairs (i,j) and for each pair we can map it to 1 if inverted else 0, sort it according to j values and build a segment tree of sums out of that. Then, for every l and r we can find effective r' (means how many pairs are there till r) and update (1,r') and effective l' and update (1,l'). In update operation we just invert it (0 if 1, 1 if 0). And the answer will be sum of all nodes in segment tree. Complexity- O(q*log(n*n)) Will this work?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hint on how to solve E ??

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

    When performing the stack sort, you can never push a number onto the stack that is bigger than a number already on the stack, otherwise they will come off the stack out of order. So a successful stack-sort, if it exists will always be: pop the stack until the top is bigger than the front of A (or empty), then pop from A onto the stack. You can simulate that for the first k values to check if it is valid (as in, numbers popped were 1, 2, 3, ... up to some value). Note that the stack will always be sorted (smallest at the top).

    To complete the sequence, suppose that the top of the stack is currently X. A must then contain all missing number less than X before any value greater than X. To get a lexicographically maximal solution, they should appear in A in decreasing order. It's also easy to verify that this will give a valid solution.

»
6 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Is there any way to stop the scoreboard auto-refreshing. It's really annoying when I'm looking at a solution to find a hack, and the scoreboard reloads and I lose what I was looking at.

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

    It's strange it doesn't auto-refresh for me when I open someone's code.

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

How to solve G?

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

    segment tree. but i've tried to solve it by UFS && block_division

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

    Try to solve it with several segment trees :D

  • »
    »
    6 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I've seen two solutions:

    1. O((Q + H)\sqrt{N} + N), where H = 100. Divide the array into blocks of size . For each block and value, store a linked list of all the places that value occurs in that block (in no particular order). To process a query, process the two partial blocks at the ends iteratively, but for the full blocks, just do an O(1) splice of one linked list onto another.

    2. O(QH\log Q + N). Store a segment tree over the updates, where each element in the segment tree is a transition table. At the leaves, an transition table is either the identity (for an "inactive" update) or an identity but with f(x)=y (for an "active" query). The root of the segment tree gives the composition of all the active updates. Now do a sweep through the array, activating updates when reaching l and deactivating them when reaching r, and looking up each a[i] through the root of the segment tree. Composing two transition tables takes O(H) time, so each activation/deactivation takes O(H\log Q) time.

    EDIT: took the big-O times out of maths mode since the images seemed to be broken.

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

    Build a segment tree, where each node has an array to[1...100](to[i] refers to what the number i will become after all modifications on the interval).

    Yet actually, I solved the problem using 100 bitsets(S[1...100]) of length n, where S[i] consists of all appearances of number i. Despite the O(nq) complexity, the constant is so small that I passed all the test cases. 33723537

»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I think Problem D needs N*M big test cases. Some of the programs are obviously O(NM), with constant > 2, which is most likely to be TLE, but we cannot submit that big test cases to hack.

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

    Can you link one of this submissions ?

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

    You can use test generators.

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

      I'm curious: are you using some sort of automated system to download source code for local testing? I can't imagine doing 300+ challenges by hand...

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

        Well, I always fill the hack form by hand (does copy-paste count?). It is as tedious as you can imagine.

        Local testing is the primary source of the challenges. It is a good idea to check the test locally in any case to avoid unsuccessful challenges. Unless it is UB, in which case I use custom invocation tab for checking and tuning the test. I also use Virtual Box for all local testing just in case.

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

          Are you also manually copy-pasting from the solution view into the file you test on locally? Assuming the majority of solutions aren't hackable, then presumably that involves more work than the actual hacks.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve F : Tree Destruction ?

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

    Find a diameter of the tree first, then delete all the points outside the diameter, finally delete the points on it one by one..

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

E is just a simulation problem , why added the "data structure" tag ??

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Got plenty of TLE on G qwq

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

When I first saw problem D, I thought of splay tree.... But then I found that a is equal to -a under modular 2.... Then it was solved under the complexity of O(n+m)...

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can you explain the preprocessing part of your code? How to count initial no. Of inversions

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it +11 Vote: I do not like it

      It's well known that if you want to get the exact number of inversions of a given permutation , you can solve it in no less than O(n log n).

      However ,this problem is only about the parity of the permutation.

      Consider a theorem in linear algebra:If you swap any 2 elements of a permutation ,the parity of the permutation will change.And we know that the permutation "1 2 ... n" is an even permutation.That is, if we swapped C pairs of numbers to make it identity permutation, the parity of the number of inversions is the same as C's.

      Sorry for my terrible English if it does trouble you :D

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C, how to prove 4 2 4 is a valid case ?

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

    ((1,3)(2)(4))for every 4 numbers.

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

      Sorry still don't get it :-( maybe if you can tell me the logic behind your solution please.

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

        Well...The question is to ask whether there exists some residue classes whose union is N_+.

        It's obvious that if S= 1/k_1 + 1/k_2 + 1/k_3 < 1 , then it's impossible to reach the condition.

        May wish to let k_1 <= k_2 <= k_3 , that means, if k_1 > 3 , it's invalid.

        Next, if k_1=3 the only solution is that k_1=k_2=k_3=3 , otherwise S < 1.

        We can easily get the idea that if there exist k_i = 1 , it's always correct.

        Finally we think of the state of k_1 = 2.

        The valid solutions are (2,2,x) and (2,4,4) ,because we can let (x_1,x_2,x_3)=(1,2,x)and(1,2,4) respectively.

        It can be proved that most of the other conditions lead to S < 1 , except for (2,3,3),(2,3,4),(2,3,5),(2,3,6), but we can verify that they are invalid.

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

    We can start the garland with time interval = 2 on an odd number(let's say we start from 1). So according to the problem statement 1,3,5,7,......,2*n + 1 are covered by this garland. With odd time intervals covered, now we need to cover only the garlands that occur at even time intervals.

    Now lets start another garland with time interval = 4 from an even number( say 2). Now this garland covers time interval 2,6,10,14,....4*n — 2. Now we see the only time intervals left are multiples of 4. 4,8,12,....,4*n. Thus starting the next garland with time interval = 4 from 4 will cover all the time intervals. Hence we get the solution.

    Hope this helped!

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

    Take values of k 1,2,3

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

when will we have editorials for this round ??

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

    After hacking phase ends. Maybe along with goodbye 2017.

»
6 years ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

Hi guys. I'm doing hack on prob.E

i used code generator

https://ideone.com/GslUJN

on following two submissions. above code generator seems generating valid input (actually hack results show that "Checker: ok jury and participant have equal answers" in both submission)

http://codeforces.com/contest/911/submission/33736718 http://codeforces.com/contest/911/submission/33726277

But the problem is that in my local environment, above submissions show different output... then, at least one hack should be succeeded. right?

But both hack failed...

is there any problem in my thinking ?

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

    There exist endl at the end of one of them. Remove it or add endl in other one.

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      What i mean different output was "Totally different" (if you execute code, then you will know) not the existence of endl or not... anyway thanks

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem D, I computed the number of pairs being reversed in a range using

(int)ceil(((float)r - l) / 2)

And to get whether this would change the parity of inversions I just mod the above expression by 2.

Can someone point the mistake.

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

    The correct formula to get the number of pairs being reversed in a range is d(d-1)/2, where d is the number of elements you are swapping ( r — l + 1 ). First number can form d-1 pairs, second one d-2, ... , 2 , 1.

»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I don't know if it's already mentioned in the comments, but here's a solution for problem G that is online and can be adapted for arbitrary-sized alphabet:

http://codeforces.com/contest/911/submission/33762818

It uses the Split-Merge Segment Trees chinese trick, where merges amortize to overall O(n * log(n)) complexity. The code is conceptually simple.

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

    Could you sketch how to prove for q merge or split operations? (I only know a proof for (I posted that proof for a similar solution here.).)

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

      If you look at the implementation, you can see that every split/make call creates log(n) nodes and every merge recursion step removes exactly one node, amortizing the total time to O(nlog(n))

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Editorial :/

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It shows testing has finished. But, my solution is still in queue.

»
6 years ago, # |
  Vote: I like it +46 Vote: I do not like it

Regarding to message from system

Your solution 33722462 for the problem 911A significantly coincides with solutions priyanka1998/33722461, priyanka1998/33722462. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties.

Sir as you can see both solution priyanka1998/33722461 and priyanka1998/33722462 were submitted from same user priyanka1998. Sir due to network problem this error occured that when I clicked on submit button same solution submitted twice. I haven't violated any rules.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what the contest will be rated on # of prob. or what ?

»
6 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Excuse me.

I have an inquiry and objection about the system.

At the end of the round, the system said me that "Your solution 33733110 for the problem 911D significantly coincides with solutions physics0523/33732628, physics0523/33733110. "

I just noticed that I may made a little mistake in my program and only repair that,but the system said I did wrong,and change my submission to unofficial.

It is natural that the two submit both I made has some similar points,and,of course,I DO NOT leeking or cheating.

I DO NOT did wrong, I swear!

So,please change my submit official and Rated.

I'm sorry I'm not good at English.

[the full text of the message from the system]
Attention!

Your solution 33733110 for the problem 911D significantly coincides with solutions physics0523/33732628, physics0523/33733110. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties.

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

    Hi physics 0523. Same thing happened to me. "Your solution 33730274 for the problem 911C significantly coincides with solutions aashifkhanate/33729291, aashifkhanate/33730274. "

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I think I just got disqualified using my own solution.

I recieved "Your solution 33730274 for the problem 911C significantly coincides with solutions aashifkhanate/33729291, aashifkhanate/33730274.". I changed the array size from 10^5 to 10^6 which may not be a huge difference to you but I was expanding my guessed solution space for problem C. Please see what's wrong here. Thanks

»
6 years ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

Hi, I've just got disqualified because one of my solution coincides with another user's solution (the message is below).

I want to clarify that I did not see/copy/plagiarize his solution prior writing my own solution. Our algorithms are very similar, but I assure you that's purely coincidental. I don't know what kind of evidence I can give, but I got my solution on my own, not from reading a leakage or something. I never even viewed user sazzach before.

Thank you for you reconsideration.

Attention!

Your solution 33715309 for the problem 911A significantly coincides with solutions sazzach/33713630, hypermassive/33715309. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties.

»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I have been caught in plagiarism with my own solution.

Your solution 33722840 for the problem 911C significantly coincides with solutions sdssudhu/33722503, sdssudhu/33722840.

I resubmitted my solution with some changes as I wasn't sure about my first one and since it was ICPC rules if my first one got AC the second one didn't matter.

Please help.

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Attention! Your solution 33736695 for the problem 911A significantly coincides with solutions HunterYH/33715069, HunterYH/33736695. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. **my English is poor ** You can see both my 33736695 and HunterYH/33715069 and HunterYH/33736695 were submitted from same user HunterYH. I only submit same code twice,because at first I used GNU C++17 Diagnostics it will easy get TLE so I submit same code with GNU C++. I think I haven't violated any rules.

»
6 years ago, # |
Rev. 8   Vote: I like it +4 Vote: I do not like it

Hello Everyone, This morning I got a message from system that my submission http://codeforces.com/contest/911/submission/33725640 during the Educational Codeforces Round 35, has been found significantly similar to http://codeforces.com/contest/911/submission/33725051 and my account may get blocked due to this.

Both of the submissions were made my me for Question C, and i was thinking that the earlier one would be ignored as we have in any normal Round.

I request the community to help me out here. I have attached the screenshots for more details.

Educational Codeforces Round 35 (Rated for Div. 2)

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

    probably, someone blocked problem C in your room and leak your code to another guy :C

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Editorial?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

do we have editorials for educationals. if yes when will they be released??

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

I know administrators are busy and this week is the New Year's Holiday, But please corresponding to the problem(the message from the system) as fast as you can...
Because of this problem,I may will miss to promotion to blue coder... Please change my submission Rated...

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

    My rating should also increase. Please rerate the round. Atleast reply something.

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

      I think so too,I want some reply from administrator quickly...

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hey,do administrators forgot this problem...?

I've not got any replys...

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

    I noticed that my submission changed official andd became blue!! thx!

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am new on codeforces. I have much question about this bootcamp. I am from bangladesh and I am a school student, Read in 0 Level. I want to participate on this bootcamp.but I didn't understand how? is there any school student's allowed?if allowed then I want to go. But I haven't money to pay for this my family isn't have enough money. and most of I haven't any passport and paypal or anything bank account.But I want to participate on this. But How? please Help me? vovuh awoo