By PikMike, history, 8 months 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 0n25 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 HS432 7 314
5 voidmax 7 337

Congratulations to the best hackers:

Rank Competitor Hack Count
1 halyavin 328:-26
2 Mohammad_kilani 107:-6
3 Aemon 91:-33
4 algmyr 57:-4
5 Yazdan_ra 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 Delsin 0:01
B Benq 0:03
C DTSBT 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  

»
8 months 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.

»
8 months 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!!

»
8 months ago, # |
  Vote: I like it +9 Vote: I do not like it

»
8 months 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).

  • »
    »
    8 months 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 :)

    • »
      »
      »
      8 months 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 ?

      • »
        »
        »
        »
        8 months 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.

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          If we make some div.2 be div1.5 , Those rating are too low to join it will what to be ?

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

Again no one thank MikeMirzayanov .

»
8 months 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! :/

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

Why is nobody thanking MikeMirzayanov

UPD: fixed

»
8 months ago, # |
  Vote: I like it +2 Vote: I do not like it
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

someone please send link to register for this contest

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

I think the best contest in those three rated contests will Good Bye 2017 but this educational contest is interesting too. I got excited when i remembered this contest.

»
8 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Does hacking fetches you points in Educational rounds as well?

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

    From the past contests, no.

  • »
    »
    8 months 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

    • »
      »
      »
      8 months 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?

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

        Yeah, for easier problems it's usually the case

»
8 months 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.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Difficulty is the same as Div2 problems

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

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

»
8 months 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?.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hacking doesn't affect your score in any way.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Does it affect our rank?

      • »
        »
        »
        »
        8 months 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.

»
8 months 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 ;) )

  • »
    »
    8 months 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
»
8 months 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.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If style has changed, It will be better.

      • »
        »
        »
        »
        8 months 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.

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

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

»
8 months 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?

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

    Isn't that what virtual is for?

»
8 months ago, # |
  Vote: I like it -18 Vote: I do not like it

you better make me blue again or i will send my gang to your abandoned shack of HQs you scums

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

Is it going to be the editorial for this contest?

»
8 months ago, # |
Rev. 5   Vote: I like it -8 Vote: I do not like it

Before every educational round I feel like :

»
8 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Contest ID — 911. Coincidence? I think not.

»
8 months 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:)

»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    :(

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

      Atleast Here in India

      • »
        »
        »
        »
        8 months 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).

»
8 months ago, # |
  Vote: I like it -13 Vote: I do not like it

I officially announce that this contest was shit.

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

    Why is that? :( I think it is educational

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

problem_C

What do you mean by "LIT Garlands "

»
8 months ago, # |
  Vote: I like it +22 Vote: I do not like it

»
8 months 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?

  • »
    »
    8 months 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.

»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

how to solve D

  • »
    »
    8 months 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.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks.

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

      Proof?

      • »
        »
        »
        »
        8 months 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

»
8 months 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"

  • »
    »
    8 months 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

  • »
    »
    8 months 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.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

"The round is over"

refreshes

"System Testing: 99% Done*

So fast!

»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

What is pretest 9 of E?

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

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

»
8 months 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?

»
8 months ago, # |
  Vote: I like it -26 Vote: I do not like it

»
8 months 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;
  • »
    »
    8 months 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

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes.. learnt a lesson . Also I should've moved forward.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to do problem D??

  • »
    »
    8 months 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.

    • »
      »
      »
      8 months 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?

      • »
        »
        »
        »
        8 months 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.

        • »
          »
          »
          »
          »
          8 months 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!

          • »
            »
            »
            »
            »
            »
            8 months 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.

            • »
              »
              »
              »
              »
              »
              »
              8 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

              Happy new year!

              • »
                »
                »
                »
                »
                »
                »
                »
                8 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Thanks :) Happy new year to you too ;)

            • »
              »
              »
              »
              »
              »
              »
              8 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thanks a lot for the explanation

»
8 months 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?

  • »
    »
    8 months 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.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That's an option. I thought, may be they'll cut hacking time and wanted to get the official answer.

      Thanks

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

How to find number of current permutation?

  • »
    »
    8 months 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.

»
8 months ago, # |
  Vote: I like it +7 Vote: I do not like it

The solution of E is guessable from sample cases..

»
8 months ago, # |
  Vote: I like it +38 Vote: I do not like it

r/UnexpectedFactorial

»
8 months 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

  • »
    »
    8 months 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;
    
    • »
      »
      »
      8 months 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;
      
      • »
        »
        »
        »
        8 months 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
        
         
        
        
        • »
          »
          »
          »
          »
          8 months 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

          • »
            »
            »
            »
            »
            »
            8 months 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

            • »
              »
              »
              »
              »
              »
              »
              8 months 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

  • »
    »
    8 months 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.

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

how to solve E?? Thanks in advance

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

loading...loading...RIP Hacking

»
8 months ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve F?

»
8 months 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?

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

    PikMike'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

»
8 months 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.

  • »
    »
    8 months 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 :)

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 months 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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Will hacking change the rank list ?

»
8 months 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...

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    NO

    • »
      »
      »
      8 months 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

      • »
        »
        »
        »
        8 months 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!
»
8 months 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

  • »
    »
    8 months 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.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      do that fit time limit?

    • »
      »
      »
      8 months 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?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hint on how to solve E ??

  • »
    »
    8 months 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.

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

      Thanx a ton !! can u mention the specific algo/DS to solve problem G ?

»
8 months 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.

  • »
    »
    8 months 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.

»
8 months ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve G?

  • »
    »
    8 months 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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try to solve it with several segment trees :D

  • »
    »
    8 months 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.

  • »
    »
    8 months 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

»
8 months 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.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you link one of this submissions ?

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

    You can use test generators.

    • »
      »
      »
      8 months 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...

      • »
        »
        »
        »
        8 months 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.

        • »
          »
          »
          »
          »
          8 months 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.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve F : Tree Destruction ?

  • »
    »
    8 months 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..

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Got plenty of TLE on G qwq

»
8 months 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)...

  • »
    »
    8 months 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

    • »
      »
      »
      8 months 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

»
8 months 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 ?

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

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

    • »
      »
      »
      8 months 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.

      • »
        »
        »
        »
        8 months 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.

  • »
    »
    8 months 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!

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Take values of k 1,2,3

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

when will we have editorials for this round ??

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    After hacking phase ends. Maybe along with goodbye 2017.

»
8 months 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 ?

  • »
    »
    8 months 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.

    • »
      »
      »
      8 months 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

»
8 months 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.

  • »
    »
    8 months 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.

»
8 months 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.

  • »
    »
    8 months 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.).)

    • »
      »
      »
      8 months 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))

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Editorial :/

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 months 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.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 months 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.

  • »
    »
    8 months 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. "

»
8 months 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

»
8 months 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.

»
8 months 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.

»
8 months 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.

»
8 months 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)

  • »
    »
    8 months 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

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Editorial?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 months 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??

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 months 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...

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

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

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Hey,do administrators forgot this problem...?

I've not got any replys...

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
7 months 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 PikMike