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.

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

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

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

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

At least.

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

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

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.

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

Same :/

i think dynamic programming, like hamiltonian cycle but im not sure, i couldnt make it pass test 4

http://codeforces.net/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

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.

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

z overflows try 1000000000 1000000000 1000000000 1000000000 1000000000

Why do you need __gcd()? What are you trying to achieve with the variable z?

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

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

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.

You forgot to hack yourself))

a[0][0] = A;
a[0][1] = B;
a[1][0] = 0;
a[1][1] = 1;

this matrix multiplying with  
[x 1] gives [A*x+b 1] and we can repeat this process..

Simpler way: you can exponentiate f itself: f^2 = (a*a)*x + a*b+b. Then use fast exponentiation to compute W,R from f^n = W*x+R:

Python code:

cur = x
while n > 0:
    if n & 1:
        cur = (a * cur + b) % MOD
    a, b = a*a % MOD, (a*b + b) % MOD
    n >>= 1
print cur

Overflow in gpsum * b is the problem here. I made the same mistake :(

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

long nr = a * b;  
...  
sum = sum.add(BigInteger.valueOf(Math.max(p, q) * x));

overflow exists. Two possible solutions:

1) Make all operands long-type;
2) Add 1l literal:

long nr = a * 1l * b;  

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

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

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.

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!

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.

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