Connector's blog

Codeforces Beta Round #75
By Connector, 14 years ago, translation, In English

Hello everyone.

Today I am an author of the contest. This round is for both divisions. There will be five problems in each division. This is my second round on the Codeforces. The actors in this contest will be walruses again =)

I want to thank Codeforces and Alias for helping me to prepare the round.

Good luck!

UPD1:

Points for problems in div1: 500-1000-1500-2500-2500

Points for problems in div2: 500-1000-1500-2000-2500

Analysis 

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

Comments Comments (64)
| Write comment?
14 years ago, # |
  Vote: I like it +4 Vote: I do not like it
There is, in total,10 problems? Or is it 7 problems with the regular style -> (1 2 (3 4 5) 6 7)?
→ Reply
14 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

Codeforces Beta Round #64
By Connector, 3 months ago
if you wan't to see the problems by the same auther click here

→ Reply
14 years ago, # |
  Vote: I like it +23 Vote: I do not like it
Could you please start system testing?
→ Reply
14 years ago, # |
← Rev. 2   Vote: I like it +38 Vote: I do not like it

The statements are easy to understand, I like this :d.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Div2 Problem C: system test is weak?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    What makes you say that? Any test that you think should be there and it isn't?
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Why you think so?
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it
      Because my solution is accepted :)

      After I locked C problem. Trying to hack my solution, and my solution got TLE. And I using that test and hacked 5 other coder`s solution. (Therefore test is suitable)

      But my solution is accepted in final test.
      → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can any one explain the logic behind Problem D Div2 ? And the order in which it can be solved ? 

→ Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    O(nlog(n))   :(
    1.Sort the numbers and (in a pair store their index as well, it will be used later).
    2.Now scan the sorted array, and while going right keep calculating maxIndex till now. 
    Store the difference between maxIndex and the current element's index.(if positive).
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      I got AC, after the systest was over.
      This is the fifth time my ratings will go down.
      :)
      → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I call m[i] is minimum a[i], a[i+1],..., a[n]. I use binary search on m[] to find result. It 's very easy to code.
      → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I didn't had the chance to try it, but looks like some sort of inversion count variant. I would suggest that you wait till the editorials are up. :)
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      Yes my solution is using BIT, similar to inversion count but I search for maximum value here..
      → Reply
14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
damn i wrote the code for D  i just clicked submit n time got over :-( bad luck  :-( 
→ Reply
14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Ratings got updated for DIV-2 ??

→ Reply
14 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

Interesting contest.

Kind of guessed the answer in C and was pretty close in D.

I'm waiting for the editorial, especially for the proofs of C and D.
→ Reply
14 years ago, # |
  Vote: I like it +14 Vote: I do not like it
Div-1 problem D
bool used[10000]; //on the contest RE 10
bool used[100000]; //after the contest AC


→ Reply
  • 14 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it
    Why not vector?
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it
      Sometimes it's slow.
      → Reply
    • 14 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      vector<bool> used(10000,0);
      So what? %)
      I'll better consider something like: 
      #define SIZ 100000
      And, of course, after that I have to consider C# or Java as a first language. At least they will fail on the local testing. (C++ is such a badass language that even 90000 out of the bounds call didn't fail on the local testing).
      → Reply
      • 14 years ago, # ^ |
        ← Rev. 2   Vote: I like it +6 Vote: I do not like it

        No
        vector <bool> used(n);
        vector under MSVS debug mode will also throw RTE if accessed out of bounds
        → Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
       
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am very suprised.In problem B,div2,I use string always got RE on pretest 2,but I  use char got AC,why??whether it is relative to the head files,I type #include<string.h> and #include <string>

→ Reply
14 years ago, # |
  Vote: I like it +26 Vote: I do not like it
I passed problem E with time 4920ms ... Lucky guy I am, right~?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Ofcourse you are lucky , Every-one. (atleast me ,) dreams of such a day.
    But I think I need to wait 2 more years for div1 E aand that too with such timing .
    → Reply
14 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Nice Contest and well framed , short and crisp problem statement
→ Reply
14 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Thanks for the contest! The problems were excellent, varied, the statements were very clear, and I'm very curious about the problems that I didn't solve, which is the way it should be :)

BTW, I thought that more people would implement a brute-force approach in Div1 A (maybe they did in Div2 C). It looked like a good hack target but I only managed to find three slow solutions in my room.

Waiting for the editorial :)

→ Reply
14 years ago, # |
  Vote: I like it +8 Vote: I do not like it
Good contest!

For problem B, I have read the statement twice and ask 2 questions then understand it.
I don't think this statement is so clear, but others is really clear.
 
For problem C, it's a little bit unusual.
But if you know some connections between graph and linear algebra then it will be really easy.

For problem E:
Is someone solved it by divide the people into groups?
1.Prepare: for each group, calc all important time and at that time who is the best.
Cost time O(BA2logA) where A is the amount of people in a group, B is the amount of groups.
2.Query: for the groups by binary search, and combine the left-most and right-most single ones.
Cost time O(Q(B+A)logA).
For A = B = sqrt(Q):
The time complexity is O(N1.5logN).
But I can't pass.


→ Reply
  • 14 years ago, # ^ |
    ← Rev. 4   Vote: I like it +8 Vote: I do not like it

    I haven't got time to implement the following idea.
    Use offline method to handle queries, the binary search won't be necessary.
    sort all queries by time, and insert them into "groups", for each group, the time is sorted and some linear scanning may work.
    still lots of minor things had to be considered to achieve O(n^1.5) complexity, and this solution may result MLE with a poor implementation.
    → Reply
14 years ago, # |
  Vote: I like it +6 Vote: I do not like it
I forgot to use stable_sort and I did not know that I could sort with pairs, or I could pass Div I B in 12 minutes :(
Anyway, learning is always happy:)
→ Reply
14 years ago, # |
  Vote: I like it +32 Vote: I do not like it
I think that you should improve hacking interface. It is very slow and sometimes didn't open properly (I had to open some solutions for several times, before I could see the source). Also when I was reading somebody's code I got some strange messsage about reading the solution for too long and the hacking window closed.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Also the option to upload testcase in plain text format should be added(or is it already possible?)
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I don't think it should... uploading large files would put a bigger strain on the server (connection, actually) even than the hassle to compile and run the test generator. This option is missing for a purpose.
      → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Anyone for Div-2 E explanation .... plz
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Wow, this is a really fun contest! Too bad I missed it :(

Does anyone know when is the next contest?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I don't know but I think that next contest will start next week. But I hope that administration prepare and start contest, for example, in Saturday evening.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      TCO Round 2 on Saturday evening
      → Reply
      • 14 years ago, # ^ |
        ← Rev. 3   Vote: I like it +1 Vote: I do not like it

        Нда, точно... это нужно еще дождаться пока кто-то не подготовит раунд... и выбрать подходящее время.

        P.S. не подумал про TopCoder поскольку не участвую в их отборочных раундах.
        → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
as for the Ski Base,I don't understand the analysis of it,I can't clearly understand why the solution is correct.Can anyone explain to me? Thank you 
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Every graph with even degree for all of its vertices is a sky base. If you don't know why, then study Eulerian circuits. So we are counting sub-graphs with all vertices having even degree. Consider a spanning tree for each of the components of the graph. All other edges not in the spanning tree have two possibilities for existence. And the existence of edges in the spanning tree is determined uniquely after that. So every time we add an edge to a component the number of even degree sub-graphs is doubled. But when we connect two of the components the answer doesn't change (Why?).
    Hope it helps, sorry for bad English.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I need clarification for problem E(div 2). Specially i m very much confused about the paragraph

"Let's consider the ski base as a non-empty set of roads that can be divided into one or more tracks so that exactly one track went along each road of the chosen set. Besides, each track can consist only of roads from the chosen set. Ski base doesn't have to be connected."

What is meant by this paragraph......................


→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I could not understand the editorial of problem C in div 2 and A in div 1 related to newspaper headline and why it is tagged as binary search and how the solution could be implemented as binary search. I doubted on whether somebody will read it or not but just want to say that please provide more explanation in editorials rather than providing few lines, although a problem could be easy for good coders but for beginner it is the ladder, so please don't make it difficult to climb.
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 4   Vote: I like it +1 Vote: I do not like it

    See Burunduk1's code , it is very clear.
    suppose the target word is abcd, 
    Then in the source word , first search for a then search for b , but don't start search from start, instead search from the position you last found the matching character that is a in this case.
    Why we are doing this :: Because we don't want to take new headline unnecessarily .
    By checking whether we can find b next-to where we found a , we can save 1 headline-expense. If b is not found next(next does not necessarily mean adjacant) to a . We will have to use another headline. So, then search the source string(that is the headline),from start for b. Doing this again and again will provide you how many headlines you need. But this is SO costly. Every time you will have to search for a character in O(n) time. So, you see, this is very costly , given such constraints. So, we use binary search. We binary search for the next position where the next character to be searched is located. Suppose a was found at 5th   position, now we want to find b, nearer to 5th position but on the right side.
    How do we do this::
    Do pre-processing, store all b's location in a array.
    Then binary search for 6 , if there is position greater than equal to 6 . that should be our next b's position. If no b is found after 5th position ::
    Take new headline. :( 
    Doing this for all characters , will produce the answer.

    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Thanks for explaining how binary search is implemented in this problem, but I could not understand the portion related to binary search of Burunduk1's code.
      I have added few lines to understand what is going on on test case 2 of the example (abcd,dabc)....
      forn(i, tn)
        {
          vi &v = pos[t[i] - 'a'];  
      // v[3]=3 for 'd'
          int j = lower_bound(all(v), p) - v.begin();
      // can't understand.             have read about lower_bound.but how p=0 will find 3 in vector
          printf("%d\t%d\n", j,p);  
          if (j >= sz(v))            
            cnt++, p = v[0] + 1;
          else
            p = v[j] + 1;
        }
        printf("%d\n", cnt);

      and I got this as the output:
      0    0
      1    4
      0    1
      0    2
      2
       could you please explain me little bit more as I am unable to correlate the output to the input with the help of code?
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        "but how p=0 will find 3 in vector"

        lower_bound finds next integer that is greater than or equal to supplied one. (here 0).
        ---------------------------------------
        if source string is abcd.
        then v for d's case will be {3} since the only d is at 3.
        and lower_bound will return that.


        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Thanks for correcting me. Now I still have 2 doubts.
          1. If the target is "dabc" and source is "abcd", then after 'd' p=4, so for target: 'a': v[0]=0; then how p=4 in lower_bound will give j=1?
          2. What I have learned from Top coder algorithm tutorial and recipes is that to use binary search there should be predicate which is true for some interval and false for other interval. so we continuously divide the search space until found the correct one. But in this case we are maintaining separate container for every alphabet in source and storing its position. then we are applying steps you mentioned but how this is binary search? How have we divided the search space?

          Lastly could you refer me more problem like this for practice.
          → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            1. When  'd' is found .
            p becomes 4.
            Then in vector v for 'a'. there is no such 'a' with position >= 4. So, p will now change to 0.[new headline required] (it will not go into if part , it goes to else part.)

            2.See, you got a sorted sequence of numbers. All you required is to find, a number which is "just" greater than or equal to some number say x.
            Take a example instead,
            1,2,3,4,4,5,5,6,7,8.
            can you find 4 using binary search.
            it is pretty simple.
            (I will leave it for you)
            hint:: search in last ,if greater search in-between first and last , if smaller search between....so on and so forth...

            Lastly, there are lots of problem on binary search , here and at topcoder.
            Use Google (and the word "archive")  
            → Reply
            • 13 years ago, # ^ |
                Vote: I like it +5 Vote: I do not like it
              http://www.cplusplus.com/reference/algorithm/lower_bound/ see::binary search code for lower bound. This site is very helpful. My doctor told me to see this five times a day. :)
              → Reply
            • 13 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              Thanks a lot for clearing lot of things but my doubt still persists. Let me rephrase the question.

              1. "how p=4 in lower_bound will give j=1?"
              for case 'a', vector v[0]=0 has only 1 element whose index or position is 0, which is represented by j. but then how j is giving value 1?

              All the vectors in this case are maintaining only single element then j must be 0 for all the cases. So why it is giving 1 in case of 'a'.

              2. if (j >= sz(v))   cnt++, p = v[0] + 1;

              this part of code is incrementing cnt or new headline and if p reaches end of the sorted values in vector then starting once again it from beginning. and

              else
                    p = v[j] + 1;

              this part is putting next value in sorted array of vector v in p.

              So where are we dividing the search space? I suppose we are only iterating in the vector.

              Likewise you mentioned in binary search we first search middle value then look at whether to search in [mid+1,high] or [low,mid+1], then further divide. but in this case how it is binary search.

              → Reply
              • 13 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it
                1.j becomes 1 , because it reached the end of the list while searching for 4.
                (v.end() - v.begin() = 1)
                2.We are not doing binary search either in "if" or "else" part.
                rather the function lower_bound is doing binary search.[See c++ code of lower_bound]
                --------------------------------------
                → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

D was a bit tricky. Spent lot of time in debugging.

→ Reply