Miyukine's blog

By Miyukine, 2 months ago, In English,

Hey! Together with Meet IT Foundation, we're delighted to present Camp IT!

So, what is it actually about? The main objective is to provide a place for development and networking for young programmers. This relates not only to algorithmic olympiads, but also to computer science activities of any kind!

Yet another IOI camp? Of course not! Although you will spend some time during the day doing IOI-styled problems, there are also Practice Activities and Evening Activities which aim to show you cool parts of computer science and give entertainment after a day of hard work.

Who can apply? You can apply if you're under $$$21$$$. Don't forget you need to fill in the Applicant Questionnaire, for which the time is May 2019.

What about money? We're happy to announce that you can attend Camp IT not caring about economical issues. We cannot reimburse travel costs, however.

If you would like to know more, refer to:

Camp IT website: Click!,

Meet IT website: Click!,

Meet IT Facebook Fanpage: Click!

See you in September! =)

Read more »

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

By Miyukine, history, 13 months ago, In English,

Disclaimer: this post contains my thoughts and suggestions. Feel free to discuss the topics in the comments

[TL;DR] Cool problems, issues, why not semi-rated.

First of all, I'd like to congratulate Um_nik for making the simultanously best and worst round I've seen in a while :) On a more serious note, I've really enjoyed solving your problems, in contrary to some yet-another-segment-tree-problems. Especially B was quite unusual when it comes to CF.

However, there are some issues brought up by geniucos here which I completely agree with. Memory limit issues are really rare, and you usually realize that when you get MLE1 after submitting. Unfortunately, it was not possible today, so some participants were affected quite much (hello Swistakk.

Moreover, it wasn't only a case of MLE. "Incorrectly" solved problem B required using random generators. And now the standard CF feature — RAND_MAX is 32767. I've tested my solution locally and was quite shocked to see WA10 after the long queue ended. Looking at my submission: oh, RAND_MAX. Let's fix it. Wait. The round has ended 3 hours ago =) Of course you can say this should fail. But the problem is that such solutions passed. Look at 38734837 or 38747568. Especially no tests with N = 1000 and answer Um_nik — seem quite weak.

And well... the queue. 30 mins is in no circumstances a "very end of the contest". Even in an OI-style contest it's quite a lot of time. Of course, participants who didn't submit anything during this time were not affected at all. Usually submits during this time belong to most important problems — or at least the hardest we could solve. So it is imho the most important period of time. Some participants passed systests without any problems, some got FST and some got errors on pretest1. My C submission fortunately passed pretests with 3950ms (with TL = 4 seconds). Of course, everyone would realize his implementation is not efficient enough after getting such verdict.

Now, the most important part. There were some other options used in the past other than binary rated. If semi-rated didn't sound like a good idea, then maybe you could at least allow participants who were severly affected by the long queue to be excluded from the official ranklist, just like cheaters are (but no bans please)? I'd be very grateful an for official response. Attention tag. KAN.

My apologies for everyone who had to read this boring wall of text. Cheers :D

Read more »

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

By Miyukine, 18 months ago, In English,

Disclaimer

The post will be mostly in Polish, as it will just contain solutions for training contests. I found Codeforces the most convenient place for writing them and allowing the participants comment.

Pierwszy krok (23 grudnia)

Obydwa zadania pochodzą z 11 oia. Szczegółowe rozwiązania można przeczytać w niebieskiej książeczce olimpiady.

Most
Turniej

Wiecznie drugi (24 grudnia)

Dzisiejsze zadania były z 2 etapu 17 oia i powinny się wykazywać trudnością większą niż poprzednie. Czasem do wejścia do finału wystarczą tylko 4 bruty ;)

Klocki
Chomiki

Trzej muszkieterowie (26 grudnia)

Trudniej już nie będzie :) 10 oi, ale zadania z siekierą. Myślałem, że autostrady są łatwiejsze, bo źle zrozumiałem na początku treść.

Autostrady
Trójmian

Read more »

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

By Miyukine, history, 19 months ago, In English,

International Tournament in Informatics is starting soon. The official website is here: http://iati-shu.org/en/home/

I'm wondering whether there is going to be an online mirror on csacademy or another site. Also, we can discuss the problems later here.

Read more »

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

By Miyukine, history, 23 months ago, In English,

Hi guys. Today I was solving a problem together with minimario and we came across a well known-looking subproblem we couldn't solve.

There are two sequences of length N, A[] and B[] with N, A[i], B[i] <= 10^5.

Our goal is to answer queries: a, b, x, y which mean : find the i in range <a, b> with the biggest value of A[i] * x + B[i] * y. 1 <= a <= b <= n, -10^5 <= x, y <= 10^5.

Is it possible to do it offline?

Is it possible with operation erase as well? (erase can be seen as setting A[i] = -inf and B[i] = -inf).

Thanks for any suggestions.

Read more »

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

By Miyukine, history, 23 months ago, In English,

I tried to solve CEOI 2017 Day1 problem — Mousetrap today during the csacademy mirror.

My idea is a bit different than what model solution does, but in the same time complexity O(nlogn).

I'll describe it briefly. First, let's assume we can freeze the mouse for a while and prepare the way for her. Let's calculate answer for this case and call it pathOnly. This is computed by the simple formula.

Now let's unfreeze the mouse. We will do binary search on answer — how many additional operations do we need now. Let's precalculate cost[] for each vertex x, meaning: how many additional operations if mouse gets to vertex x and stays there forever. Forever means in this case: until we prepare the rest of the graph for her.

Cost is computed by a simple recursive formula : cost[onPath] = 0 and cost[x] = cost[parent[x]] + degree(x) — 1 otherwise.

Now let's move to the last step of the solution. Assume we are at some step of binsearch checking if the result can be not greater than k now. If a vertex has cost bigger than k, we should never let the mouse reach it. Otherwise, the mouse can safely get to that vertex. We compute dp[x] now -> how many operations do we need to succeed to be done before the mouse enters vertex x, dp[x] can be either 0 or 1. When a vertex is forbidden or sum of dps from its sons is greater than 1, dp[x] equals 1. Otherwise, it is 0. In the end, if dp[root] > 0, the answer for our current k does not exist and does exist otherwise.

The problem is that this solution doesn't work in at least two ways. I believe the implementation is O(nlogn) and should fit in the time limit, but it fails a lot. It gets WA twice, too. I would be very grateful if someone expressed his opinion about it.

Code (pastebin)

Thanks in advance. PS. How to link the submission on csacademy?

Read more »

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

By Miyukine, history, 2 years ago, In English,

Hi everyone!

Baltic Olympiad in Informatics is being held in Bergen, Norway. Here is the official competition site.

I am wondering — will there be any online mirror? It would be great if there actually was one, it doesn't seem probable :/

Read more »

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

By Miyukine, history, 2 years ago, In English,
 
 
 
 
  • Vote: I like it
  • +37
  • Vote: I do not like it

By Miyukine, history, 2 years ago, In English,

8VC Venture Cup 2017 — Elimination Round[Editorial]

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Read more »

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

By Miyukine, 2 years ago, In English,

Hello everyone! The first round of the 8VC Venture Cup 2017 will be held on Sunday.

I am honoured to be the problemsetter of the round. Reyna helped me a lot. Huge applause to KAN for his valuable coordinator's help, and MikeMirzayanov for his admirable work for the Codeforces comunity. I also want to thank testers very much (Alexey ashmelev Shmelev and Alex AlexFetisov Fetisov).

This round is a first stage of 8VC Venture Cup 2017. If you want to acknowledge yourselves with the competition, try here.

The main character of the round is PolandBall. It's a small friendly Ball who lives in a forest along with other Balls. You'll surely like it :)

I tried to fulfill your demands with a various, interesting and challenging problems described in a concise way.

Hope to see you soon, good luck and have fun!

UPD1: Scoring 500100015002250250027503500.

UPD2 Thank you for participation! Contest is over. Did you like the problemset? Feel free to comment =)

UPD3 Editorial

UPD4: Winners

  1. tourist
  2. moejy0viiiiiv
  3. W4yneb0t
  4. ilyakor
  5. ainta.

Hope you've had a good time with PolandBall solving the problems.

Congratulations to all the winners and TOP-200 who advances into 8VC Finals =)

Read more »

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

By Miyukine, history, 3 years ago, In English,

Hello Codeforces writers,

How long were you waiting for your contests? Were the stuff answering?

Here is my short, sad story.

I written email with propositions of the tasks about one YEAR ago. After few days I've got a response from GlebsHP "Okay, your proposition is received and will be evaluated in a few next weeks. "

The delay turned out to be huge. My question is : Should we take it for granted that this is how it looks like?

More seriously, this is something which should be dealt with. Of course, we are all trying to make the community as satisfied as possible. But anyway it is really uncomfortable and also discouraging. Problems may get outdated or improved, the proposal should be probably rewritten after such a long period of time.

What could the Codeforces stuff do about it? Do you have any ideas?

Read more »

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

By Miyukine, history, 3 years ago, In English,

Hey!

Polish Collegiate Team Programming Contest (AMPPZ 2016) took place today, organized by University of Wroclaw. This is my first ACM experience, and I want to share with you my impressions.

To begin with, I'm still a high schooler (2nd grade). However, thanks to generosity of UWroclaw organizers team and some charity institutions, a few best high school teams were able to participate.

Now let's talk about the contest. My teammates were Paweł Burzyński(pawelek1) and Kacper Kluk (wonrzrzeczny). None of us is a really fast coder, so we just decided to focus more on accuracy than speed. As we'll see later, this was kind of a good idea.

The contest started with no delays. I was not expected to be the coding monkey, but somehow it happened that three first and easiest tasks were accepted by me. These were not really challenging, so let's just ignore this fact. Some time later, Kacper scored the "ifologic" problem C. Then, the difficulty has risen.

Meanwhile, teams of UWarsaw1 and 2 were skyrocketing, grabbing quite outstanding scores of 7 problems per 90 minutes and 9 problems after the first half of the contest. After 2,5 hours there were 2 problems with no solves. The problemset was rather on the technical side and at this stage it was only a matter of time who will manage to implement more tasks correctly. As for our team, Paweł scored an interesting F and Kacper was implementing G. B was still unsolved, but we were giving it a try, because it looked like a problem which requires just careful cases handling for which probably most top teams had no time.

There were still two number theory problems left, two graphs, two implementations G and (super awful) B and a something-with-convex-hull-problem E. At that point we had an accuracy of 0 incorrect tries, which gave us a good position even though our solving times was average. Paweł got into E and Kacper finished G, and at 3:15 we had 7 (+20 penalty).

After this, we got quite stuck on harder problems. Because we couldn't solve anything harder, I was chosen to code some clever backtracking for B. A similar problem was already on AMPPZ 2014, named pillars (http://main.edu.pl/en/archive/amppz/2014/fil). While I was adding new and new ideas to the solution, other guys were thinking on EIHL. 30 minutes left, and Paweł sat to code his I solution. Unsurprisingly, it had some bugs. There was little time left, so we had to speed up. We were working together, but I barely knew what the solution should do. We debugged the samples and... WA. 10 minutes before the end, we still had WA and Paweł had basically no ideas what could be wrong. I still don't know how I came up blindly with the right idea, but three mintues later we were happy with the AC. 8 problems with 2 incorrect tries during the whole competition -> that was rather well. At that point we knew we were going to be top10, and we were really satisfied.

After the contest, we had some time to discuss the problems with friends and meet some famous people. We've even managed to have a picture taken with Petr! :)

Then, the solutions presentation and final ceremony took place. The organizers prepared amazing piece of work which simulated the ranking in a really cool way. The final results :

  1. UWarsaw1 (mnbvmar, marcin_smu, swistakk) 11.

  2. UWarsaw2 (Stonefeang, Errichto, mareksom) 10.

  3. *Google (Petr, Franken, Kwasnicki) 10.

  4. UWroclaw2 (Lowicki, Syposz, Michalak) 9.

  5. UWarsaw3 (znirzej, tabasz, kezsulap) 8.

  6. *III High School Gdynia (Miyukine, pawelek1, wonrzrzeczny) 8.

Our results were really satisfactory. And what about you? How was your first ever ACM contest? I'm not talking about such programming legends as [Bredor] and his http://codeforces.com/blog/entry/45106 ACM story, just average people. I'm writing this mostly for myself to remember this event, but I will appreciate any answers :)

One more thing. I want to thank the organizers for an interesting problemset and a reaaaally cool event. Thank you, and thank all people who contributed to it. Looking forward to seeing you in @amppz2017!

Read more »

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

By Miyukine, history, 3 years ago, In English,

Have you ever seen a problem connected to graphs diameter, where it is used in complexity?

For example: http://main.edu.pl/en/archive/oi/21/tur .

Model solution goes O( (1 + sqrt(2)) ^ T) * (n + m) ), where n is number of vertices, m — edges and T is the longest path which we can encounter in it. However, longest path is not a diameter. I've just wanted to show what I am talking about.

Any help with finding such a problem would be highly appreciated. Thanks in advance!

Read more »

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

By Miyukine, 3 years ago, In English,

Today (April 1st) our school announced : "Glider meeting on 7th lesson". Everyone found it as an april fools' joke, but...

LOL ^^

And what is the best April Fools' joke you've ever taken part in?

Read more »

 
 
 
 
  • Vote: I like it
  • -25
  • Vote: I do not like it

By Miyukine, 4 years ago, In English,

This is the second part of Hunger Games Editorial, hope you'll enjoy it :) And again, thanks for stuff for awesome contest, congratz for survivors too!

UPD: Problems B, D, E, Q, T, W are now available, more soon :)

Editorial Hall of Fame:

Stonefeang Andres_Unt cuber2460 Anonym_KALEP adamant ngoisao_93 gendelpiekel fcdkbear izrak

Problem A: Good Numbers.

Tutorial by: ngoisao_93

Call LCM(i, j) the lowest common multiple of i and j.

First, we should analyse that if x is divisible by LCM(p^i, q^j), then x is divisible by p^i and q^j at the same time.

Call set s(i, j) the set of number x in range [l, r] that x is divisible by LCM(p^i, q^j). Call |s(i, j)| the size of s(i, j). We can find out that:

|s(i, j)| = |s(1, j)| - |s(1, i-1)| = r/LCM(p^i, q^j) - (l-1)/LCM(p^i, q^j)

Call set d(i, j) the set of number x in range [l, r] that x is divisible by LCM(p^i, q^j) and doesn't belong to any set d(ii, jj) (i <= ii, j <= jj, i != ii or j != jj and LCM(p^ii, q^jj) <= r). Call |d(i, j)| the size of d(i, j).

Our answer is sum of |d(i, j)| with i > j and LCM(p^i, q^j) <= r.

We also find out that |d(i, j)| = |s(i, j)|sum of |d(ii, jj)| (i <= ii, j <= jj, i != ii or j != jj and LCM(p^ii, q^jj) <= r). So we can use recursion with memorize to this.

Our biggest problem is now checking for overflow (since LCM(p^i, q^j) can exceed int64). I found a pretty easy way to do this in Pascal:

function CheckOverflow(m, n: int64): boolean;
const e = 0.000001;
      oo = round(1e18)+1;
var tmp, tmpm, tmpn, tmpu, tmpr: double;
begin
 tmpm:=m; tmpn:=n; tmpu:=GCD(m, n);
 tmp:=tmpm/tmpu*tmpn;
 tmpr:=oo;
 exit(tmp-e < tmpr);
end;

I wonder if there is a way to do this in C++ (without bignum)

Miyukine's update: Let's check if p*q = ret gives overflow. We can check if ret divides q and ret / q = p.

Complexity of whole solution: O((log l)^2 * (log r)^2 * (log l + log r))

Code; http://ideone.com/R1AgnQ

Problem B: Hamro and array

Tutorial by : ngoisao_93

We first calculate array d with d[i] = a[1] - a[2] + a[3] - a[4] + ... + a[i - 1] * ( - 1)(i + 1) in O(n) (if i is odd, d[i] = d[i - 1] + a[i], else d[i] = d[i - 1] - a[i]). Then, for each query, if l is odd then ans = d[r] - d[l - 1], else ans = -(d[r] - d[l - 1]).

Complexity: O(n + q).

His code: http://ideone.com/kMalCH

Problem C:

Problem D: Hamro and Tools

Tutorial by : ngoisao_93

We can solve this problem by using Disjoint — Set Union (DSU). Beside the array pset[i] = current toolset of i, we'll need another array contain with contain[i] = the toolset that is put in box i. If no toolset is in box i, contain[i] = 0. For each query that come, if box t is empty, then we'll put the toolset from box s to box t (contain[t] = contain[s] and contain[s] = 0). Otherwise, we'll "unionSet" the toolset in box s with the toolset in box t (unionSet(contain[s], contain[t]) and contain[s] = 0).

Finally, we can find where each tool is by the help of another array box, with box[i] = current box of toolset i. Finding array box is easy with help from array contain. The answer for each tool i is box[findSet(i)].

Complexity: O(n).

Code: http://ideone.com/Te3wS9

Problem E: LCM Query

Tutorial by: fcdkbear

Our solution consists of 2 parts: preprocessing and answering the queries in O(1) time.

So, in preprocessing part we are calculating the answers for all possible inputs.

How to do that? Let's iterate through all possible left borders of the segments. Note, that moving the right border of the segment do not decrease the LCM (LCM increases or stays the same). How many times will LCM increase in case our left border is fixed? Not many. Theoretically, every power of prime, that is less than or equal to 60 may increase our LCM, and that's it.

So for each left border let's precalculate the nearest occurrence of each power of each prime number. After that we'll have an information in the following form: if the left border of the segment is i, and the right border is between j and k, inclusive, LCM is equal to value. So, for each segment with length between j - i + 1 and k - i + 1 answer is not bigger than value. We may handle such types of requests using segment tree with range modification. In a node we will keep two numbers — double value of the LCM (actually, it's logarithm: note that log(a  *  b) = log(a)  +  log(b), so instead of multiplying we may just add the logarithms of our powers of primes) and the corresponding value modulo 1000000007.

After performing all the queries to segment tree we may run something like DFS on the segment tree and collect the answers for all possible inputs.

The overall complexity is O(n  *  log(n)  *  M), where M is a number of prime powers that are less than or equal to 60

Code: http://pastebin.com/7zcYTced

Problem F: Forfeit

Tutorial by: Anonym_KALEP

First we make an array F[] for each edge , for an edge like e if after deleting it we have two components C1 and C2 , then f[e] = |C1| * |C2| , It's easy to undrestand that if we increase weight of edge e by 1 the total sum of distances will increase by F[e].

Now we consider Sum as minimum total sum of distances , from where Min(Sum) = (N - 1)2 We can be sure that for answer is 0 .

Now we can solve the problem with DP Where DP[E][S]=number of ways we can weight tree with sum S using first E edges.Note that first we subtract Sum from K and we use dp for collecting K - Sum

DP[E][S] = DP[E - 1][S - (L[E] * F[E])] + DP[E - 1][S - ((L[E] + 1) * F[E])] + ... + DP[E - 1][S - (R[E] * F[E]]

This DP is O(K * N2) but we can reduce it to O(K * N) (where N < 400 )

Source code: http://ideone.com/WOZfbg

Problem G: Hamro and Izocup

Tutorial by: Anonym_KALEP

let S1 be the area of SECTOR BOC and S2 be area of TRIANGLE BOC Answer = S1 - S2

We can calculate OH using pythagorean theorem and length's of OB & HB( = α / 2) . so we can calculate area of triangle BOC .

for calculating the area of sector BOC first we should find . We name as

in triangle BOH according to Law of sines : = sin(O / 2) = = 2 *

So area of sector BOC = * π R2

Now we have S1 & S2 So we have answer !

Source code: http://ideone.com/Zkvh6p

Problem H: Hamro and circles

This problem is basically the same as G. First, imagine that second circle is a square and solve G. Then, swap the circles, solve G again and add results.

Source code: http://pastebin.com/ZvJJcAKP

Problem I:

Problem J:

Problem K: Pepsi Cola <3

There are at least 2 different solutions for this problem, I'll try to explain them.

cuber2460's solution:

Let's define A as log of the biggest value in sequence T. By the problem constraints, A ≤ 17. I'll describe an O(3^A) solution, which will pass if implemented without additional log factor.

We'll try to find for all possible values of OR how many subsequences have that OR. (Taking the result is pretty easy then).

Define X contains Y iff (XORY = X). Notice, that OR X might be created only from values, which X contain.

We'll write subset DP in a quite standard way. For all values of X, we'll first assign dp[X] = 2L, where L is number of values, which X contain. (L can be computed the same time we write DP, just for all subsets of active bits in X, we'll add L[x] += L[subset]). Then, we will just subtract all values, because not all the subsets have OR equal to X. But we'll have this computed before entering X, so we can remove them without any additional effort.

Source code: http://pastebin.com/R6B2a41u

My old code, which is O(3^A * A), and gets TLE, but it's quite easier to understand: http://pastebin.com/7GNLJQ7E

izrak's solution:

We consider a number to be the sum of some powers of two. (X = 2i + 2j + 2k + ...).

+ similar terms for 22 * i + j and 23 * i.

Where g[i][j][k] = the number of subsequences with bits i, j and k set. We can use the Mobius DP similar to that described in this solution: http://www.usaco.org/current/data/sol_skyscraper.html to calculate f[i] = # of elements in the input array which are "supersets" of i in O(nlgn). Then, to calculate g[i][j][k], we can calculate how many elements of the array contain bit i but not j,k or bit i,k but not j etc (call these types of requirements classes) through inclusion exclusion with f[] in O(3  *  23  *  23). Then by iterating over subsets of the classes to be included in our subsequence and doing some simple math we can determine g[i][j][k] in O(223 * 23 * 23). The overall complexity is thus O($n lg n + log^3 n) See code for details.

Source code: http://pastebin.com/Hphc3k2y

Problem L:

Problem M: Guni!

Tutorial by: Anonym_KALEP

We can solve this problem using 2 segment trees. In first tree we keep array a and after processing each query of type 1 on it we add score of gi to second tree and for queries of type 2 we process this query on second tree and add result to it.

In first tree we keep negative of array a and for queries of type 1 we apply RMQ on it for finding minimum element in the gi's interval , its obvious that absolute value of minimum element in that interval is maximum element in gi , cuz we kepp negative of ai's . also only information needed from gi's are their maximum element( their score ) , so after getting answer of queries of type 1 from first tree we only add max element of gi( that is negative also ) to the second tree .

for queries of type 2 we use RMQ again this time on second tree and now we have answer for query . answer of this query is needed information for this Guni!(gi) so we add this number to second tree again .

In the end the answer is sum of all elements in second tree (scores of Gunis).

Code: http://ideone.com/n00BPJ

Problem N:

Problem O:

Problem P:

Problem Q: Mina :X

We can preprocess answers for each set size with the following DP: dp[0] = dp[1] = 0

dp[i] = min(max(dp[j] + 1, dp[i — j] + 2) for each 1 ≤ j < i.

Also, we should find what j gives optimal answer, we'll need it later.

Therefore, when we'll get a set S of size i, we'll already know what is correct answer for it.

When we know which j gives optimal answer, we can just query first j elements from our set and query them.

If the answer is "Yes", we should take those elements (and extract every other from S). Else, we should extract those j elements.

Solution: http://pastebin.com/cQ9vFkPc

According to Anonym_KALEP this may be done with Fibonacci search. His code: http://ideone.com/3dTmfO

Problem R:

Problem S:

Problem T: The ranking

gendelpiekel's explanation:

Consider the simplified case where we know that, for some interval, every competitor is either before the interval (say there are S of these competitors), after the interval, or somewhere inside the interval with uniform probability over the whole interval (say there are K of these). Then if this arrangement happens, each of the K competitors then has a chance to come each of S  +  1th, S  +  2th, ..., S  +  Kth.

Note also that if we consider all endpoints together and then take the intervals between consecutive endpoints: then for each interval, every competitor will either not cover that interval at all, or will completely cover that interval (and thus if they are in it, they will have a uniform probability of being anywhere in that interval). Also, there are O(N) of these intervals.

This gives us the simple algorithm: for each interval (O(N)), for each competitor i, (O(N)), calculate dp[S][K] = the probability of S other competitors appearing before this interval and K other competitors appearing inside this interval (which we can do in O(N3) with DP). However, this is overall O(N5) which is too slow. So we need to try and calculate "dp[S][K] for all competitors except i", for every i. One idea is to calculate dp[S][K] for all competitors, and then "subtract" each competitor with some maths. Overall this would be O(N4). Theoretically this is possible but in practice it is too inaccurate.

Instead we can calculate this with divide and conquer (overall O({N4}lgN), or buckets . For example, for divide and conquer we can calculate f(l,  r) = the dp[S][K] for all competitors outside of the range [l,  r), and then recurse on f(l,  mid) and f(mid,  r).

Problem U:

Problem V:

Problem W: Palindrome query

Consider strings S and S', to make implementation easier. We'll use hashing to comparing their substrings. We'll store their values in a Fenwick or Segment Tree. Suppose we change position x. (Do not forget to remove previous value!) Then, instead of p1[x] * pot[x] we'll have p2[x] * pot[x] at this place. We add this value to our data structure, and we're done.

For each query we'll use binary search to answer it, as when there's palindrome of length K, we're sure there are palindromes of length K-2, K-4, ....

Source code: http://pastebin.com/gn4wNe6a

Source code by adamant : http://ideone.com/8kLke7

Problem X:

I'll try to write all solutions as soon as possible :)

Read more »

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

By Miyukine, 4 years ago, In English,

Here's the first part of Hunger Games Editorial prepared by community. There are only my hints, see also the second blog, which will be soon published, with different, more detailed solutions written by many people :) I'd like to thank problemsetters team (PrinceOfPersia, keyvankhademi and AliA) for such wonderful contest. Hints will be probably updated when I'll learn more beautiful solutions for these problems :) Enjoy!

Problem A: Good Numbers

Suppose first integer is multiplied A times and second — B times. How many ways are there to complete the big number? Did we count something more than once?

Problem B: Hamro and array

Try to count numbers on even and odd positions separately.

Problem C: Hamro and Vampire Diaries

Suppose A[1] = x. How do we calculate A[1 + 3]? How to calculate next and all other values of A? What happens if n mod 3 = 0?

Problem D: Hamro and tools

Read about how STL can merge lists in O(1) or consider all queries in reverse order.

Problem E: LCM query

Suppose right end of our interval is i. How many different LCM's can we reach in the left? Many? Not many?

Problem F: Forfeit

What is the minimum weight of our tree such that it satisfies constraints? How does the sum change when we increase one edge by 1?

Problem G: Hamro and Icozup

//lel maths

Problem H: Hamro and Circles

//lel maths again, how to explain maths? :D Does this problem differ much from G? What should we change to get AC in H?

Problem I: Hamro and Khikhland's map

We will get the most cash if we take all adges except MST. Google MST if you don't know what it is :)

Problem J: Special Vertex

Suppose we've queried vertex X. Then, we get answer which subtree contains the special vertex, we can forget about all other subtrees of X and do this recurvisely on this subtree. How to choose X such that our solution becomes fast?

Problem K: Pepsi Cola <3

Let's count for each OR how many subsets have this OR. Try to think which OR-es affect which others. How to calculate it fast?

Problem L: It's not that bad (seriously, why does this task has such title?)

Go through all powers of 2 from largest to smallest (2^30 -> 1). For every visited power we'll try to build new graph. For every edge: if its value does not containthis power (value OR power != value) add it to the graph. Then, check if end is reachable from start. What if so? What if not?

Problem M: Guni!

Associate each Guni with maximum value in it? Do we have to maintain any other values in it?

Problem N: Demiurges play again

Try thinking in DP categories. Count dpmin[x] and dpmax[x] for each vertex. Suppose we've counted them for all subtrees of x, how to count them for x?

Problem O: Cheque

Do it "with induction" by K. Suppose we know minimum values for all vertices that are in the distance <= V from marked points. How to count them for V+1?

Problem P: Godzilla and Candies

Choose vertex x. Consider all queries in the graph. For each query only count those vertices which DO NOT belong to the same subtree of x. Then, extract x from graph and do it recursively on all sons of x subtrees. How to choose vertex x such that our solution becomes fast? (See also problem J).

Problem Q: Mina :X

Try to come up with DP which counts minimal number of questions for subset of size X. When we will enter X, we'll have already counted all possibilities, so consider all of them once more and see which of them we may check.

Problem R: Makegraph

Suppose we have answer 1 at some point. Do we already know all the future answers?

Problem S: Godzilla and Pretty XOR

Try to build S optimally. What will be maximal size of S? How to check whether we should insert new value or not?

Problem T: The ranking!

I still do not know how to solve it :( But look at sth cool instead ^^ https://piwoicydr.files.wordpress.com/2015/03/dsc_1126am.jpg

Problem U: Godzilla and chess

Will n^3/32 solution be efficient enough? How to write it easily?

Problem V: Godzilla and ugly XOR

Consider max and min values separately, let's build MIN. Start from the most significant bit. Do we have to add it now or we may later?

Problem W: Palindrome Query

We may use hashing for checking if two substrings are equal. For all updates it's easy to modify our hash. How to answer queries if there were no updates? Does something really change when they are?

Problem X: Tree Query

Use divide and conquer on tree, think in the same way as P. Choose vertex x, perform some queries, extract x from graph, do it recursively. How to choose x? (compare with P and J).

Read more »

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