Hello, Codeforces!

Educational Codeforces Round 13 will take place on 13 June 2016 at 19:00 MSK for the first and the second divisions. Almost two months passed from the previous round. That is due the next reasons: 1) I coordinated regular CF-round at the end of April; 2) about whole CP community were busy with preparing and competing in ACM ICPC WF in May; 3) at the beginning of this month I start to work at AimTech (I hope that I'll have enough time to continue prepare ERs).

<It's need to read at least once maybe you'll find something interesting>

The round will be unrated for all users and it will be held with extented ACM ICPC rules. You will have two hours to solve six problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

If you have ideas for some problems or maybe already prepared problems that you can't use in rounds or official competitions, you can write to me.

It seems that it is harder to invent interesting simple problems (like A and B) than difficult ones. So don't be afraid to suggest interesting simple or very simple tasks (of course the difficult tasks are also needed). Please send only the problems for which you know the solution with clear statement (the story is not required). And also please add one or two samples to make the problem statement more clear.

</It's need to read at least once maybe you'll find something interesting>

The problemset was suggested by Codeforces users. The problem А was suggested by user Abdrakhman Ismail bash. The problem B was suggested by Arthur Jaworski KingArthur. The problem C was suggested by Sheikh Monir skmonir. The problem D was suggested by Zi Song Yeoh zscoder (there are a lot of unused his problems). The problem E was suggested and prepared by Alexey Dergunov dalex. The simpler version of the problem F was suggested by AmirMohammad Dehghan PrinceOfPersia.

Thanks a lot to them and all others who are sending the problems! The number of unused problems are increasing. If I didn't miss anything I already replied to all who sent me the problems at least 5-6 days ago. Please be patient if your problem was not used a long while.

As I said the problem E is prepared by Alexey Dergunov dalex. All other problems was prepared by me (Edvard Davtyan). Thanks to Tatiana Semyonova Tatiana_S for checking the English statements. The problems was tested by users suggested them, respectively: Abdrakhman Ismail bash, Arthur Jaworski KingArthur, Sheikh Monir skmonir, Zi Song Yeoh zscoder, Alexey Dergunov dalex and AmirMohammad Dehghan PrinceOfPersia. Thanks a lot to all of them!

I hope you will enjoy the problems! Previous time the problems were too hard. I've tried to fix that. The problems should be simpler than usual.

Good luck and have fun!

UPD: The round is finished. The editorial is published.

It's the first summer round :-)

Where is Delinur?

They don't need her since Edvard is a native Russian speaker and he also knows English (obviously!) and Tatiana Semyonova has checked English statement.

Usually I'm translating the problems by myself (it helps me to improve my English) and the interpreter (Maria and now Tatyana) just checking the problem statements and making fixes.

Interpreter — это тот, кто устно переводит. В данном случае наверное надо было использовать translator. By нужно убрать перед myself. Дальше у вас со временами все перепутано

Actually, Maria left the project, she asked to convey greetings and best wishes to all people on Codeforces! Tatyana Tatiana_S Semenova agreed to help us with English :-)

I did not know her handle and could not find it. Now I'll add it to the post.

Mike, I want The Educational Codeforces is rated *. *

Couldn't give the previous one....had been waiting for this one for long! Excited! Hoping for a matrix exponentiation problem...I never solved it in a contest!

participate to kiya nhi

Looks like you still haven't solved a matrix exponentiation problem in a contest. :P I solved my first today :D

Could easily be solved with simple fast exponentiation without forming a matrix.

Result = (exp(a,n)*x + b*(exp(a,n)-1)%M * exp(a-1,m-2,m))%M , a not equal to 1

(x+b*n)%m if a = 1

Result = (exp(a,n)*x + b*(exp(a,n)-1)%M *

exp(a-1,m-2,m))%MCan you explain what happens there? I have found formula: a^n*x + b((a^n-1)/

(a-1))And this is only point which I don't understand.

(a/b)%MOD=(a%MOD*(modular mult. invserse of b modulo MOD))%MOD See this for more:https://github.com/ishan-nitj/Competitve-Programming/blob/master/Number%20theory/Modular%20arithmetic.pptx

and this https://github.com/ishan-nitj/Competitve-Programming/blob/master/Number%20theory/GCD%20and%20modular%20exp.%20by%20squaring.cpp

"It's the first summer round"

No here, I'm freezing

I know this if Off topic. But Believe me, my rating was 1905. Any changes in rating system?

See the standing http://codeforces.com/contest/677/standings I did this contest unofficial.

check this: http://codeforces.com/blog/entry/44214

Is this round being delayed for 10 minutes?

At least.

Looks like it. Now I get to properly finish my lunch xD

Well, I know what is needed to solve F and I also know that I can't code it so I quit, good luck! :D

Can you tell what was the idea behind solving F??

It can be solved like this http://codeforces.com/blog/entry/22031, look at the comments :)

I did it same way but it timed out. My solution

I guess it timed out because of SQRT DECOMPOSITION .

That's why you're purple. I used to had this "well, it's obvious this problem can be solved by persistent 2D segment trees with heavy light decomposition built on linkcut trees, hire monkeys to code it for me" and walk away proudly for coming up with such a 'brilliant' solution, but I discovered that's not the way one should follow. In half of cases it turns out such problem has some nice tricky solution using very simple techniques and in half of cases it turns out solution is in fact what I thought, but still a lot of people have no troubles with implementing it which is a sign that I should definitely improve my coding skills in that area. Treat contests (especially educational rounds) as opportunities to learn not just the place where you solve problems which you already know how to solve.

After becoming red approach changes, right? :p

Looks like he hired monkeys to code it for him, or coded all the stuff like a monkey himself.

This way he can be smart in the discussion:

While copy pasting ton of stuff on every problem in 2 minutes, get the whole problemset done in 10 minutes and red color very quickly :P

I didn't want to say "I invent tricky ideas, so I am red", I wanted to say "Stop giving up, that is not the right way to progress" and "Sometimes appropriate way to solution leads through tricky ideas and sometimes it leads through fighting one's weaknesses with coding something, and surely it doesn't lead through being satisfied with coming up with complicated solution". "I am not able to do this, so I won't even try" attitude is the worst way to improve your skills.

What I said here and copying prewritten code are kinda irrelevant. "hire monkeys to code it for me" was the key part. Main point here is that one definitely should not treat coming up with solution as all the logical difficulty and implementation as dirty duty one can omit and be satisfied (as I used to on high school). Another thing is that as long as code is prewritten by me and contest rules allow me to freely copy-paste it then if it helps me getting fast AC I feel the right to be fully satisfied with it — such scenario is rather the exact opposite to scenario of getting no AC at all which we are talking about.

Edit. The reply should be to your upper comment. I got confused by the comments tree :)

My comment refers to "That's why you're purple".

Basically it suggests that red coders either find a nice and tricky idea or have such a good coding skills that can implement a complicated idea quite fast. Which means red coder = very smart or skillful and not red = !(smart or skillful) = !smart & !skillful.

You forgot to add that you also use additional approach. You got such a huge library, because of spending a lot of time on problem solving and practicing/participating in many contests, that you can just copy-paste most of the complicated stuff.

This changes things a lot as it means red coder = ((1) very smart or (2) skillful) and (3)having a lot of practice and a lot of libraries.

And in this case not red means !(((1) | (2)) & (3)) so smart and skillful meets that criteria.

This was example of discrimination by cf color. I don't know why do you think that once you are red, you can treat not red as somehow worse and less talented.

I think that being high rated in short competitions really means 2 things:

or

Maybe "That' why you're purple" was oversimplification, because at any point I didn't want to address the actual smartness or abilities to code some particular thing, so I would like to cut out part of the discussion regarding to being smart, having a lot of practice, having developed library etc. which are of course important factors of someone's colour, but they were not what I was going to point at what may have been a reason for a little misuderstanding.

Only thing I wanted to focus on was the attitude when facing problems. From my own experiences I can say that difference between purple me and red me is surely also a lot of practice, but also very importantly revolutionizing my way of thinking. No matter of someone's current abilities to code and smartness, "I am not able to do this, so I won't even try, good luck" attitude is a place for severe improvements (no matter whether "I am not able to do this" part relates to coming up with solution (which connected with "so I won't even try" never has been my point of view) or coding a solution (which was exactly exactly very often my point of view in past and I am not happy with this, but fortunately it is no longer the case)). My initial comment's main purpose was in fact to be a purely motivational one.

Btw on a completely irrelevant note, you made it seem like copying prewritten code is essential part of today's competitive programming. In fact (apart from template) I copy some codes from library in approximately one in 20 problems.

My personal red experience is that "whatever you say can be used against you", that is, no matter how careful you are, something you say is going to be perceived as arrogant by someone (hell, some people told me they thought I was arrogant before they had the chance to talk to me!). So I'd say at least a large part of this discrimination you mention can be attributed to the lower-rated contestants themselves.

That being said, here's a simplified version of Swistakk's statement:

"Programming contests consist of coding and implementation, so if you want to be a very good contestant you need to practice both, not only one of them".

Sounds like really good advice to me (and I should follow it more often, my implementation skills are crap)

Could you givgive an example of such a problem (requiring all techniques you mentioned)?

what is wrong with my code it is failing on test 5 http://sprunge.us/iFNf? THe code is for problem D.

I think, we cannot simply divide like this:

`second = (B*((tmp-1l)/(A-1l)))%MOD;`

Probably there is a smarter way to deal with modular division.

(a/b) mod m is not equal to a mod m / b mod m so you cant divide by (a-1) so easily. you should use modular inverse

Instead of dividing (tmp-1) by (A-1) directly, (tmp-1) can be multiplied with the modular inverse of (A-1). UPD: I did this but my solution got hacked anyway.

Here Scroll down to the modular inverse part!

By Euler's theorem, you can use

`((divisor) ** (mod - 2)) % mod`

to divide if`mod`

is prime. In this case, divisor would be (a — 1) and mod would be 10 ** 9 + 7.https://en.wikipedia.org/wiki/Modular_multiplicative_inverse

That N = 1 case in E. -_-

Same :/

How to solve problem E?

i think dynamic programming, like hamiltonian cycle but i

`m not sure, i couldn`

t make it pass test 4http://codeforces.com/contest/678/submission/18433012

I tried DP, but its complexity is bad.

You need to find an order which maximizes your probability of winning. This is a standard Bitmask DP.

My solution : code

What to search for to get this standard dp problem?

Your code is a little messy , so can you tell me the DP states you used?

Lets define DP[mask][prev_winner] as the max probability such that we have covered people in mask and prev_winner is our winner.

Now we try N * (N — 1) possibilities for first 2 position and try to find the max ans.

Transition is :

if prev_winner = 0:

DP[mask][prev_winner] = max(prob[prev_winner][i] * DP[mask | (1 << i)][prev_winner]) for all i's which we have not seen.

else:

DP[mask][prev_winner] = max(prob[prev_winner][i] * DP[mask | (1 << i)][prev_winner] + prob[i][prev_winner] * DP[mask | (1 << i)][i]) for all i's which we have not seen.

I hope this helps.

I thought we have to consider two disjoint subsets and use their maximum values for the union of these subsets. I can't prove why we only need first two positions. I'm missing something very obvious, possibly.

I don't understand these formulas:

"DP[mask][prev_winner] = max(prob[prev_winner][i] * DP[mask | (1 << i)][prev_winner]) for all i's which we have not seen."

It means that in order to cover people in mask you look at all the masks with one more people, you ask what is the probability that 0 will win among all these people and then you calculate the value for the mask with the smaller amount of people. It looks like your final state is dp[0][0]?

Final state for DP is dp[(1 << n) — 1][0]. I add one more person into mask and ask what is the probability that the person I want to win is the winner. And I split the dp based on whether I have seen 0 or not. So above formula is for the case when I have seen 0 (what is the probability that 0 is the winner when I add one more person into mask). Other formula covers the second case as both of them can win.

A simple way is to set dp[mask] = best probability for Ivan to win among people with bit=1 in the mask.

18433677

How do you prove that only mask is important? I believed that the last winner is also important, but stress-test of your solution says that it isn't.

I choose two fighters to move between dp states, maybe this confuses you.

So basically for a given mask we can independently get the best probability of Ivan to win. To compute this, we take maximum over all possible choices for next fight (choice of two fighters, possibly including Ivan).

That's a nice solution, but it is very magical for me.

If you choose the last 2 people it is against the rules, as you can choose only 1 last person.

So if you are going to choose the last 2 people (i,j):

or

I don't know how do the people come up with such ideas, but is there a way to do this problem more straight forward?

Like you have the probability dp[mask] that Ivan wins the mask or dp[mask][winner] that winner wins the mask and you are selecting one player in each move?

Despite being more straight forward, that solution would also reduce the complexity to O(n*2^n).

Edit — it will reduce the complexity only in case with dp[mask] state.

Edit2. Now I see that you are not choosing the last fight, as you can't do that. Ivan has to fight the last fight in each mask. You are choosing the best fight among all possible fights within the mask and you take the sum of 2 different outcomes of it. It is more clear now.

Actually now I realized that I forgot that the winner from the last fight

hasto be chosen. That is, my solution assumes a tournament, where there are multiple fights with elimination in parallel.So I solved a different problem and that's why the solution seemed clear for me (and unclear for others).

It is quite strange that this got AC.. Maybe it could be hacked? Though, intuitively, it would fall on large random tests, which I assume already exist in the set.

Maybe this works because the strategy from the problem is indeed optimal? :)

Your solution works because:

dp[mask] = maximum probability that Ivan wins the mask.

If there is no Ivan in the mask dp[mask] = 0.

If there is Ivan in the mask, you choose the best tournament in that fight. You have 2 cases here:

a) You choose 2 fighters without Ivan and I explained that case above. That fight would happen in any but last position — my explanation covers that too. But to make it more clear: you don't care at which stage that fight would happen, the point is that the winner of that fight would be defeated by Ivan later.

b) You choose Ivan and another fighter — that fight has to happen as the last one.

So you evaluate the fight between 0 and i.

So your formula will take dp[mask^1]*prob[i][0] and this is 0, because dp[mask^1] = 0

Which is exactly what we want.

That's why I said that it is a great solution with memory O(2^n) and was very impressed how did you manage to come up with this reasoning during 2 hours. It's interesting to see that you were thinking of something different :P

this explanation is wrong, lol

That's what I wrote in case a). In case b) you are adding the new candidate to the mask. The mask is already beaten by Ivan — so it will be the last fight with new candidate.

Are you sure every sequence can be made into a chain? For instance, what about 3 beats 4, 5 beats 6, 2 beats 3, 2 beats 5?

And even if that transformation is possible, the sequence of fights is not determined in advance (because as you said you can change it depending on prior results), so you wouldn't necessarily know what transformation to use.

It's very interesting that this solution works, but I think the explanation why is not that simple...

I'm not sure about a chain, but I can't see what is the problem with my explanation.

It is clear that you choose the most profitable battle. If Ivan is engaged, it is the last battle, no matter what was the order of the other battles.

If he is not engaged, that battle is not last, as the winner of it got already beaten by Ivan in the state we have calculated. So we can insert it everywhere, but the last position.

Your example doesn't include Ivan and for such case the solution immediately outputs 0.

I was replying to dalex's explanation, not yours, which I only read now. As far as I can see, you don't address the requirement that the winner of the last fight has to be part of the next fight.

Because we already reached the discussion depth limit — it is hard to say to which answer was the reply.

That requirement is addressed in the following way:

If Ivan won the last battle, he obviously will be participating in the next one.

Below part was edited:

I got lost in one case.

If you choose the battle between (i,j) and i won that battle. You know that in the dp[mask^(1<<j)] he was defeated at some point (as Ivan won the whole mask^(1<<j)). You insert that battle after the last battle won by i in mask^(1<<j) (which means that after i's victory we invite j to fight with him).

If i didn't win anything in mask^(1<<j):

a) If he lost in hist first fight, then add battle between i and j on the first position.

b) Otherwise there exists k, who defeated i and k had to win at least one battle (as i didn't loose the first fight). Let's say that k defeated r just before defeating i. And let's assume that r also defeated m.

Now it is clear that i and j have to fight in the first fight, as i didn't win anything in mask^(1<<j). After (i,j) should fight (i,k) and after that (k,r) but r would be defeated by k and it has also defeated m...

I constructed a case by ffao, which ruined the explanation about chains: http://ideone.com/QYmfXx... or not? Look what it outputs for mask 31 (after 5 defeats 6).

My solution uses the same idea as yours, but I don't really know why it works! I just code it to see if it solved the problem, but I was skeptical. In my mask I store the participants that are dead, and try all possible pairs, and sum the combinations that result in only Ivan alive. The code turns out to be very simple but I don't know why it works! 18510404

can you tell me what i did wrong here, please?

http://codeforces.com/contest/678/submission/18433012

Reads comment and then realises that it's pointless.

I solved it using dp, Let f[s][i] be the probability that the jedi winns if s is the set of siths that are alive, and i the sith that won the last round. We can try over all possible siths j!=i, and over all possible outcomes (of the fight between i and j), of course we should chose the one that maximizes the probability that the jedi winns.

But don't you have to deal with two subsets each time?

Why two subsets? As you can see my recurrence use just one subset. Note that the set of died siths is the complement of the alive siths

two mutually exclusive subsets , with one winner of each subset, fighting in the current round which covers union of both subsets.

At least this is all I could come up with.

@Alei : I do nt get in ur dp how u are ensuring that 0th index is the last winner. could u pls elaborate how uve done that.. or how is it implicitly taken care of.?

ok got it now didnt read the base condition carefully.. very nice code :)

Tnx for providing us with your clear and simple solution. :)

in problem E, how the sample gives 0.68??

Stuff that can happen so 1st person win are:

1 win 2, 1 win 3

1 win 3, 1 win 2

2 win 3, 1 win 2

3 win 2, 1 win 3

All this happen with 0.49333 probability.

What am i missing?

Question asks to find the maximum probability which comes from this order 2, 3, 1.

2 wins, 1 wins : 0.4 * 0.5

3 wins, 1 wins : 0.6 * 0.8

Total prob = 0.2 + 0.48 = 0.6

Note that optimal choices can differ depending on the results of the previous battles. So talking about "order" is not correct.

PROBLEM C: It is wrong with my code?

z overflows try 1000000000 1000000000 1000000000 1000000000 1000000000

the solution change the data type of the input variables int a long long

You can do: a / __gcd(a, b) * b

To avoid overflows as the division will be carried out at first

Why do you need

`__gcd()`

? What are you trying to achieve with the variablez?find the number of numbers divisible by two numbers given

Interesting, I haven't thought about that. I've calculated that number with expression

n/ (a*b).It is good that the contest is not rated :)

Probably (na-nab)*p overflows, try (na-nab)*1ll*p (and same with q). Or simply use long long for all vars.

Thanks, the problem really was easier than last time. Maybe you had to swap B and C. UPD. Take back a words about the B and C after start of hacking.

I sent two solutions for problem B that got OK. One of them was hacked, the other wasnt. But the table says I havent solved this problem. Why?

Relax, the contest is not rated. Enjoy the moment =)

I wouldnt allow anyone to hack my solution in a rated contest))))

C was solved by 1500+. now it has become 900+. #HackEffect

Can someone tell me why my solution fails for C?

Compiler got confused by

`cnt`

and`abs`

, so it gave up =)You can't just divide by (b * c), it should be GCD(b,c). Consider this input: 6 2 4 1 3 Your code gives 6 as an answer, where it should be 5. Edit Wrote 3 instead of 6, corrected.

Not gcd, but lcm

My first hacking attempt and i hacked 15 solutions for problem C

You forgot to hack yourself))

How could problem D be solved using matrices?

why a[1][0]=0 and a[1][1]=1??

Simpler way: you can exponentiate

fitself: f^2 = (a*a)*x + a*b+b. Then use fast exponentiation to compute W,R from f^n = W*x+R:Python code:

What is the hack case for D?

My solution is to find value

A^{n}·x+ (1 +A+A^{2}+A^{3}... +A^{n}) *B. To find sum of GP, I use the standard formula with an exception case where A = 1, when GP sum = n. What is wrong with this 18423561UPD: Mine was hacked due to overflow of GPSUM*b in special case as I forgot to take modulo with n and it overflowed even long long :(Overflow in gpsum * b is the problem here. I made the same mistake :(

I am getting overflow in Java7 at problem C when running this test : 1000000000 1 3 1000000000 999999999 My code: https://ideone.com/kHjrJT

Any idea?

EDIT: Now I see that I was not the only one facing this problem. I changed every variable from int to long and now everything seems to work. God, I hate when this happens. But better here than IRL.

if operands are int, then result is int. So in pieces:

overflow exists. Two possible solutions:

1) Make all operands long-type;

2) Add 1l literal:

1l — is long-type const so during multiplications overflow wouldn't appear.

My god, problem C is a pure hacking bloodbath...

I want some advice about hacking. Sometimes the contestant doesn't initialize a variable, so it contains a garbage value, which might give WA. What should I do in such cases, is the garbage value machine dependent or is it some fixed value?

This thing happened in last CF round, one solution didn't initialize a variable, and he was taking max of it with another variable. Fortunately for him, the garbage value was some large negative value, so I couldn't hack him. I would have hacked if the garbage value was some large positive value. What to do in such cases?

I shall advice u properly tomorrow..just wait...

What's the idea for problem F?

I instantly came up with the idea of using a fully dynamic convex hull and then evaluating at certain coordinates. I coded it and debugged it without thinking, only to fail at Test #9. Then I thought a little bit and I realized that when deleting a line, some lines that were removed earlier because they weren't relevant anymore, might become relevant again, so I'm not sure if fully dynamic convex hull is something we can do.

I still don't know how to solve it.

I think you can solve it without fully dynamic convex hull. Just process queries by blocks (block can have

sqrt(n) size, but this is not the best choice). Build convex hull on previous blocks (without deleted pairs in current block of course). Then lookup answer for query inO(sqrt(n) +log(n)).O(n*sqrt(n)) for all.I think it is good solution, but I am too lazy to check it today =D

One solution is that: for each line there is an interval it exists. So, build a segment tree each node contain a convex hull. See link. The other one is sqrt decomposition query. Build a convex hull at each block!

Huh, I haven't written a single task using either of those techniques, guess I have to try :)

What does "Unexpected verdict" mean for my hacking attempts #236256, 236261, and 236265?

UPD: fixed.

i hacked myself in problem D due to this- ans = ((b%mod * n %mod)+x)%mod test case — 1 1000000000 10000000000000000000 1000000000

due to operator preference b%mod * n will take place first thus overflow!

in the test case you mentioned, the value for n is 10^19 which won't fit even in long long. I think you meant to type 10^18.

there will be no tutorial for this round?

http://codeforces.com/blog/entry/45405

Where is the editorial for fifth question??

When i run c number code on my laptop it answered me 813.But why codeforces answered 625?

## include<bits/stdc++.h>

## define ll long long

## define sf scanf

## define pf printf

## define end return 0

## define d double

## define f float

## define b break

## define c continue

using namespace std; int main() { ios::sync_with_stdio(0),cin.tie(0); ll m,n,o,p,q,a=0; cin>>m>>n>>o>>p>>q; a+=(m/n)*p; a+=(m/o)*q; a-=(m/(n*o))*(min(p,q)); if((n*o)>m) if((m!=1)&&(((m==n)&&(!(m%o)))||((m==o)&&(!(m%n))))) a-=min(p,q); cout<<a<<endl; end; }