kpw29's blog

By kpw29, history, 3 months ago, In English

Today after the round #707 I managed to get Time Limit Exceeded on problem B. Surprisingly, when I resubmitted after system tests, and got AC fitting tightly into the TL.

So I resubmitted $$$5$$$ more times. Each one got Accepted, too.

It's not a first time this happens. During the round #683, when I was among writers team, in one of the problems someone managed to get TLE on system tests even though we had pretests=tests.

Did you also experience something similar? Any idea what causes the judge to become slower during the contest? And, most importantly, should it be considered a bug or a feature?

Read more »

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

By kpw29, 8 months ago, In English

Hello, Codeforces!

On behalf of Meet IT, I'm glad to invite you to (Codeforces Round #683 by Meet IT (Div1, Div2) which will take place this Sunday (15th November).

The round lasts 2.5 hours and is rated for both divisions.

What is Meet IT?

We are a family of enthusiastic and motivated young people passionate about programming and mathematics. We build a community where people learn together, motivate and help each other.

Please expand the spoiler to find out more about us.

Meet IT family members worked hard over the last few months to provide you with our favourite challenges we came up with. We hope that you will enjoy them as much as we did :)

We are enthusiasts of short and clear problem statements, strong pretests, and happy participants!

Every effort is valuable for us, and therefore I'd like to thank everyone who has contributed to the creation of this round:

  • Co-founders of Meet IT: Mateusz and Paweł for guiding Meet IT projects and making things happen.
  • Maciej, Piotr and Michał. Without their commitment in early years of Meet IT the Family would not exist.
  • Round coordinator antontrygubO_o for endless discussions about the problemset.
  • pawelek1 for coming up with problem ideas.
  • tnowak for massive support in the work on harder tasks.
  • staniewzki and jjaworska for developing the most challenging problem of the round.
  • pasawicki for interest in tennis which was an inspiration to one of the problems, and for preparing another problem.
  • lcaonmst for preparing a problem quickly and diligently.
  • Mohamed.Sobhy for coming up with a nice easy problem and preparing it.
  • hiphop-nigdy-stop for enduring my repetitive reminders to prepare a problem.
  • flaviu2001 for his excitement about the round after testing and help to improve the shortcomings.
  • _h_ for help in providing a high-quality editorial to one of the problems.
  • dorijanlendvaj for firmly complaining about one edgy problem that pushed us towards substituting it with a better one.
  • kobor for providing beautiful pictures for the removed problem. :(
  • Devil for coming up with the substitution problem :), without you we would be still finalizing the problemset.
  • arsijo for paying special attention to statements clarity during testing.
  • zdolna_kaczka for winning the virtual contest among testers.
  • Anadi for inventing an alternative solution to one of the hard problems as well as his kind comments and suggestions.
  • Farhan132 for his ideas on how to improve the problemset in the second division.
  • Linkus and JanPawel2 for showing the need to reduce the round difficulty a bit.
  • The Army of Testers: ffao, khiro, _cherry_, Whistleroosh, ijontichy, growup974, AwesomeHunter, Omkar, TeaTime, hg333.
  • MikeMirzayanov for the amazing platforms Codeforces and Polygon.
  • all the people who strive for Meet IT Family to grow.
  • Last but not least, my dear wife Marta who was very supportive throughout the long process of preparing the round.


I'm also thankful for Swistakk for testing the round thoroughly. Sorry for forgetting! I wrote the announcement sometime before that. I totally don't get why he got downvoted, please give him as much contribution as he deserves!


There will be $$$6$$$ problems in each division, with $$$4$$$ problems shared. One of those will have a subtask!

We strongly recommend to read all the problems. You have been warned :)


Div 2: 500 — 1000 — 1250 — 2000 — 2250 — (2500 + 750)

Div 1: 500 — 1000 — 1250 — (1750+750) — 3000 — 3000


We would like to host a stream shortly after the contest. We haven't yet figured out the details, you can expect some backstage stories about the round, Meet IT, and casual discussion. Stay tuned!


We've added the link to the stream which shows on the Streams pannel on the right. You're more than welcome to join our stream


Editorial is ready!


We hope you've all enjoyed the round despite some minor issues. Congratulations to the winners!

Division 1:

  1. Um_nik (the only person to solve all problems!)

  2. ecnerwala

  3. Benq

  4. ainta

  5. ksun48

Division 2:

  1. shb

  2. jz_597

  3. 1700012703

  4. XueYJ

  5. zybkl

Read more »

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

By kpw29, 10 months ago, In English

Thank you very much for taking part in the contest!

Contest timeline

1447A - Add Candies

Tiny hint

1447B - Numbers Box


1447C - Knapsack

Alternative solution

1447D - Catching Cheaters

Key observation

1447E - Xor Tree

Small hints
First step
Next step

1447F1 - Frequency Problem (Easy Version)

First steps
Proof of the observation above
Consequence of the observation
Why the simplification works
Solution for the easy version
Hint for the subproblem
Solution of the subproblem

1446E - Long Recovery

The upper bound
When does the organism remain sick?

1446F - Line Distance

Stupid hint
Geometric insight
Proof of observation
Final details

Read more »

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

By kpw29, history, 10 months ago, In English

I was first red in my second year of high school, now I'm barely yellow. But this is not going to be a whining blog, you can just laugh at what I did.

A few weeks ago I thought: crap, I was 2400 years ago, now my CF rating is pretty shit. I don't like the fact that the rest of my ICPC team has around average 2700 rating, and I don't like the idea of posting a contest announcement as a non-red.

I've also noticed that there were 2 months before my wedding (24.09), so I set myself a challenge to retire before that date, as a red coder.

I started daily practice, took a few virtual contests and did daily upsolving around 2400-rated problems. I was really looking forward to catching up. But round #664 didn't really go as I wanted — I skipped B because C looked very nice, and then got stuck on the arising geometry. Around zero rating change didn't interest me, so a minute before the end I thought: well, of course I'm not going to finish C in time. My previous (unrated) performances were consistently really good in Div2. Why not just fall and gain rating in Div2? It will be much quicker.

So I resubmitted my beautiful problem A in 1:59.

So far, so good. I looked at CF-Predictor during the contest and thought: "I should be OK." What could possibly go wrong?

top 10 epic fails

Guys, be smart. Don't try to fall to Div2 intentionally.

Read more »

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

By kpw29, 15 months ago, In English

Hi! I'd like to do ask the wise men of Codeforces if they know any resources related to SPFA (Shortest Path Finding Algorithm). The short description of the algorithm can be found in PrinceOfPersia's blog:


According to this comment by romanandreev it works on average in $$$O(m log n)$$$, but there are counterexamples. Is anyone aware of any papers trying to tackle SPFA complexity?

Read more »

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

By kpw29, 19 months ago, In English

Remember Camp IT? Well, it’s ok if not, because we’re organizing a new one and the summer one won’t be worth mentioning compared to this one anyways.

There won’t only be programming tasks on IOI level, but also ML workshops! You might think they won’t be challenging enough for you... The advanced level of the workshops will be hosted by profesionalists with years of experience (for example, Marek Bardoński from AI Revolution). They are prepared to grasp interest not only needs of students with little or no experience in Machine Learning, but also of those who have already worked in ML projects or interned at companies such as Boston Consulting Group or Facebook.

If you don’t already know, apart from the tasks and ML workshops there will be fun Evening Activities — as if the like-minded people, with whom you can talk for hours, was not enough.

Everyone 16-21 years old can apply (if you don’t fit into this gap, contact us and we’ll see what can be done). Yes, everyone can apply, as there won’t be any quiz to get in. The Winter Workshops won’t be free, but you can apply for financial aid if you would like to attend but financial circumstances would prevent you from doing so.

If that doesn’t convince you, just come and check for yourself... Be fast though, because the places are selling like hotcakes!

Book your place at our : website

Make sure you like our Facebook fanpage so that you can hear the freshest news

Read more »

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

By kpw29, 2 years 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 kpw29, history, 3 years 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 kpw29, 3 years ago, In English


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.


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


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


Read more »

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

By kpw29, history, 4 years ago, In English

International Tournament in Informatics is starting soon. The official website is here:

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 kpw29, history, 4 years 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 kpw29, history, 4 years 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 kpw29, history, 4 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 kpw29, history, 4 years ago, In English
  • Vote: I like it
  • +37
  • Vote: I do not like it

By kpw29, history, 4 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 kpw29, 4 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 I_Remember_Olya_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. Retired_MiFaFaOvO
  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 kpw29, history, 5 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 kpw29, history, 5 years ago, In English


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 ( 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 (Radewoosh, Errichto, mareksom) 10.

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

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

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

  6. *III High School Gdynia (kpw29, 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 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 kpw29, history, 5 years ago, In English

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

For example: .

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 kpw29, 5 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 kpw29, 6 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:

Radewoosh .I. Chameleon2460 sepiosky adamant xuanquang1999 rnsiehemt Fcdkbear JoeyWheeler

Problem A: Good Numbers.

Tutorial by: xuanquang1999

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;
 tmpm:=m; tmpn:=n; tmpu:=GCD(m, n);
 exit(tmp-e < tmpr);

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

kpw29'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))


Problem B: Hamro and array

Tutorial by : xuanquang1999

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:

Problem C:

Problem D: Hamro and Tools

Tutorial by : xuanquang1999

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


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


Problem F: Forfeit

Tutorial by: sepiosky

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:

Problem G: Hamro and Izocup

Tutorial by: sepiosky

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:

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:

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.

Chameleon2460'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:

My old code, which is O(3^A * A), and gets TLE, but it's quite easier to understand:

JoeyWheeler'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: 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:

Problem L:

Problem M: Guni!

Tutorial by: sepiosky

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


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.


According to sepiosky this may be done with Fibonacci search. His code:

Problem R:

Problem S:

Problem T: The ranking

rnsiehemt'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:

Source code by adamant :

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 kpw29, 6 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 aliasadiiii) 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 ^^

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