MikeMirzayanov's blog

By MikeMirzayanov, 5 years ago, translation, In English,

The contest has been moved to the Gym.

Today it will be ACM-ICPC, NEEERC, Southern Subregional Contest! As a head of judges I wish good luck to all the participants!

On Saturday (October, 25), 07:00 (UTC) it will be a internet-mirror: [contest:481]. Interesting problems are waiting for you. Judges tried to prepare problems of wide difficulty range: for newcomers and for expirienced teams.

For sure, it will be unrated contest. We recommend you to take part in teams. I think, the contest will be moved to Gym later.

Good luck!

MikeMirzayanov, head of judges.

P.S. Saratov Views:

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

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

prizes are depicted at bottom right? (i thought alcohol i got 3 hrs ago lost its effect ;)

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

Yeah, I like the last Saratov view. haha

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it -59 Vote: I do not like it

    The comment is hidden because of too negative feedback, click here to view it

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

    This blog has 10 lines and 6 pictures. But all the comments are about the bottom right picture. Interesting :D

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

      I don't know man, I find that "Saratov Approaching" pic quite creepy. Like where is NSFL tag? Scarred4lyf :(

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

100 votes up for the bottom right Saratov view :D

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

The last Saratov view is mesmerizing *_*

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

I love Saratov!!!

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

Oh, dammit. Codeforces is gonna be filtered soon in Iran... :|

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

I'm sorry to say that, but the "Saratov Girls" photo is taken at Sydney's Bondy Beach (Australia) for some Cosmopolitan Magazine event:

Click the image below to follow the link and switch to the 2-nd picture to compare:

1000 babes in bikini

And note Copyright 2012 News Group Newspapers Ltd and/or its licensors. No use without permission. Contact ... when right-clicking the image.

However, I think other pictures may be more authentic :)

And by the way I believe There are many more beautiful girls in Saratov — probably it would be easier to find them via social networks rather than from google...

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

    Google lied to me, Sherlock.

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

      My bad, I thought that I've met the second girl from the left.

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

        My bad, I thought that I've met the second girl from the left.

        Ah, nowadays the girls often are trying to follow the same "magazine-photo-model-standard" which leads to many of them be quite indistinguishable :(

        P.S. But it may happen that either you or this girl have travelled there some time ago...

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

          Everyone in Saratov reads Cosmopolitan, that's why the last picture is pretty standard for them

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

        zero-based indexes? :D

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

          here the science tell us it doesn't matter :D
          but I believe many sorting algorithms will stuck on this problem :D

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

    Thanks RodionGork for making image larger now everything is clear :D

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

This contest overlaps with the following contest

http://acm.timus.ru/contest.aspx?id=241

Lets hope one of the contests will be shifted :)

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

    Thanks for warning it! I totally forgot about the timus contest.

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

      you can use google calender , whenever you find a contest scheduled it and just check the calender every morning , it helps me a lot :)

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

i love saratov especially girls :P

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

To be noted, there is this contest on UVa http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=12 and another one in Timus http://acm.timus.ru/contest.aspx?id=241 same day/time.

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

    The UVA contest will not take place,as far as I know (but not 100% sure). Still we have two contests at the same time on CF and Timus. Both contests are GREAT and both Russian,so,lets hope the personnel in charge will do something about the time clash :)

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

      Contest on Timus is better for Div. 2, Southern Subregional — for Div. 1

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

please change your photo this photo is not good for CF !! thanks

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

I didn't know why, But since I was a kid, I had a feeling that I love Saratov. And now I know what was the reason of that feeling. :D

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

Saratov is beautiful !!

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

that motivates to code :P

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

    Or just gives you plain distraction. If you know what I mean ;)

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

I can't say anything:|

ACM & girls ...

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

    Then don't say anything , Just make sure that you don't flood the blogs with comments that don't mean anything.

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

Let vote them

I choose third one from left :D

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

    I think all of them are good :x :D

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

Is it possible to keep rated contests for teams and give ratings to teams like you give ratings for individual users ?

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it
  • 2012/2013: top 4
  • 2013/2014: top 4
  • 2014/2015: top 4
  • 2015/2016: ?????
  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Saratov: SU1, SU2

    2011/2012: top2

    2012/2013: top2

    2013/2014: top2

    2014/2015: top2

    2015/2016: ?????

    xD

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

      Don't praise your teams unless they defeat Nizhny Novgorod SU.

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

    Full version:

    2009/2010 top 4
    2010/2011 team with dalex
    2011/2012 team with dalex
    2012/2013 top 4
    2013/2014 top 4
    2014/2015 top 4
    2015/2016 top 1 (as ez collections became java standard)
    
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This picture on the bottom right corner really has nothing to do with a programming website Always distract me when I open the site.

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

    Why do you say it has nothing to do with programming? It's a well known programming task — eight queens. You need to place eight white queens on the chess board so that none of them can beat any other. The solution displayed on top is not a valid one though.

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

      wait. 8 queens..?

      holy macaroni, you certainly know how to think outside the box.

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

      marat.snowbear if you look closely, then you'll find out that this is actually a variation of the eight queens problem — nine queens. It can be observed more clearly thanks to the image provided by RodionGork :)

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

      Yes but chess pieces are much harder and they are not physically attractive.

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

Its repulsive

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

Trust from the GOD!!! What is this picture??? Do you know hove many person will see that picture???
I GUESS NEXT TIME YOU WILL NOT PUT BAD THINGS IN THIS SIDE

»
5 years ago, # |
Rev. 3   Vote: I like it -14 Vote: I do not like it

Really, can that picture be removed? In addition to different religious views, consider a high-school teacher recommending the website to his/her students. If this picture will be the first thing they will see, it might lead to some embarrassing situation and the teacher getting fired.

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

Why can't I register a team ?? :\

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

It says in the post that teams are preferred. But how to register a team for an upcoming contest?

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

I think this contest is same with TIMUS

Duration and starting time are same.

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

Ranklist is broken. My solved G disappeared from the ranklist after a while. WTF?

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

    Why the negative rating? The above message was a legitimate bug report I typed during the contest. The ranklist was indeed broken for quite some time (30 minutes or so). My dashboard showed that I had 7 problems solved but one of them (and not the last one submitted) was missing from the scoreboard. It did, as I mentioned before, disappear -- immediately after I solved problem G it was shown in the scoreboard, but it stopped appearing after a while. I have no idea how such a thing is possible, but it is certainly a bug.

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

Cant apply binary search on them(hot chicks) due to random distribution... :P

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

What was the 31st test for F?

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

    We've made about 15 WAs in that case too

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

    my error was a wrong algorithm...

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

      You are choosing the max cut, then choose the next max cut, but this is totally wrong, You have to try all possible cuts and select the maximum cut on the left or on the right.

      in case 31:

      9 3

      15 15 15 30 1 30 15 15 15

      You select (10+1+30) which is 61, then you have only (15+15+15) on the left or the right,

      but if you try all cuts, you will get (15+15+30) + (30+15+15)

      something like this: 8410587

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

How to solve B?

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

    make a count for each color ... and keep the "-1" blankets as a bonus

    Now repeat the following process while u have a color where count[color]%(k/n)!=0 :

    • Pick the color with the minimum count and count[color]%(k/n)!=0 ... call it color1

    • Let's set v = color1%(k/n)

    • Pick the color with the maximum count (other than the color1) .. call it color2

    • If u can't find possible colors in step2 ... pick the bonus blankets.

    • Now color v blankets from color1 with color2 ... and (k/n-v) blankets from color2 with color1

    • if (k/n-v)>count[color2] ... use bonus blankets, and remove from them k/n — (v+count[color2])

    • if conut[bonus] < (k/n) — (v+count[color2]) ... then the answer is No

    After u finish this process, for any color i, it will achieve count[i] % (k/n) = 0

    Which can be easily matched with itself

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

      Directly while loading the input you can color one side of each -1 blanket any color you like (e.g., add all of them to color 1), the solution always exists anyway, and the code gets simpler: you simply always take the color with the least (non-zero) number of blankets, and if it is not enough, you fill the rest from the color with the most blankets.

      (This is essentially the same algorithm as used in the Alias method)

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

        Strange, I'm doing the same, yet I can't get past test #2. I made random tester and checker just to find that my code easily passes a few million tests. It seems I am missing something, can somebody help me with tests/suggestions?

        The code is 8417893.

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

          Test #2 is most likely the second example input. You are failing it because you are not outputting the blankets in the order in which they appear in the input. (Your third blanket is 3 4, but one of its sides should be 1.)

          I got one WA for this during the actual contest, I was also too careless in reading the statement :)

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

            Thank you very much, that was the problem!

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

        I've get AC using your instructions and read about Alias method but can't understand why is it the same algorithm ='(

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

      Do you have a proof of why this works? (Or a link to a proof; I couldn't find an editorial.)

      We considered this greedy approach, but since we couldn't prove it, we didn't implement it.

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

        Here I am giving the proof of problem B. We know that we can easily solve the problem when n=2. Now if we have n=x then we can simple reduce it to n=x-1 using the technique described above,i.e.,take the color with smallest number of blankets and complete this set with any other set of color u want(above given is the set of color with maximum number of blankets). One thing should be kept in mind that the other chosen set must have blankets greater than required number.

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

editorials?

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

First time I see, a grandmaster wants to cheat with me! Cheers!

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

How many comands go from NEERC Southern Subregional to 1/2 final NEERC Spb?

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

D — Data Center. I dislike such "obfuscation" that LOW voltage is marked by bigger value (1) than HIGH voltage (0), why not ask to find minimum servers with HIGH voltage, which should be marked as 1? I misread (as usually) statement, made opposite, and gain WA #12 8408879.

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

Is this Contest archived? I can't resubmit any problem!

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

    For now, you need to enter it in virtual participation to be able to make submissions.

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

      Oh, thanks!

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

      My virtual participation has ended but I still want to make more submissions. What can I do?

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

        Start another virtual participation.

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

        You can start a new virtual participation :v But after that, you can't submit any other contest ^^!

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

    Yes...

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

thank you for the contest it had some nice problems

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

This contest is no longer on the contest page. Why has it been removed ?

EDIT: I now see it has been moved to the gym :)

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

Can anyone give me some hints about prob. G and K?

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

    G: Find the leftmost interval that needs changing. Where should you change it? Clearly, the best option is to start from its right end -- this will also lower the most other intervals to the right of the current one. My solution runs in O(n) and uses a deque to store the non-minimal elements in the current length-K interval. Each time you move one step to the right, possibly pop_left once, push_right once, and then pop_right while needed.

    K: Obviously, you can connect each vertex to the second one in its list (i.e., the first one other than itself). This gives you at least n/2 edges, but not necessarily all n-1. How to generalize this? Suppose that you already have some components. If some component A and component B were connected via an edge a-b, what would you see? For each vertex of A, the first vertex of B in their list would be b, and vice versa. Notably, a and b are the first ones of A and B for each other. When can you be sure that you found a new edge? If you find two vertices a in A, b in B such that: b is the very first vertex in a's list that is not in A, and a is the very first vertex in b's list that is not in B. Does such a pair of vertices always have to exist?

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

As if girls were the prize of ACM ICPC :-P
and yeah, look at the hypocrites, if some non-'RED' coder comments they upvote it (oh look, how funny), but if same comment is made by some other coder, they all join hands to downvote it.

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

I can's submit problems in the Gym. It goes to a link like this — http://codeforces.com/gym/100513/problem/C?csrf_token=a9770299g5h52c9hda3d7887h9h9313a and shows error code ERR_EMPTY_RESPONSE

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

    Same here. Me too. I got "Network Error" every want to submit

»
5 years ago, # |
Rev. 3   Vote: I like it -21 Vote: I do not like it

"Network error"! I can't submit! :(

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

When will the editorials be published?

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

Can someone kindly outline the idea for Problem K?

My idea was to regard graph as a chain for every vertex to create distance matrix,then use floyd to compute shortest distance, finally union set to output n-1 edges 8417836 don't know where it is wrong and it keeps wrong answer for test 4

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

    Your code does not make much sense to me. Why would you, for example, do "dis[u][v]=dis[v][u]=min(dis[u][v],j-1);"? If v is the j-th vertes in u's list, it can still be much closer than in distance j-1 -- for instance, even in distance 1. So at this point you only get some random upper bounds on the distance.

    Afterwards, you only process pairs that are in distance 1, but those had to be in distance 1 even before the Floyd-Warshall, so the Floyd-Warshall actually does nothing, and you only take the pairs of vertices you already know that are in distance 1.

    Here is a test case that breaks your solution:

    4
    1 2 3 4
    2 1 3 4
    3 4 2 1
    4 3 2 1
    

    You will only find the edges 1-2 and 3-4, but not the edge 2-3.

    (I already wrote a post with some hints for K, look above.)

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

Any idea about problem C ?

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

    First of all, in order to ease your processing you might want to convert the tree such that each node has only one key/value pair. Then each "component" will be represented by a chain of k/v pair nodes, connected from the first one to its parent (unless it's the main component), and from the last one to all of its children in the component graph. Now your problem is simply reduced to finding the first occurrence of some key on the path from any node to the root. This can be done in O(log N) time per query using a technique known as Heavy-Light Decomposition (HLD) — a fairly simple transform that allows you to get from any node in a tree to the root in logarithmic time, by potentially skipping over entire chains.

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

      Bruce also mentions heavy-light decomposition in his blog but I think that it is an overkill and that my solution is simpler to implement. Here it is:

      Preprocess the tree into a list of (key,value) pairs by running a simple DFS and maintaining a stack for the occurrences of each property. Here are the steps:

      • Each time you enter a new vertex v, append all its properties to the list, push them into the corresponding stacks, and then store the current length of the list into L[v].

      • Each time you finish processing a vertex, pop all its properties from their stacks and append the new tops of those stacks to the list (these key,value pairs just became visible again).

      After this preprocessing, for any vertex v and any key k, we simply need to find the last occurrence of k in the first L[v] elements of our list. To do this quickly, just build an interval tree on top of the list, and in each node store the set of keys that occur at least once in its subtree.

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

        That is slightly simpler (although the heavy-light decomposition only takes about 25 lines of code). I suspect it could be simplified further to avoid the interval tree: just keep a separate list for each property, with a field for the position in the original combined list (which doesn't physically need to be constructed). Then the search just becomes a binary search on the right per-property list, and can use lower_bound.

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

          This is exactly how I solved it (8408659).

          For each property:

          Consider only nodes that contain it. Iterate these nodes in the dfs order (we can run a dfs beforehand to determine this). When you enter a node, push its value to the stack. When you exit from a node, pop its value. Since there might be missing nodes (not all of nodes have this property), we can add some extra spaces between the sequence of nodes to simplify the query process. Eventually, we just use lower_bound to find the relative position of the given node in the preprocessed sequences and return its value.

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

    Here is an easy segment tree based solution:

    First build a segment tree by traversing the tree in preorder, then each subtree forms a contiguous segment in the segment tree. Each node u in the segment tree has a map tree[u]. An update operation at node u takes a (key, value) pair and updates tree[u][key] with value if tree[u][key] is not set yet.

    Run a dfs to build the segment tree, index[node] is the index of component node in the segment tree.

    dfs (node, count)
        index[node] = count
        for each child u of node
            count = dfs(u, count + 1)
        for each (key, value) in property[node]
            // note that the segment (index[node], count) contains the subtree from node
            update (1, 1, n, index[node], count, key, value)
        return count
    

    The update operation:

    update (node, l, r, x, y, key, value)
        if x > y
            return
        if l == x and r == y
            tree[node][key] is not defined
                tree[node][key] = value
            return
        mid = (l + r) / 2
        update (node * 2, l, mid, x, min(mid, y), key, value);
        update (node * 2 + 1, mid + 1, r, max(x, mid+1), y, key, value);
    

    Query operation:

    query (node, l, r, pos, key)
        if l == r
            if tree[node][key] is defined
                return tree[node][key]
            else
                return N/A
        else
            mid = (l + r) / 2
            if pos <= mid and query (node * 2, l, mid, pos, key) is not N/A
                return query (node * 2, l, mid, pos, key)
            else if pos > mid and query (node * 2 + 1, mid + 1, r, pos, key) is not N/A
                return query (node * 2 + 1, mid + 1, r, pos, key)
            else if tree[node][key] is defined
                return tree[node][key]
            else
                return N/A
    

    Now for query (x, key) answer will be query (1, 1, n, index[x], key)

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

    It's possible that offline solutions got AC in problem C ? I code a offline HLD and i don't know why i got "Idleness limit exceeded on test 1" . Should be because i run a offline algorithm ?

    Code: http://pastebin.com/6hE9PWaT

    My idea is very similar to many people , for every kind of key i activate all nodes with that key and then answer all queries of same kind of key.

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

      Yes, you should construct an online solution. This is an "interactive" problem: you can't read the next query until you print the answer to the previous one and call fflush(stdout).

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

        Ok i know it now , Thank you very much , it's first time that i try to solve an interactive problem :v.

        PS: How do you solve it with an online solution ?

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

I've added analysis of all the problems except L to my blog.

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

Any idea what is causing the runtime error for problem D? I saw a couple of people get it (including me.) I got it on test 16.

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

    Was because I didn't use long for m. But now I am getting a wrong answer on #17. This is my algorithm:

    Sort servers with first comparator capacity and then voltage. That is for two servers A and B, A is greater than B iff A.capacity > B.capacity or A.capacity == B.capacity and A.voltage > B.voltage

    Then looping from the last server,

    • If A.capacity >= m and A.voltage == 1: Take it and break the loop
    • Else if A.capacity >= m and A.voltage == 0: Traverse ahead and check if there is an element C such that C.capacity >= m and C.voltage == 1. If such an element is found, break and take C. If at any point C.capacity < m break and take A. Else take C. Break the loop.
    • Else (In this situation A.capacity < m so take it irrespective of voltage because we have sorted by voltage anyway. And then set m = m - A.capacity

    If someone wants my code please inbox me. I would appreciate any help. Thanks!

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

How to solve problem A? Как решать задачу А?

UPD: ;) find http://codeforces.ru/blog/entry/14368#comment-194335

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

could adminstor put the Ural Regional School Programming Contest 2014 contest into the gym to practice,it is also a very good contest,thanks

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

I am left with all these girls, you fall in love you want

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

I think I didn't understand problem 100513L - Useful Roads . Can someone provide me with the output for the following test case?

6 6
1 2
1 3
1 4
2 5
2 6
3 6

I think the useful edges are all, cause all of them can be used to go to some vertex.