MikeMirzayanov's blog

Codeforces Round #116
By MikeMirzayanov, 13 years ago, translation, In English

Hello!

Today it will be good old ACM-ICPC round. Yes, it will be the rated event for the second division, and the participants of the first division will be able to participate out of competition.

Problems have been prepared by Nerevar, natalia, MikeMirzayanov and Edvard, and Delinur translated all the problems. Thanks!

Good luck!

UPD: Ratings will be updated later. Sorry for delay.

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

Comments Comments (33)
| Write comment?
»
13 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Hello.

I'm almost new here, and I'm wondering what the "ACM-ICPC Rules" will be like. I am thinking that, in this round, when we submit our source code, we will be told the results of all tests, not only ones of pretest, and there will be no Hacks. Is this right?

→ Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

More information about contest please !!!

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

Why binary search tag is added to problem E? http://mirror.codeforces.com/problemset/problem/180/E

I solved it in O(n + m) and I no see any place to use binary search.

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

    Are you sure?But the tag now is "two points".

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

      Tag was previously different :) Now, its corrected.

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

    Binary search is one of the intuitive method to solve the problem. You didn't use it doesn't mean it's wrong.

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

    This problem can solve by DP sliding window too.. :)

    → Reply
»
13 years ago, # |
  Vote: I like it +2 Vote: I do not like it

When will it be rated?

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

How can this be? Some of submissions are quite similar but are written by different people. for example submission number 1609559 and submission number 1609912 for problem E.

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

    It shouldn't be. Admins should take a look at that. If you dig a bit deeper you might notice that the people placed #7, #11, #12, #14, #18, #19 have matching solutions (at least for some problems). They all come from the same city, so I suppose they participated together.

    In general: I have no problem with people joining the contest together (not sure if that would be against the rules) but simply copying solutions is very dishonest towards all other contestants. I don't even see the purpose of cheating here. Do people get an ego boost if they get an increased rating based on somebody else's solution they submitted?

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

      Will this round be unrated ? :/

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

        Probably after update rating, cheaters will be removed :)

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

        I think the ratings have been updated but are not displayed...Take a look at the cheaters profiles...They are all Blue now and this was their first contest..So I guess the ratings have been updated .VNBZTY and Liu_Ts

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

      "but simply copying solutions is very dishonest towards all other contestants."

      I agree this. If some people copied their solution one another and get high ranks together, the position of other people would be lower, and their rating would be lower.

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

    I think both VNBZTY and Liu_Ts are the same people..They submitted the same codes to all the problems(even the variable names and their initial values are same) , solved each problem in exactly the same language and always VNBZTY submitted the code and if it was accepted then within 10 minutes Liu_Ts submitted it...So much cannot be mere coincidence. Take a look at their submissions and compare it ..VNBZTY submissions , Liu_Ts submissions

    → Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it -6 Vote: I do not like it

    Administrator will accept it to first user after finishing contest but in it contest it will accept to both users.

    → Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, I am really new here and I want to know whether there is problem set analysis about codeforces round here or where can I find them ?

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

    After publishing editorial author's usually put the link in the blog page. For some strange reason codeforces is not interested to put links of all editorials on a single page,so iman_MC made this page: http://mirror.codeforces.com/blog/entry/1492, here you can find editorials of previous rounds.

    → Reply
»
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it

No matter how late it will be, will ratings definitely be updated?

→ Reply
»
13 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

What is the meaning of UPD? We can see this in every contests in Codeforces.But I can't understand what this means.

→ Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody tell me how to solve problem E?

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

    So here is a simple solution: I maintained an array of vectors vector arr[] where arr[i] contained the array of different paints between any two consecutive i. Therefore arr[i] would be empty if the string had no or just one element of the type. If inp= 1 2 3 1 2 3 5 1 1 then arr[1]= 2 3 0 Then, I iterated through all the array of vectors to find the maximum number of consecutive elements that sum to <=k. This is the code for the later part

    for(int i=1;i<100001;i++)
  {
    if(v[i].size()==0)continue;
    int back=0;
    int front=0;
    int sum=0;
    bool frontmoved=true;
    bool backmoved=false;
    while(front!=v[i].size())
    {
      if(frontmoved)
	sum+=v[i][front];
      if(backmoved)
	sum-=v[i][back-1];
      if(sum<=k)
      {
	if(max<front-back+2)max=front-back+2;
	front++;
	frontmoved=true;
	backmoved=false;
      }
      else
      {back++;backmoved=true;frontmoved=false;}
      if(front<back)
      {front++;frontmoved=true;}
    }
  }
    → Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there problem analysis for this round?

→ Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

More than 20 hour passed now, when will the rating update?!

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

    Be patient, maybe they ( or the server) are busy now. The main reason you are here because you want to practice more, not to get high score to be contemplated :)

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I would be greatful if someone would provide me a detailed explaination of this source. Also , any other thoughts about problem B would be very helpful. Thanks ! :)

→ Reply