Gerald's blog

Codeforces Beta Round #88
By Gerald, 13 years ago, translation, In English

Hello everybody! My name is Gerald Agapov. I study at Saratov State University. Today I present you the set of, I hope interesting, problems. Good luck to all!

And also a warm thanks RAD,  MikeMirzayanov and the entire Codeforces team for the great system and this opportunity! (с) dolphinigle

UPD. 

The match has ended. Thank you for paticipating!

Top 5 Coders:
5. kelvin

Announcement of Codeforces Beta Round 88
  • Vote: I like it
  • +208
  • Vote: I do not like it

Comments Comments (85)
| Write comment?
13 years ago, # |
  Vote: I like it +6 Vote: I do not like it
Anticipating hacker-rush round
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it
    Why hacker-rush? May be divisions will be divided to different rooms?
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it
      Yeah, I have absolutely forgotten that divisions are to be divided. What a pity...
      → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Although I like math a lot ( really, a lot! ), I'm just not that good at it. I hope problems won't be very mathy. ( This may get me many "thumbs down" :) )
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it
    Agree, no mathy problems plz.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +22 Vote: I do not like it
      OK, few minutes. Replace all problems in 20 minutes before contest

      </sarcasm>
      → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Wow i love codeforces.com.Almost 1 contest a week and that contests are great. :)
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Record number of regirstrants?
→ Reply
13 years ago, # |
  Vote: I like it +9 Vote: I do not like it
Can you please send the notification mail with more time of anticipation?. I received the mail with 4 hours befrore the contest started and  i didn't see it.

I think 18 hours before would be suitable for everyone.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I got the notification mail 13 minutes after the competition has started.
    → Reply
13 years ago, # |
  Vote: I like it +11 Vote: I do not like it
Very tough set of questions
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    They are more tend to DIV I level. However, I enjoy this match a lot. Thanks, Gerald.
    → Reply
13 years ago, # |
  Vote: I like it +14 Vote: I do not like it
Fast system judging is coming back.
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it -13 Vote: I do not like it

my solution is going to fail. prob. B.
Because I am printing only two type of answers :: "2" and "1 000000001"
→ Reply
13 years ago, # |
  Vote: I like it +6 Vote: I do not like it
for the problem A
 f4 3 - 9 -
 f3 2 4 8 10
 f2 1 5 7 11
 f1 0 6 - 12

→ Reply
13 years ago, # |
  Vote: I like it +28 Vote: I do not like it
Amazing system testing speed.
→ Reply
13 years ago, # |
  Vote: I like it +22 Vote: I do not like it
the problem A's test data is too weak !
I saw a lot of people just solve it by violence, the time complexity is O(t*n) ， but the code pass the system test, I want to know , the system test data is contain data like this:
50000 2
1 2 100000000
1 2 100000000
1 2 100000000
1 2 100000000
.....

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

I only wished it has a larger memory limit though.
→ Reply
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
I have a question, suppose somebody enter into the contest, read problems and don't submit any solution, will the contest be rated for him or not ?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    not rated
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it -27 Vote: I do not like it
      so there is a bug , and I suggest that it should be rated if he/she register the contest? do you agree with me?
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it +14 Vote: I do not like it
        No, I don't
        → Reply
      • 13 years ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it

        It were like you said some time ago. Now it's better, because if you have an issue and can't come back home, then you don't need to unregister (this happened to me)

        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Contest should not be rated only by registering for that contest, but it should be rated for anybody who read at least one problem.(Similar to Topcoder)
                   
          → Reply
      • 13 years ago, # ^ |
          Vote: I like it -14 Vote: I do not like it
        in fact, my meaning is that who registered and read problem should be rated!
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          It's hard to check now, who reads problem. Because It's possible to read it without authentication
          → Reply
  • 13 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it
    No, you will get rated only when you submit your code (or try to hack others according to the rules, but I don't know how...)
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      You can hack other solutions only after your solution for this problem passes pretests.

      So, only if you try to submit code, this contest for you will be rated.
      → Reply
13 years ago, # |
  Vote: I like it -6 Vote: I do not like it
I am hoping rating increase even though I have not solved anything :)
Because the rating system is flawd sorry.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    If you did not solved anything(score=0), but supposed to increase your rating - system will force your rating change to zero.
    → Reply
13 years ago, # |
  Vote: I like it +14 Vote: I do not like it

I liked problems C and D. But I fear this round might have been too hard for the division2 participants.

Thanks a lot for the round :)

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

Isn't it unfair that if somebody read problems and couldn't submit any solution then that round will be unrated for him.

→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
It's been a very good contest, I really enjoyed taking part in it. Unfortunately I had to resubmit problem B because of a stupid bug. I did like problem C although I failed to solve it in time.
Big thanks to the author for the contest.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Nice Experience , Want to see more combined division contests.
Nice problems too. :)
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it
    To be honest I think that it was div 1 contest, not combined division contest. More than 300 coders finished with 0 pts. And of course I like the problems.
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it
    I notice that combined division contests will easily give more rating .
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Tests of problem A are just unfair. I think this problem should be rejudged with 1-2 strong test case so that solution of O(n*t) (~10^13) cannot get passed. Or this round may be made unrated.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Or in problem statement, there should be something like "the values of t[i] will be given with equal probability in given range".

    PS: Sorry for my bad English.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Any ideas how to solve C?
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    1. Try to find any cycle. If there are no cycles prints -1.

    2. If we have any cycle with len>3 
    1 2 ... n-1 n
    let's check edge from 1 to n-1. If it exists 1 n-1 n is correct answer,
    else we have cycle 1 2 .. n-1(because of edge from n-1 to 1), that is shorter. Do it while len>3
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      isn't this O(n^3) ? You have to try to find a cycle N times and you have a quadratic amount of edges
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I find cycle only once by dfs. It's O(edges)=O(N^2)

        After that O(N) to make it shorter


        → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      why we can be sure that there is edge from n-1 to 1 on step 2?
      → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    A little modified DFS, you just should know not only current vertex but previous one too.
    → Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +38 Vote: I do not like it

    Here's my somewhat different approach:


    Start with a set containing all nodes. Recurse on that:
    1) If the set contains <= 2 nodes, no cycle is found here.
    2) Pick the first node (say, X). Now, separate the other nodes into two sets, depending on the direction of the edge from that node to the node we picked. That is, put all nodes A such that the edge is from A to X in a set, and put all other nodes in another set.

    Let's name the set with an edge from that set to node X with outward set, and the other set as inward set.
    3) Iterate over all members of inward set, say, I, Iterate over all members of outward set, say, O. If an edge is present from I to O (in that direction), return the triple (I, O, X).
    4) Otherwise, recurse on each of the outward set and inward set, separately.

    This works in O(N^2)
    → Reply
    • 13 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      sorry, wrong branch

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

      Could You explain more clearly point 3 ? If I iterate over all Inward set and for every element in Inward I check all edges to Outward I will definitely get |Inward| * |Onward|, so N^2, so the whole alogrithm will be working in N^3. I suppose point 3 should work in linear time, but I don't know how.

      → Reply
      • 13 years ago, # ^ |
          Vote: I like it +15 Vote: I do not like it
        No, we check them in |Inward| * |Onward|. However the overall complexity is still N^2. ;)

        Hint:
        Each edge in the graph will only be checked once in the entire algorithm.
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it
          Now I understand. At the begining I thought that in 4th point You merge Outward  and Inward and then recurse (on n-1 set). But of course if there is no edge from Inward to Outward (which we know from point 3), it is impossible that  there exists some ohter cycle between Outward and Inward (and then the merge is pointless). Thanks for help.
          → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        something like "divide and conquer"
        → Reply
    • 13 years ago, # ^ |
        Vote: I like it -9 Vote: I do not like it
      I tried this case 

      4
      0000
      1010
      0001
      0100

      on your code and its output was "1 4 2" which is obviously wrong, not sure if it is a problem in the case I provided or your idea or just a bug, in the last 2 cases that would mean system test was weak. If I am missing something please show it to me :)
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it
        It's incorrect test.

        No 1-4 edge and n 4-1 edge
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          "in which every pair of vertexes is connected by exactly one directed edge"
          I totally misread this part in the contest ! :( Sorry for that.
          → Reply
  • 13 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it
    Let count[v] be the number of outcoming edges of the vertex v. Then number of incoming edges is n - count[v] - 1. Suppose we take two first vertices of the cycle, name them v and u. And there is the edge vu in the graph. Proposal: (count[u] ≥ count[v]) then there exists w such that there is the cycle v → u → w. Let's prove it: suppose we have a vertex w, that there is the edges uw and wv, then we have a cycle. Let's look at the sets of incoming edges of v and outcoming edges of u, if they intersect, then there is such w. Suppose count[u] ≥ count[v] and suppose their sets of outcoming and incoming sets don't intersect. Then the cardinality of their union is n - count[v] - 1 + count[u]. This union doesn't contain v and u. So n - count[v] - 1 + count[u] ≤ n - 2,  count[u] ≤ count[v] - 1 and count[u] < count[v], so there is contradiction.

    Suppose we have a cycle, and there is no edge vu, such that count[u] ≥ count[v]. Let's look at cycle, name their vertices v1, v2, v3. As we supposed count[v1] > count[v2] and count[v2] > count[v3] and count[v3] > count[v1], so count[v1] > count[v1], thats impossible. 
    So the algorithm is to get all the edges vu, and if count[u] ≥ count[v], then find the third vertex of the cycle.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Thanks for explaining .
      If I understood correctly , the two para's are respectively "if" and "only if" parts for proving count[u] >= count[v] for existence of cycle , right ?
      → Reply
  • 13 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    This is my opinion:

    See the graph as a real tournament, every pairs of different teams plays exactly 1 match. We use an array rank[], in which teams with lower rank always win teams with higher one.

    - Firstly, rank[1] = 1.

    - Consider team I.

    - Find the best team (smallest rank) that team I wins, call it W.

    - Find the worst team (highest rank) that team I loses, call it L.

    We easily observe that rank[L]+1>=rank[W].

    If team W wins team L, we have a cycle I wins W, W wins L and L wins I.

    Otherwise rank[I]=rank[L]+1, and rank[W→array end]+=1

    It works in O(n^2).
     

    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      How to get the array rank[] ?
      initially rank[1] = 1 then rank[I] = rank[L] + 1 and rank[W->array end] += 1.
      Are rank[] initially filled with 0's ?
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I mistyped it. It should be, rank of teams which loses I +=1.
        → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I mistyped it. It should be rank of teams which loses I +=1.
        → Reply
13 years ago, # |
  Vote: I like it -6 Vote: I do not like it
I request rejudge over problem A. It took me (and as I see a lot other also) a bit much time to write O(n) solution where O(n*t) solution passed. By the ways, it helped me a lot to find my math weakness :p
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Any ideas on how to solve problem D?
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    If u know something about FFT(Fast Fourier Transform), it should be better to get in that. Here's my very complex solve, if u had better, plz tell me. : )


    So for F(A), each time, u divide A into two part, the first one of A contains all the elements that mod 2 equals 1, and the second one mod 2 equals 1+1=2(It should be 0 but it can be easier if u understand it as "2"). Then for each part, u do it again. This time, the first part contains the elements mod 2*2 equals 1 and second part contains the elements mod 2*2 equals 1+2, likely, the third part should be mod 2*2 = 2 and forth part mod 2*2 = 2+2.

    Knowing above, we can do something just similar to a binary search in O(log n)(maybe?) time. Assume a function query(l,r,nowmod,nowrest,startid,endid); it returns the available sum from b[l] to b[r]. The other four parameter represent a segment from array b, start from "startid", and end with "endid" and all of the elements in it obey that they mod "nowmod" = "mowrest". Then, if l == startid and r == endid, u just calculate a part of arithmetic progression contains all of the numbers from 1 to n and between u and v. For this step, u can use the formula of the sum of arithmetic progression in O(1), right? Else, u should calculate a position "mid", where the array divide into two parts. If l>=mid+1, all of the needed number is in the right of the progression, so u call query(l,r,nowmod*2,nowmod+nowrest,mid+1,endid). Similarly, if r<=mid, u call query(l,r,nowmod*2,nowmod,startid,mid). The other situation is l<=mid and r>=mid+1，u just break it into two parts, and return query(l,mid,nowmod*2,nowrest,startid,mid)
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      + query(mid+1,r,nowmod*2,nowrest+nowmod,mid+1,endid). Don't forget to get mod of the sum each time u calculate it.
      → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      nice :)
      → Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
When is the editorial coming???
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Virtual contests closed??? 
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Any hints on Prob.B ?? thx...
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    for each ma = (pa*10e9)%mod , 0<= pa <= min(a,mod-1);
    if(ma>0 && ma + b <mod) then whatever b is , (ma+b)%mod is != 0. 
    → Reply
13 years ago, # |
  Vote: I like it -10 Vote: I do not like it
I got TLE on B using Python and AC it with C++ and this happened many time in the past. Just wonder if the time limit for python can be lifted up a bit since python is much slower than Java/C
→ Reply
13 years ago, # |
  Vote: I like it +9 Vote: I do not like it
My code got passed when I changed std::cin to fgets in problem C. Lesson learned...
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Same here :D
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Why this difference?
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    cin/cout are slower than scanf/printf/puts/gets. So if you want to read more than 500KB from input it's not a good idea to use cin.
    → Reply
    • 13 years ago, # ^ |
      ← Rev. 2   Vote: I like it +6 Vote: I do not like it
      The thing is that cin/cout synchronize with stdio every time you use them. If you write cin.sync_with_stdio(false); at the beginning, speed will be greatly increased.
      → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
for the problem it seems there are lot of cases regarding where starting , finishing and the current position of elevator is ,,,,How a   lot of coders managed to do it n just a few lines could not get their idea .Can anybody help me please  in finding out that ,,,,,,,
→ Reply