Codeforces Round #338 (Div. 2)

9 years ago, # |

Registration open during contest ? Is it indended or is it a bug ?

→ Reply

C137

9 years ago, # |

+48

Should be called hello 2016...

→ Reply

Xephy

9 years ago, # ^ |

← Rev. 3 →

Just wait for PrinceOfPersia to prepare another Hello 201X contest.

→ Reply

Hacliker

9 years ago, # ^ |

Maybe "cheers!2016" is nicer... Dala!

→ Reply

G_Hani

9 years ago, # |

+10

hope it will be good first round for you guys

→ Reply

Bat-Orgil

9 years ago, # |

Good luck to all of you! Hope you'll have fun with the first contest in 2016 :)

→ Reply

Ahmed_Hussein_Karam

9 years ago, # |

← Rev. 3 →

Sorry, I didn't have that long experience on codeforces. What's really that polygon for which you always thank MikeMirzayanov, TheWishmaster ?

→ Reply

Xephy

9 years ago, # ^ |

-18

The platform that contests are hosted at. Their own, handwritted (handbuilt?) Ejudge. A pretty neat thing, if you ask me. Link.

→ Reply

MikeMirzayanov

9 years ago, # ^ |

Polygon (https://polygon.codeforces.com) is a system to prepare programming problems and contests. It is used for each Codeforces round, but not only: many other contests are prepared in Polygon.

→ Reply

randomstr

9 years ago, # |

+24

A lot of Legendary grandmasters will take part in this round!

→ Reply

EnumerativeCombinatorics

9 years ago, # |

I'm currently a blue coder because of the Magic (my actual rating is 2510). Can I take part in this contest as a Div2 Contestant? Is it rated for Magical Div2 coders?

→ Reply

A.Magdy7

9 years ago, # ^ |

-17

i think it depends on your rate not on your color and if what you say is right most of Div2 contestants will not be able to participate in this contest as they change their color into red "or any other Div1 color" and in this case this contest will change from Div2 contest into Div1 contest XD except form a few contestants who doesn't change their color XD

→ Reply

I_Can_Do_It

9 years ago, # |

First time participating as a Legendary grandmaster :D thanks Codeforces for this opportunity :)

→ Reply

drd93

9 years ago, # ^ |

← Rev. 2 →

First time as Legendary Grandmaster as well for me! Feeling so nervous ^_^

→ Reply

Gilmour

9 years ago, # ^ |

← Rev. 2 →

That magic just changes the color of your name . that's all . it doesn't make you a real legendary grandmaster ! :))

→ Reply

allllekssssa

9 years ago, # |

I bet this will be the first contest when I will hack Legendary Grandmaster :)

Good luck to setters, my frist round as setter (and the only one in the cf) was very stressful :)

→ Reply

BloodMaster06

9 years ago, # |

-32

orzdyh orzjc orztourist orzWJMZBMR ORZ TooDifficult 23333333

→ Reply

9 years ago, # |

Score distribution pls?

→ Reply

shubham95

9 years ago, # |

hope good rating this time

→ Reply

shivamd

9 years ago, # |

I missed the registration due to unusual time. Can i any how give the contest now ??

→ Reply

firmsnail

9 years ago, # |

Why do you change the time limit in problem C without notification?

→ Reply

9 years ago, # ^ |

We were not changing any constraints or time limits during the contest. However, they were changed just before the contest, so it may happen that you got old version because of caching. We apologize for the inconvenience.

→ Reply

firmsnail

9 years ago, # ^ |

It's strange. I've seen that the time limit of Problem C is 1.5s when I open the page of Problem C first time. I submitted the problem and got TLE, and I found my program just run 1000ms. So, I check and confirm the time limit is 1.5s. But when I refresh the page, the time limit had been changed to 1s.

→ Reply

9 years ago, # ^ |

Do you have O(N * N) complexity?

→ Reply

firmsnail

9 years ago, # ^ |

Yes

→ Reply

SandorGarcia

9 years ago, # ^ |

← Rev. 2 →

This is a very serious issue, my rating was not affected by this because I am in div 1, but it changes a lot in a solution with hash to have 1.5x time and the time hints about the level of optimization required. Please try to design a way to prevent this from happening in the future (all people should read the same statements)

PS: If it wasn't obvious I also got the 1.5seconds time limit

→ Reply

MaxEinstle

9 years ago, # |

← Rev. 2 →

-20

In one of my hacks i recognized that the person is printing "Yes" instead of "YES" .. i thought i will get it but i was penalized for it. can we print in any format other that that was specified in the problem. the problem A is clearly saying to print "YES" and "NO". Please look into it

→ Reply

cool_handle_much_wow

9 years ago, # ^ |

+31

I guess the checker is case-insensitive. How do you think that person's solution would pass the pretests if the checker was indeed case-sensitive?

→ Reply

MaxEinstle

9 years ago, # ^ |

← Rev. 2 →

-20

maybe.. but i got -50 because of that and i thought maybe the pretest didnt have any answers with "yes" sometimes they leave out many cases in pretest so we can hack

→ Reply

MikeMirzayanov

9 years ago, # ^ |

+15

There is a special note on the hacking form: "Attention: the most checking programs ignore whitespaces and case of keywords (e.g YES/yes, NO/no, etc.) while judging participant's output".

→ Reply

MaxEinstle

9 years ago, # ^ |

Oh sorry for my comment then .. Thanks for clarifying

→ Reply

9 years ago, # |

← Rev. 2 →

Hm, for me E was easier than C and D :)

UPD: Actually I think its even easier than B too. Just a bit hard implementation because of math on big numbers. It has no complex algorithms or hard ideas, just obvious pattern and mid school math.

→ Reply

9 years ago, # ^ |

but i cant find the pattern. can you tell me?

→ Reply

9 years ago, # ^ |

Instead of thinking them as hexagons, think of them as squares.

Now, after 6 steps, it will be on x-axis. Just take it from there. n%6

→ Reply

saurabhsuniljain

9 years ago, # ^ |

You just nailed it!!!

→ Reply

9 years ago, # ^ |

-10

The only thing I nailed is A. I solved D, but I can't code it. B is fucking beyond me. I dind't even read C. I only read E after I read Beresta's comment, and since I'd already fucked the round up, I didn't have much hope left. Besides, what's the point in having something so div2A disguised as div2E

→ Reply

binary_eagle

9 years ago, # ^ |

I don't think B should be beyond you. You are a candidate master. I understood and solved it.

It is just find the longest path length that ends at node i. This can be found with dfs.

Then multiply this with the number of neighbors of i.

Maximize this value over all nodes i.

→ Reply

9 years ago, # ^ |

umm.... he isn't a candidate master :v check his profile

→ Reply

9 years ago, # ^ |

The approach I came up with for B is not pretty.

First, you have to do a DP on tree using DFS to calculate contiguous segments. Then, you have to take care of bends(reverse logic of the previous dfs). Store bunch of things, like endpoints, degree of each node, etc.

It just didn't feel like div2 B.

Besides, I may be wrong.

→ Reply

9 years ago, # ^ |

you just have to do the dp using dfs and store the degree. Taking care of bends, storing endpoints are not necessary

→ Reply

9 years ago, # ^ |

← Rev. 2 →

So if the root of tree is 3, and one branch has 2,1 and another branch from root has 4,5 what will you do then?

→ Reply

9 years ago, # ^ |

← Rev. 2 →

the idea is to start iterating from the maximum node. first you take 5 and and calculate the maximum obtainable tail ending at 5 , store the value in dp , multiply it by degree. then continue doing this for 4,3,2,1

→ Reply

9 years ago, # ^ |

Yeah, that's how you handle bends.

→ Reply

9 years ago, # ^ |

Got it! Thanks :)

→ Reply

9 years ago, # ^ |

← Rev. 2 →

So, on each iteration we do a full cycle around the last spiral starting in right-bottom corner. Full cycle done in 6 steps (move top-right, top-left, left, left-bot, bot-right, right). All these steps except second will have the same length, each cycle increasing by 1. Second step has one hex less length.

So on Nth iteration we will do (6N-1) steps to made a cycle.

So from progression formula it will be (3N+2)*N steps to made N iterations.

From input we substract full cycles by solving the equation. After that just do at max 6 more steps to finish remaining steps.

The solution is O(1). Most hard part is to mess with big numbers.

Passed pretests and I done some testing manually, so 90% sure it is correct. Will be 100% after system testing :)

→ Reply

9 years ago, # ^ |

Well, got WA on #103 :)

→ Reply

9 years ago, # ^ |

Messed up with big numbers in that one. Small fix and now it is AC.

So, the algorithm is correct, just messed up with implementation.

→ Reply

kanade

9 years ago, # ^ |

Why problem E problem E?

→ Reply

9 years ago, # ^ |

I just read the problem in the last few mins, after solving D (I didn't attempt C first), and realize that it is quite easy -_-

→ Reply

Emilbek

9 years ago, # |

How to solve B?

→ Reply

9 years ago, # ^ |

← Rev. 2 →

-31

I didn't solve B. I think C was easier than B

→ Reply

fauzdar65

9 years ago, # ^ |

Iterate over each vertex and fix it as the end of tail. Now however long the tail you choose(ending at current vertex) the spine will be same, which is the number of edges originating from current vertex. So, that value needs to be multiplied with dp[x], which is the longest decreasing sequence originating from current vertex. You can precompute dp easily in O(N).

→ Reply

9 years ago, # ^ |

Thank you! With that description I managed to get the solution without the graph structure 15261877.
Very beautiful :)

→ Reply

9 years ago, # ^ |

my solution is
for node 1 to N
it can be a node of a tail(a,b,c...N)
a<b<c<...<N
can build max tail for each node

ans is max (len(max_tail[N]) * connection[N])

→ Reply

9 years ago, # ^ |

← Rev. 2 →

my solution is wrong because i compare int and long long

→ Reply

Reayz

9 years ago, # ^ |

Yeah, there are my two submissions: 15258474 and 15258091

→ Reply

9 years ago, # ^ |

+14

B is killing me.

I've spent like 20 minutes reading and reading and reading the statement. So overwhelming.

And after that got hacked 5 mins before the end, couldn't figure out whats wrong with my solution in that time.

→ Reply

9 years ago, # ^ |

← Rev. 2 →

Oh my god, stupid overflow of int32. I don't really want to see my rating change after this contest. Solved A, B, E but because of stupid mistakes have only A left.

It is so awful. Place #2832.

→ Reply

internom

9 years ago, # ^ |

← Rev. 2 →

Me too but got WA on system test. Translation of problem B was blunt. I think the test case which yours was hacked is this one.

Expected Answer: 9

After contest I figured out that tail can be only one point ( no segment :D ).

BTW problems were good.

Statement ( girl who translated the statement :D ) just trolled me ( maybe my English trolled me )

She wants to paint the tail that satisfies the following conditions: 1. Only segments already presented on the picture can be painted;

→ Reply

9 years ago, # ^ |

The contestants mostly got hacked because they used int, I also got hacked 10 minutes before the end and was completely dumbstruck. But then I changed the final ans to long long and got AC. And during system test , many people failed on B. I checked some of them and they all had this overflow issue

→ Reply

internom

9 years ago, # ^ |

← Rev. 2 →

I'm sure many got WA because of overflow. But the statement was evil for people who reads carefully.

She wants to paint the tail that satisfies the following conditions: 1. Only segments already presented on the picture can be painted;

This means, To paint a tail then paint segment o.o. Problems were good but translation was bit dummy. Any Thanks for great platform. Good luck to all :D

→ Reply

promix17

9 years ago, # |

← Rev. 2 →

What was 3-d pretest for D? Can't detrmine whats wrong...

→ Reply

wineColoredDays

9 years ago, # |

Extremely weak pretests in D killed me today :(

→ Reply

Deemo

9 years ago, # |

What is the hack test for problem D!?

→ Reply

VastoLorde95

9 years ago, # ^ |

← Rev. 6 →

+18

Contestant's mistake: (a^b)%MOD ≠ (a^(b%MOD))%MOD

What it actually is (a^b)%MOD = (a^{(b%(MOD - 1))})%MOD

Contestants solution were working if b < MOD - 1

→ Reply

Bekmyrat.A

9 years ago, # ^ |

← Rev. 2 →

could you please explain why to use b%(mod-1)
my solution also failed for that reason.

→ Reply

9 years ago, # ^ |

Little Fermat Theorem. a ^ (p — 1) is 1 mod p, and you can avoid groups of length (p-1) in multiplication because they are equal to 1.

→ Reply

VastoLorde95

9 years ago, # ^ |

← Rev. 7 →

By Fermat's Little Theorem we get that

a^p - 1 ≡ 1%p, so if b = n × (p - 1) + r, then,

a^b → (a^{n × (p - 1) + r})%p

→ (a^{n × (p - 1)} × a^r)%p

→ (a^{n × (p - 1)})%p × (a^r)%p

→ 1 × a^r%p

Here r = b%(p - 1)

→ Reply

9 years ago, # ^ |

-12

Except carmichael numbers

→ Reply

anakot

9 years ago, # ^ |

I got the formula right, but used inverse of 2 while calculating (a ^ (p/2)%MOD-1)%MOD. It got WA. Why ?

→ Reply

VastoLorde95

9 years ago, # ^ |

That is because 2 and 10⁹ + 6 are not co-prime and inverse exists only if the pair of numbers is co-prime.

→ Reply

http://codeforces.net/contest/615/submission/15249100

9 years ago, # ^ |

← Rev. 2 →

I used some value and understood that (a^b)%MOD ≠ (a^(b%MOD))%MOD

but couldn't understand what would be the alternative. could u explain why (MOD-1) ?

(upd) just saw your reply, thanks

→ Reply

kshitij_jain

9 years ago, # ^ |

I took MOD -2 :(

→ Reply

radoslav11

9 years ago, # |

Very well prepared round and the problemset was good! :)

→ Reply

wfe2017

9 years ago, # |

← Rev. 3 →

-41

Hmmm what's wrong with the code here?

→ Reply

poikniok

9 years ago, # ^ |

+14

Please don't paste in long code, link to submission.

→ Reply

9 years ago, # ^ |

← Rev. 6 →

Please, use pastebin, ideone, paste.ubuntu or github for your code.
It would be much better to read your code there.

→ Reply

saurabhsuniljain

9 years ago, # |

How to solve D??

→ Reply

gepardo

9 years ago, # ^ |

+11

Use formula:

p(n) = n ^ (d(n) / 2)

where: * p(n) is multiplication of all the divisiors of n. * d(n) is count of divisors.

→ Reply

9 years ago, # ^ |

but, why?

→ Reply

drd93

9 years ago, # ^ |

So how do you calculate the number of divisors fast?

→ Reply

kingofnumbers

9 years ago, # ^ |

← Rev. 2 →

n=p1^e1 * p2^e2 ... pk ^ ek

number of divisors is (e1+1)*(e2+1) .... *(ek+1)

→ Reply

Iskandarov_Islom

9 years ago, # ^ |

it`s not quite correct for example: 2 3 3

d(n) = 3 d(n) / 2 = 3 / 2 = 1 9 ^ 1 = 9 the correct answer is 27

→ Reply

zdolna_kaczka

9 years ago, # ^ |

Well, in maths 3 / 2 = 1.5, and 9^1.5 = 27, so mathematically speaking it is absolutely correct.

→ Reply

Iskandarov_Islom

9 years ago, # ^ |

thank you for answer now I understand

→ Reply

9 years ago, # ^ |

← Rev. 3 →

Formula.(I think this is the formula. Feel free to correct me)

let k=frequency of a prime

then, ans=product of((prime^(2^k-1))^(sum/f(prime)))

sum=product of(frequency of prime+1)

f(prime)=frequency of prime+1.

→ Reply

9 years ago, # ^ |

Still waiting for someone to correct me.

OMG!! this can be easily coded with modular exponentiation ;_; .

→ Reply

9 years ago, # ^ |

← Rev. 2 →

-16

Ignore

→ Reply

MahanZDH

9 years ago, # ^ |

+10

If n is not a perfect square, then every divisor d1 can be paired with the divisor n/d1, which is distinct from d1; the product of these two is n. So the product of all divisors is equal to n^k, where 2k is the number of divisors. (Note that a positive integer has an odd number of distinct divisors if and only if it is a square).

If n is a perfect square, then it will have 2k+1 divisors for some k; the product will be n^k×√n=n^(k+0.5).

→ Reply

bhishma

9 years ago, # ^ |

Yeah I saw something similar in Math Stackexchange link : http://math.stackexchange.com/questions/24126/what-does-the-product-of-all-proper-divisors-equal-to

→ Reply

9 years ago, # ^ |

← Rev. 2 →

+13

First of all you want to bundle all primes with the same value. You now have n = p₁^e₁p₂^e₂...p_m^e_m

All divisors must be written in the form d = p₁^f₁p₂^f₂...p_m^f_m, where 0 ≤ f_i ≤ e_i.

Then we know that the product of all divisors d is:

$\text{[math]}$

We see that all factors from i₁ to i_m - 1 are not depending on i_m so we can put them outside the last product when we raise it to the (e_m + 1)'th power. In fact we can repeat this process for every term, and so we can split this product into m terms to get the following result:

$\text{[math]}$

Which is equal to:

$\text{[math]}$

The inner product should be calculated by using two precalculated tables:

One table for the products from i=0 to i=j-1

One table for the products from i=j+1 to i=m-1

To prevent overflow, everything in the exponent of p_j can be taken modulo 10⁹ + 7 - 1, using Euler's theorem.

→ Reply

fofao_funk

9 years ago, # ^ |

How could we apply modulo 10⁹ + 7 - 1 in the exponent of pj, since we have a division (by 2) and 2 and 10⁹ + 7 - 1 aren't coprimes?

→ Reply

9 years ago, # ^ |

e_j is at most 200000, so we calculate e_j·(e_j + 1) without using modulo because it won't overflow. Then you can divide by 2 because it will either divide e_j or e_j + 1. Then after multiplying with the product you can take the modulo.

→ Reply

fofao_funk

9 years ago, # ^ |

Hmm... So if we have an expression like (a / b) % c, we can always divide a by b before taking the modulo if b divides a?

→ Reply

9 years ago, # ^ |

Correct! But if you calculate a by some crazy formula, you must check that it won't overflow. In this case, you must use long longs for calculating e_j(e_j + 1). Otherwise it might overflow for large e_j and then the value is negative, and might not be divisible by 2 anymore.

→ Reply

fofao_funk

9 years ago, # ^ |

Got it! Thank you a lot for your explanations!

→ Reply

9 years ago, # ^ |

I've done EXACLY like this(or at least I meant to do so) but I get WA on test #12 which looks really easy, it is basically just 200 000 , 135391 's so we should print:

135391 ^ (sum of all numbers from 1 to 200 000) but still getting WA,code : 15258784

→ Reply

9 years ago, # ^ |

1LL * x * x * a van produce an overflow when both x andere a are very large, so you could mod 1LL * x * x before multiplying it with a.

→ Reply

9 years ago, # ^ |

Oh thanks

→ Reply

godmar

9 years ago, # ^ |

← Rev. 2 →

If you're using a language with fast enough arbitrary integer arithmetic, just compute the entire product. See 15259490.

→ Reply

daga

9 years ago, # |

In problem E i am getting wrong answer at pretest 2 but for the given test #2, i am getting right answer on my machine as well as on custom invocation. are they different test cases?

→ Reply

xuanquang1999

9 years ago, # ^ |

← Rev. 3 →

I have exactly the same trouble with you.

→ Reply

xuanquang1999

9 years ago, # ^ |

So, it's turned out that the second pretest is different from the second example. Never seen this in the past...

→ Reply

Kuzey

9 years ago, # ^ |

Compile your code with -O2

→ Reply

C137

9 years ago, # |

Nice problems, but bad performance by me :( I hope to do better next time :)

→ Reply

Jefe

9 years ago, # |

← Rev. 3 →

I think difficulty is:

A,D,E,B,C

At least for a math student. Although I somehow kept gettin WA on E. No idea why.

For problem D, if x is the number we just want $\text{[math]}$ . Unless x is perfect square, in which case we want $\text{[math]}$

→ Reply

anh1l1ator

9 years ago, # ^ |

-15

I don't know about E I read till D. So according to me, the difficulty was A < D~=C < B.

→ Reply

9 years ago, # ^ |

A~E<B

→ Reply

9 years ago, # ^ |

I'm sorry, if the question is silly, but how do you make these formulas here? :)

→ Reply

Jefe

9 years ago, # ^ |

You wrap the text in dollar signs. Like if it was a latex document.

→ Reply

Caviar

9 years ago, # |

How to pass the pretest 4 for D? I don't even figure out why I got WA.

→ Reply

9 years ago, # ^ |

I think it was a case for perfect squares because when i fixed my code for perfect squares it passed for pretest 4. Not totally sure though because I haven't checked the test cases manually yet

→ Reply

promix17

9 years ago, # ^ |

Fuck, I always compute sqrt(n*t(n)), but there are 2 sqrt by module p...

→ Reply

9 years ago, # |

Hey in the second problem what if tail is 2 and 5. then the spines will be 1-2, 2-5 2-8, 5-3, 5-4 ans should be 2*5 = 10?

→ Reply

9 years ago, # ^ |

only the edges from tail endpoint will be considered as spine . in this case the tail end point is 5 (maximum node value in the tail), so the spines in this case are 2-5, 5-3 and 5-4

→ Reply

wfe2017

9 years ago, # |

← Rev. 2 →

hmmm I don't see what is wrong with the code here: http://codeforces.net/contest/615/submission/15249100

→ Reply

PortgasDAce

9 years ago, # |

hello , you can give me solution B , thank you so much

→ Reply

Jefe

9 years ago, # ^ |

← Rev. 2 →

For each vertex x, find the longest increasing sequence ending in it, we save it in L[x]. We can do this with a dfs starting with the largest integer, and setting the maximum length of a sequence ending in x as 1 + max, where max is the longest sequence ending in a neighbour of x that is smaller than x. You can look at my submission for more details.

After that, we just have to calculate the maximum of d(x) * L[X]. Where d(x) is the degree of vertex x.

→ Reply

9 years ago, # ^ |

I don't know whether my solution passed yet, so I'll make a sketchy description.

Let's enumerate all the vertices. At every step of that loop we'll consider the current vertex as the beginning of the tail. Inside the loop we're going the grow our tail step by step using dfs. On each step, dfs processed the last vertex of the tail, so it must have the biggest number among those we've already encountered. If the current vertex we are processing is the last, then we can also count how many spines there are. The number of the spines is the number of the adjacent vertices to the current back of the tail. So, we multiply the current length of the tail and the number of adjacent vertices and store that number in some global variable. If, during our dfs processing we're encountering bigger beauty, then we update that global variable. DFS continues till it can find the next vertex with the number bigger than the current number.

If my approach is correct and there wouldn't be any beautiful descriptions of the solution, I'll make a more detailed description with pictures :)

→ Reply

9 years ago, # ^ |

No, I was wrong. Don't read that long text :)

→ Reply

9 years ago, # ^ |

By the way, it's a nice case to study Einstellung Effect :)

→ Reply

dummkopf

9 years ago, # |

+23

I think the English in the problems is really bad and misunderstood. Especially problem B: "The number of points", they said, seems to be confused! Is it better if we simply write "the point" or "index"? Moreover, "endpoints" couldn't be the last point, this is not the meaning of "endpoints". Fortunately, they have noticed this and announce other contestants. Anyway, it was such a difficult contest for me and there were a lot of fun. Thanks :)

→ Reply

winaichan263

9 years ago, # |

When does the editorial usually come out? Last time it came out as soon as the contest finished :)

→ Reply

9 years ago, # ^ |

recently it comes out real fast.so I don't think it will take more than "a few" hours

→ Reply

9 years ago, # ^ |

Usually we publish editorial immediately or in one hour after the contest ends. However, this time that may take a bit longer. Anyway, solutions for all the problems are already mentioned in comments.

→ Reply

9 years ago, # |

This time limit for C is a joke, isn't it? All solutions using hashing failed on test #20 due to TLE.. And difference between N^2 and N^2 * LOG is not huge....

→ Reply

codecracker4

9 years ago, # ^ |

same ! got tle on test #20 ... I assume they were expecting some trie based solution for that :|

→ Reply

Na2a

9 years ago, # ^ |

+11

Could be also solved by Z-Function.

→ Reply

SashaMN

9 years ago, # ^ |

← Rev. 2 →

I used only std::string member-functions, very easy and straigtforward solution.

Submission: 15255098 46ms.

→ Reply

Na2a

9 years ago, # ^ |

Greedy solutions works here?

→ Reply

SashaMN

9 years ago, # ^ |

It is easy to prove that it works.

→ Reply

DiegoAE

9 years ago, # ^ |

← Rev. 2 →

My solution was based on trie and I got TL anyway, 15252039. I think the time limit was very tight and it was not set taking into account Java solutions.

→ Reply

yoones.rezaei

9 years ago, # ^ |

My solution got ML on test #23. after changing vector(27) to map I got accepted in 900ms

→ Reply

radoslav11

9 years ago, # ^ |

Same here :(

BTW: wasn't the time limit = 1.5sec

→ Reply

9 years ago, # ^ |

We were expecting a very stupid solution, that does nothing except straightforward comparison of the strings. It works in 70ms on all tests. As for trie and hashing, we set the timelimit such that it will pass depending on it's optimality.

→ Reply

9 years ago, # ^ |

Exactly. I solved it in that way. But, I make a precalculation for saving some starting positions (for later finding longest match in a straightforward way)

→ Reply

9 years ago, # ^ |

Why was the timelimit changed from 1,5s to 1s ? Also, the sad thing is that on Good Bye 2015 hashes for n = 5000 were accepted and today for much smalled constraints they fail :(

→ Reply

9 years ago, # ^ |

+19

You are free to generate maxtest and use "run" tab to see how long does your solution work.

→ Reply

9 years ago, # ^ |

But... how? I've never known about such a feature o.O Where can we find it ?

→ Reply

nikitayusupov

9 years ago, # ^ |

codeforces.com/contest/559/customtest

→ Reply

SandorGarcia

9 years ago, # ^ |

Sorry for the insistence in the same topic but you seem to disregard the importance of the fact that different people get different statements. Assuming that the time limit didn't changed during contest and it is a caching issue the is is HUGE, today it was a 0.5 seconds difference but tomorrow it may be a last minute FIX on a bugged problem, and the worst is that the people affected have no way to know!

PS: Referring as to GlebsHP doesn't answers the Why was the time... ?

→ Reply

RetiredAmrMahmoud

9 years ago, # ^ |

my N^2 DP approach got stack overflow :D

→ Reply

aka.Sohieb

9 years ago, # ^ |

← Rev. 3 →

I solved it using Z algorithm and it runs in 77 ms in the worst case. 15255258

→ Reply

decoder123

9 years ago, # |

+12

Sorry to say..but a better indication of these line could fetch more AC's.

3.The numbers of points from the beginning of the tail to the end should strictly increase.

The number on the points from the beginning of the tail to the end should strictly increase.

The translation is no doubt awesome( The job you guys do is really good ..please don't mind) but this whole line changes the problem in a second.

→ Reply

9 years ago, # ^ |

Completely agree with you, but anyways is a great problem.

→ Reply

9 years ago, # ^ |

Exactly. I understood this line after 15 minutes of reading the problem

→ Reply

rtheman

9 years ago, # ^ |

Yes, initially I thought that there are no cycles. "Number of points increase" :P

→ Reply

Bleuj

9 years ago, # |

← Rev. 2 →

Problem E saved some people :)

→ Reply

allllekssssa

9 years ago, # |

← Rev. 2 →

I must say the problems are pretty nice ;) I spent two interesting hours of coding.

But I can not tell that I like third task, I can not understand why we should print anything more than number of needed strings s. For me that change task from nice to boring.

And yes, I hacked one Legendary Gradmaster :D

→ Reply

9 years ago, # ^ |

-8

Hahaaha, you hacked forcer. He is fake Legendary Grandmaster

→ Reply

allllekssssa

9 years ago, # ^ |

No way, I was sure he is real Lagendary Grandmaster :(

→ Reply

9 years ago, # ^ |

Hope one day you will do it ;)

→ Reply

9 years ago, # |

link Can someone help me?

→ Reply

masterwayne

9 years ago, # ^ |

Take 1LL while calculating final answer

→ Reply

9 years ago, # ^ |

it makes me very very upset.

how can i avoid this?
should i define int long long int?

→ Reply

Reayz

9 years ago, # ^ |

There are my two submissions: 15258474 and 15258091

→ Reply

P_Nyagolov

9 years ago, # |

+15

I liked the problems, they were very nice but I hate B's statement.

→ Reply

9 years ago, # ^ |

I think it's safe we all did :-(

→ Reply

http://www.codeforces.com/contest/615/submission/15255459

9 years ago, # ^ |

Here's how I got B's statement.

1) Read the problem statement (WTF) 2) See the picture below (eh?) 3) Read the problem statement again (getting the hold of it) 4) See the picture again and compare with my understanding (oka, time to code)

though I got WA first, then got pretest passed, then got HACKED :v , and at the last moment got the right solution

→ Reply

P_Nyagolov

9 years ago, # ^ |

Eh, I forgot to use the current vertex in the dfs and got TLE (unfortunately it passed pretests ... ) :D :D :D

→ Reply

masterwayne

9 years ago, # |

For the problem B i just sorted all the edges according to source and destination and then i just iterated over all of them with maximum length tail that can formed by keeping the starting and ending point of that particular tail and it passed :)

Though it is in practise now because i didnt took 1LL while i was calculating result so its got overflowed :(

→ Reply

fnf47

9 years ago, # |

Ratings updated

→ Reply

gepardo

9 years ago, # ^ |

It is funny that for unrated people color wasn't changed:

→ Reply

dush1729

9 years ago, # |

-9

And i rise again, just because i solved A fast enough. :D

→ Reply

9 years ago, # |

Is there a way to get a full test case? I got wrong answer in problem C at test case #20 and I really don't know why.

→ Reply

9 years ago, # ^ |

Nevermind, found my silly mistake

→ Reply

aka.Sohieb

9 years ago, # |

Could someone tells why this gives WA!! what I missed here?! problem D 15242486

→ Reply

Amirnasr

9 years ago, # ^ |

number of divisors will overflow

→ Reply

AlluMihu

9 years ago, # |

What happened to problem B? I left it with all test passed after 1 hour and a half then I had to leave my pc and now I see that I got TLE on test 34.. Did you reevaluate the sources?

→ Reply

Arafatistic

9 years ago, # ^ |

After contest will be system tests, there are about 100 test, if your solution will not pass one of them it will be wrong answer. That's codeforces system testing! ^_^

→ Reply

9 years ago, # ^ |

It passed only pretests, which is only a part of the entire test set.

After contest ends, all solutions are running through full test set.

→ Reply

Elise

9 years ago, # |

Solved A and B and then spent over 1 and a half hour on problem D and couldn't pass test 12. My approach was:

Knowing that n = p_i^x_i * p_i+1^x_i+1 * ... * p_k^x_k, I tried to look at each p_i and count how many times it's used in d(n), the multiplication of all divisors of n. My goal was to find d(n) as p_i^y_i * p_i+1^y_i+1 * ... * p_k^y_k, multiply it all and find the result MOD 10^9+7.

For each p_i we have y_i = sum(1 to x_i)*((1+x_1) * ... * (1+x_(i-1)) * ... * (1+x_(i+1) * ... * (1+x_k)). You can use p_i from 1 to x_i times and for each p_j != p_i you can use it from 0 to x_j times to build one divisor of n.

Someone used the same approach and passed test 12? Or can you point me where I'm wrong? This problem is killing me.

→ Reply

aeremin

9 years ago, # ^ |

y_i can overflow (e.g. we have 100 different primes in input), y_i will be more than 2^99. It should be calculated modulo 10^9 + 6.
AFAIU you will get TLE if you will calculate each y_i separately.

→ Reply

Elise

9 years ago, # ^ |

← Rev. 3 →

Oh, I was considering (a^b)%MOD == (a^(b%MOD))%MOD as true, never thought about it and didn't see it was false during the contest. Learned something today, thank you.

→ Reply

9 years ago, # ^ |

My first solution failed Pretest 12 too. I think it's overflow since my resubmission changed some ints to long longs.

→ Reply

9 years ago, # |

looks like the magic thingy has done something pretty weird with the "became .." portion

→ Reply

Svyat

9 years ago, # |

Why second test in problem E didn't match with second test from samples during the contest? But now it matches.

→ Reply

Melnik

9 years ago, # |

← Rev. 5 →

Explain, please, where's the bug As you see, I have verdict: ans is too long. And at the same time ans isn't too long (23==23). And it is correct, because checker should give another verdict in the case it's incorrect

→ Reply

d3nd0h

9 years ago, # |

-11

is this only me or there is a legendary master in div 2?

→ Reply

Melnik

9 years ago, # ^ |

Dont worry, it's just a present from Santa Claus)

→ Reply

d3nd0h

9 years ago, # ^ |

i didn't expect this to be down voted so many :) but i was dumbly confused, maybe i missed the news about this :D

→ Reply

mahmud2690

9 years ago, # |

Could you explain why my solution to problem C gets TL. Here is the link: http://codeforces.net/contest/615/submission/15258328 i made several assertions for TL ( bad() function ), but still can not get where the solution stuck.

→ Reply

Luqman

9 years ago, # ^ |

Try running your code on custom invocation using this random testcase

#include <bits/stdc++.h>

using namespace std;

int main() {
  for(int i = 0; i < 2100; i++) printf("%c", rand() % 2 + 'a'); printf("\n");
  for(int i = 0; i < 2100; i++) printf("%c", rand() % 2 + 'a'); printf("\n");
  return 0;
}

Your code run 1528 ms. And it's RTE too. It's O(n^2 log n) because of map. Try finding better approach (i.e. without log n factor, don't use map, etc.)

→ Reply

mahmud2690

9 years ago, # ^ |

But as you see there is a function ( void bad() ) checks for TL, in that case i should get runtime error, instead TL.

→ Reply

shas19

9 years ago, # |

Can anyone tell me why I am getting runtime error on test case 23 in problem D? http://codeforces.net/contest/615/submission/15258241

→ Reply

Luqman

9 years ago, # ^ |

Variable f is overflow, and at some time can be negative.

When you use it at function powi(LL a, LL b), the b is negative so it's looping forever, then stack overflow (see, your memory is 262 MB)

→ Reply

shas19

9 years ago, # ^ |

Thanks a lot for help I changed f to f%(M-1) now I started getting WA in TC21 http://codeforces.net/contest/615/submission/15259163

→ Reply

kingofnumbers

9 years ago, # |

← Rev. 2 →

Became Candidate Master! What a Magic :D

picture above taken from rating change page

and some other people who didn't use magic and promoted today to another color their color didn't change :D

→ Reply

Bleuj

9 years ago, # ^ |

What about "Became unrated"?

→ Reply

9 years ago, # |

← Rev. 2 →

I think there is a problem crash on Problem D tonight.

It's quite similar to the problem BestCoder Round #61 Div.1 Problem 1003, which was held on 2015-10-31 19:00~21:00 UTC+8, which may be a little bit harder than tonight's problem D(I think).

→ Reply

anup_coder

9 years ago, # |

Can the problem B be solved using only dfs?

→ Reply

9 years ago, # ^ |

If you're writing a dfs without remembering anything, then it's impossible to pass this problem.

If you're writing a dfs, which will remember the answer of certain node it gave before, and will give you the answer directly if you ask later, it'll work.

15242225 It's a good example.

BTW, in fact, a for loop will solve this problem directly, since the graph is a DAG, and you know exactly the correct order to visit them (from 1 to n).15255434 Here's mine solving in this way.

→ Reply

9 years ago, # ^ |

i don't think it can. As I have no control over the degree of the nodes, There is no avoiding checking all the nodes for the tail length multiply the node's degree. And as doing DFS from each node will cost you TLE, you must use a dp table

→ Reply

dgkeut966

9 years ago, # |

I think the problems are good.Howerer I really felt unhappy when I got "Wrong Answer at pretest 1" ,just because i didn't wirte '\n' in the end.

→ Reply

9 years ago, # |

For problem D why does this solution give WA on case 23 ?

→ Reply

9 years ago, # ^ |

The way you're finding the divisors is wrong.

There are over 10,000 primes betwwen 1 and 200000. If your program is given all the primes between 1 and 200000, the variable divisors you're getting is wrong. In fact, it's way larger than a long long int can repesent.

Some tricks are required here.

→ Reply

9 years ago, # ^ |

I only found the number of divisors , not the divisors . variable divisors is sum of (power of each prime + 1). If this number is odd , that means N is a perfect square so I calculate temp which is basically the root of N. then the answer is simply N^(divisors/2). Whats wrong in this ?

→ Reply

9 years ago, # ^ |

I just mean the way you are calculating the number of divisors, or in other word, the variable divisor.

Line 40~41 in your code is:

    for(map<ll int,ll int>::iterator it=m.begin();it!=m.end();it++)
        divisors *= (it->second + 1);

which is absolutely wrong. Since the number of divisors can be really large.

There are over 10,000 primes betwwen 1 and 200000. If I give your program 10,000 different primes as input, the number of divisors will be 2^10000 ,which is impossible to represent by a long long int variable.

So some number theory tricks is required here.

→ Reply

9 years ago, # |

Can this solution be optimised to pass task C ? (right now it gives TLE on test 41)

→ Reply

9 years ago, # |

I want to clarify a bit the B's problem statement for myself, so that I am not prone to make such a mistake in the future.

"The tail should be continuous, i.e. consists of some sequence of points, such that EVERY TWO neighbouring points are connected by a colored segment;"
"all the SEGMENTS, such that ONE OF their ends is the endpoint of the tail"

Aren't these statements mean that the length of the tail MUST be bigger than 1?
If not, I'd like to see an explanation for that, because it will make me a bit wiser in the future.
Specifically, I'd like to see how the logical inverse of the first statement looks like.

→ Reply

9 years ago, # ^ |

← Rev. 9 →

Here is my attempt to construct the unambiguous tail.

A thing is a tail if the following statements are both true:
1. Statement A: the tail is a vector (a₁, a₂, ..., a_n).
2. Statement B: there is no element in the vector such that the element is less than or equal to the previous element. The same thing simbolically: $\text{[math]}$ a_i - 1 & $\text{[math]}$ a_i $\text{[math]}$ (a_i > a_i - 1).

Notice the existential quantifiers on the left-hand side of the implication. If the left-hand side becomes false, then the whole statement is true, which allows the tail to be a single vertex. The thing is not a tail when the following statement is true: $\text{[math]}$ a_i - 1 & $\text{[math]}$ a_i $\text{[math]}$ (a_i ≤ a_i - 1).

Could the same thing be done with the statement
The tail should be continuous, i.e. consists of some sequence of points,
such that EVERY TWO neighbouring points are connected by a colored segment;
?

→ Reply

9 years ago, # ^ |

You are analyzing too much and making the thing complicated.

1)Tail will have some points. two points will be connected by a segment. The points connected will form an increasing/decreasing order. The node with the maximum value is the endpoint. If you take only one node, it doesn't violate any of that. It has some points (one). Two points are connected by a segment (there are no two points that they are not connected by a segment). The points connected will form an order (trivial, there's only one node).

2)The tail endpoint is a node. and all the segments that form the spine will have this node as one of their ends. This statement looks clear to me compared to previous one

→ Reply

internom

9 years ago, # ^ |

← Rev. 2 →

Maybe not too much — It's in the statement

She wants to paint the tail that satisfies the following conditions: 1. Only segments already presented on the picture can be painted;

This means — To paint a tail then paint a segment. Translation just trolled some people and some people got AC instead of getting hacked o.O

→ Reply

9 years ago, # ^ |

Only segments already presented on the picture can be painted. This statement may be redundant but does not derail the main statement . "paint a tail then paint a segment"- this doesn't make sense, does it? because only after painting a segment u get the tail. a tail is already painted, why should u paint a tail again? :v

You might have some problem with translation issue. But please don't demoralize people like me who have solved it after much hardship by saying things like "some people got AC instead of getting hacked" :v (I also got hacked once) . It makes me feel very unaccomplished :/

→ Reply

9 years ago, # ^ |

Statement of B was very ambiguous. I thought during the entire contest that we can use two end points. Translation was not good. The problem should have had a mathematical formulation written along with it to avoid confusion.

→ Reply

spandanpathak

9 years ago, # |

Tutorial?

→ Reply

ihs

9 years ago, # ^ |

according to this comment

solutions for problems mentioned in comments!!!

you have to read all comments to see solutions

→ Reply

Mhammad1

9 years ago, # |

Anyone notice that the Length constraint for strings for problem C changed from 3000 to 2100 and the time limit changed from 1.5s to 1s without any announcement?

BTW, the problems are very good , thanks

→ Reply

aka.Sohieb

9 years ago, # |

When will the tutorials be translated?!

→ Reply

9 years ago, # |

If someone please can help me with some explanations to the D problem, I got a bug/problem and can't find it. I've read some comments but still not found the bug after 2 hours. Here is the code: http://codeforces.net/contest/615/submission/15260805

→ Reply

9 years ago, # ^ |

x = multi( x , z / 2 );

You should get rid of that annoying division, given that you are working with modular arithmetic.

I think that's the problem!

→ Reply

9 years ago, # ^ |

That changes the result but is still not giving the right answer for the 21st test

→ Reply

9 years ago, # ^ |

I mean, you have to make the division, but not there!

Given that you are working with (MOD — 1) for the exponent, the division result will be (in most of the cases) incorrect.

Hint: If z is an even number, and z = (a0 + 1) * (a1 + 1) * ... * (ap + 1), then there must be at least one (ai + 1) that is even.

→ Reply

9 years ago, # ^ |

After long, long, long revisions to my code, I finally managed to finish the problem, even if I'm not very clear about this modular arithmetic. Thanks!

→ Reply

shas19

9 years ago, # ^ |

I am getting same problem as yours..Can you tell me what did you do to remove WA in tc 21?

→ Reply

9 years ago, # ^ |

← Rev. 2 →

(f*k)/2 this code right here, you divide it by 2 but if you work modulo and in your f variable will be an even number, you will have at least one ( it->second + 1 ) in your map which is even and you should divide it by 2 when f will be even. If you still can`t figure it out look at my hode here: http://codeforces.net/contest/615/submission/15262138

→ Reply

9 years ago, # |

For those who haven't noticed : Link to Editorial

→ Reply