Very interesting contest.

But, how to solve task K, L and H?

Thanks in advance.

# | User | Rating |
---|---|---|

1 | tourist | 3843 |

2 | jiangly | 3705 |

3 | Benq | 3628 |

4 | orzdevinwang | 3571 |

5 | Geothermal | 3569 |

5 | cnnfls_csy | 3569 |

7 | jqdai0815 | 3530 |

8 | ecnerwala | 3499 |

9 | gyh20 | 3447 |

10 | Rebelz | 3409 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 171 |

2 | awoo | 164 |

3 | adamant | 162 |

4 | TheScrasse | 159 |

5 | nor | 153 |

5 | maroonrk | 153 |

7 | -is-this-fft- | 152 |

8 | Petr | 146 |

9 | orz | 145 |

10 | pajenegod | 144 |

Very interesting contest.

But, how to solve task K, L and H?

Thanks in advance.

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/15/2024 13:50:48 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

L: We construct tree greedy , then solve problem with centroid-decomposition code: https://ideone.com/kzZmuP

L: Once we have the shortest paths tree, computing the answer can be done using centroid decomposition.

The tree can be computed with Dijkstra's algorithm, modified to prefer parents with a smaller path from the root (with respect to the lexicographical order). Checking if a path is smaller can be done with binary lifting, in a way similar to the computation of LCAs.

You can build tree without comparing pathes. After Dijkstra algorithm you can use DFS using only edges related to some shortest path, one thing you need before DFS is to sort edges by destination.

H. Let

p=x-y,q=y-z,r=z- 1. Then, inpqr-space, a subhill is of the formp≥const,q≥const,r≥const,p+q+r≤const.Fix the value of

p+q+r(try allO(N) possibilities). Now the task is a standard 3D-sum problem. In total it works inO(N^{4}).I believe it's also possible to solve it in

O(N^{3}) but looks quite messy.H: Let's split each 3d update/query into <=100 2d updates/queries. For fixed y, we get update/query on some rectangle. First do all updates using inclusion/exclusion (adding +-1 to points (X,Z) to denote adding +-1 to all x>=X, Z>=z and then taking partial sums to find value at position (x,z)); now you can answer each 2d sum query in

O(1) using partial sums once again.K: Kind of divide-and-conquer. Let's assume that each query contains element n/2. In this case we can calculate dp for each suffix of the left part of the array and for each prefix of the right part; now in order to answer a query you can combine corresponding suffix of first part and prefix of second part in

O(D). Now we are left with queries which are completely contained within left or right subarray; OK — let's solve them recursively. That gives usO(D*M) to answer all queries andO(N*D*logN) to calculate all DP values at each level of recursion.Is there any new upsolving? When I access upsolving system, the last problem is old -> "O-17 Sphenic Numbers".

Can you give the links of old problems? I don't understand what is Grand Prix. I see blog of its discussion on codeforces but there is no link to the actual problems. Is it a private contest?

It is private, but very good contest. Site is p̶r̶i̶v̶a̶t̶e̶c̶u̶p̶.̶r̶u̶ opencup.ru You can participate if you are registered in team, and your coordinator (in my case he is a lecturer in my university) gave you credentials.

Yes, it's a private series of ACM ICPC-style contests called Open Cup (website is in Russian only). Problems are private, participation is restricted to "sectors" only (it's basically a multi-site contest).

Is there a site where old problems are available for public in English? Is it illegal for the participants to share the problem statements?

I don't think there is one. No idea about the legality.

Actually, there are a lot of problem statements of previous seasons in public access here: http://opencup.ru/

Just choose season in left menu with the button "Выбрать сезон".

Then choose stage in menu "Выбрать этап" and there you can find problem statements.

I do not see the extended menu like you. Maybe you are logged in? I just see Div2/Div1 Results, Yandex and they also require login credentials.

It's at the very bottom of the page, on the left side. Extended menu appears on hovering the "Выбрать этап" button.

There are no statements for this season. Check some previous, for example: http://opencup.ru/index.cgi?data=newstape&menu=index&head=index&ncup=och&class=och

Finally, upsolving have apear!

...and later disappeared by 'Service is not available' :(

Where can i find problems?

F?

B?

Find the rightmost '(' that can be paired with some ')' in the range, and the leftmost ')' that can be paired with it, and remove them.

D?

We can get digit D as answer if all non-null digits in N are not less than D and all digits after first occurence of D in N are equal to 9. Find the biggest D we can get.

Lets compare digits by parameter 'how much this digit meets in the range 1..N'. How to make this comparator: The base observation is an each digit meets equal amount of times in numbers in the range 1..10^x-1. So lets process digits of number N from left to right, suppose current digit is X, there are three cases (suppose lhs < rhs):

If lhs not better than lhs, we can take rhs. So as result we can find maximum D where D have the same amount occurences as 1.

Does anybody know when (approximately) contest will be unfrozen? Just curious.

snarknews said it'll be done after 4pm tomorrow, after Vekua event in Tbilisi.

Thanks :)

Problem A is copied from this one.

And I think problem F is also copied from problems of Multi-University Training Contest in China. In my mind, I have solved this problem before.

how to solve C??

Consider all 4! permutations, after left,right,top,bottom fixed, you can fix horizontal & vertical offsets between left & right. After that you can find answer using dp (hint: for fixed horizontal offset precalc cnt[i][j] for top/bottom strings — count positions p, that s[p]=i and s[p+offset]=j).

Spoiler