**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!

- standings link: http://contest.sgu.ru/monitor/?id=1

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:

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

Yeah, I like the last Saratov view. haha

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

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

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

100 votes up for the bottom right Saratov view :D

sorry man. There's only one type of bra for me, it's Algebra

So you are a girl and never wear bras? waiting for down vote online :)

hentai!!!

@_@ me? never

dude, I am a man -_-

The last Saratov view is mesmerizing *_*

i know, the beach is beautiful, isn't it ? *_*

Dude, there's a beach in that pic?! o.O

Around 8 things in particular?

Don't think small man, think bigger :)

Around 16 :P.

Atleast 18 dude !! :D :P

I love Saratov!!!

Anything in particular? :p

Many things in particular. I'm sure you know. ;)

Don't we all? ;)

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

Ugly Truth!!

the photo is not good for CF !!!you enjoy from this photo!!!

it got filtered in like 43 hours XD

Great prediction!

.

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:

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...Google lied to me, Sherlock.

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...

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

zero-based indexes? :D

here the science tell us it doesn't matter :D

but I believe many sorting algorithms will stuck on this problem :D

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

And I thought you got engaged only recently? :O

That's why I saw this image only once :D

This contest overlaps with the following contest

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

Lets hope one of the contests will be shifted :)

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

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

i love saratov especially girls :P

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.

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 :)

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

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

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

Saratov is beautiful !!

that motivates to code :P

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

I can't say anything:|

ACM & girls ...

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

Let vote them

I choose third one from left :D

I think all of them are good :x :D

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

Saratov: SU1, SU2

2011/2012: top2

2012/2013: top2

2013/2014: top2

2014/2015: top2

2015/2016: ?????

xD

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

Full version:

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

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.

wait. 8 queens..?

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

He ain't

REDfor nothin' ;)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 :)

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

Its repulsive

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 SIDEReally, 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.

Life is pain...

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

It will be possible soon

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

It will be possible soon

I think this contest is same with

TIMUSDuration and starting time are same.

NO

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

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.

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

What was the 31st test for F?

We've made about 15 WAs in that case too

my error was a wrong algorithm...

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

Thank you!

Thank you!

How to solve B?

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

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)

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.

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 :)

Thank you very much, that was the problem!

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

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.

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.

editorials?

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

cheaters are everywhere!

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

13

in final standings top14 without Saratov 5

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.

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

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

Oh, thanks!

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

Start another virtual participation.

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

Yes...

thank you for the contest it had some nice problems

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 :)

It was moved to the Gym.

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

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?

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.

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

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

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

When will the editorials be published?

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

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:

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.)

Any idea about problem C ?

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.

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.

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.

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.

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.

The update operation:

Query operation:

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

Thank You. :)

This method is giving TLE.

https://pastebin.com/zJTksZn1

Can you please check out the code and give some suggestions.

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.

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).

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 ?

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

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.

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,

`A.capacity >= m and A.voltage == 1:`

Take it and break the loop`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.`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!

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

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

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

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

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

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