Greetings!
Codeforces Round #338 (Div. 2) will be held tomorrow. Note that round starts at the unusual time! This round was made by Maxim Vinnichenko(maxkvant), and me, Alexander Zoykin. It is our first round and we hope that everything will be OK. Thanks to GlebsHP for the great help in preparing the contest, Bobrosoft for being more than tester, Delinur for translating the statements into English, and MikeMirzayanov for the great Polygon and Codeforces systems.
score distribution 500 — 1250 — 1750 — 2000 — 2500
Good luck!
upd Congratulations to winners!
div 2:
div 1:
Pretty weird. This blog was posted 21 hour(s) ago and according to it, contest should be held today but it will be held tomorrow. Moreover registration was closed 24 hours before the contest. :-|
I hope problem statements be as concise and clear as the post :D
The statement of Problem B is really ugly...
I wish the contest would be later... I will miss it.
Сuriously, will magic color be changed after rated contest?
The Standings must look very cool with all these popping red colors! :D
Curiously... then we won't be able to be Legendary grandmasters.
i think the magic color will not change before 10/1 but your rating will change after the contest
Finally after contest both magic color and my own color wasn't changed through i have up my rank...:(
A nice time for Chinese coder:),hope to work out 3 problems or four:D
This contest will be very interesting and there are many hacks , dp and graph problems.
And data structure?
Hope to have some interesting Problems with Small , Concise & Easier to Understand Statement . All The Best .
Registration open during contest ? Is it indended or is it a bug ?
Should be called hello 2016...
Just wait for PrinceOfPersia to prepare another Hello 201X contest.
Maybe "cheers!2016" is nicer... Dala!
hope it will be good first round for you guys
Good luck to all of you! Hope you'll have fun with the first contest in 2016 :)
Sorry, I didn't have that long experience on codeforces. What's really that polygon for which you always thank MikeMirzayanov, TheWishmaster ?
The platform that contests are hosted at. Their own, handwritted (handbuilt?) Ejudge. A pretty neat thing, if you ask me. Link.
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.
A lot of Legendary grandmasters will take part in this round!
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?
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
First time participating as a Legendary grandmaster :D thanks Codeforces for this opportunity :)
First time as Legendary Grandmaster as well for me! Feeling so nervous ^_^
That magic just changes the color of your name . that's all . it doesn't make you a real legendary grandmaster ! :))
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 :)
orzdyh orzjc orztourist orzWJMZBMR ORZ TooDifficult 23333333
Score distribution pls?
hope good rating this time
I missed the registration due to unusual time. Can i any how give the contest now ??
Why do you change the time limit in problem C without notification?
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.
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.
Do you have O(N * N) complexity?
Yes
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
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
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?
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
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".
Oh sorry for my comment then .. Thanks for clarifying
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.
but i cant find the pattern. can you tell me?
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
You just nailed it!!!
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
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.
umm.... he isn't a candidate master :v check his profile
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.
you just have to do the dp using dfs and store the degree. Taking care of bends, storing endpoints are not necessary
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?
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
Yeah, that's how you handle bends.
Got it! Thanks :)
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 :)
Well, got WA on #103 :)
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.
Why problem E problem E?
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 -_-
How to solve B?
I didn't solve B. I think C was easier than B
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).
Thank you! With that description I managed to get the solution without the graph structure 15261877.
Very beautiful :)
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])
my solution is wrong because i compare int and long long
Yeah, there are my two submissions: 15258474 and 15258091
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.
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.
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;
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
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
What was 3-d pretest for D? Can't detrmine whats wrong...
Extremely weak pretests in D killed me today :(
What is the hack test for problem D!?
Contestant's mistake: (ab)%MOD ≠ (a(b%MOD))%MOD
What it actually is (ab)%MOD = (a(b%(MOD - 1)))%MOD
Contestants solution were working if b < MOD - 1
could you please explain why to use b%(mod-1)
my solution also failed for that reason.
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.
By Fermat's Little Theorem we get that
ap - 1 ≡ 1%p, so if b = n × (p - 1) + r, then,
ab → (an × (p - 1) + r)%p
→ (an × (p - 1) × ar)%p
→ (an × (p - 1))%p × (ar)%p
→ 1 × ar%p
Here r = b%(p - 1)
Except carmichael numbers
I got the formula right, but used inverse of 2 while calculating (a ^ (p/2)%MOD-1)%MOD. It got WA. Why ?
That is because 2 and 109 + 6 are not co-prime and inverse exists only if the pair of numbers is co-prime.
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
I took MOD -2 :(
Very well prepared round and the problemset was good! :)
Hmmm what's wrong with the code here?
http://codeforces.net/contest/615/submission/15249100
Please don't paste in long code, link to submission.
Please, use pastebin, ideone, paste.ubuntu or github for your code.
It would be much better to read your code there.
How to solve D??
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.
but, why?
So how do you calculate the number of divisors fast?
n=p1^e1 * p2^e2 ... pk ^ ek
number of divisors is (e1+1)*(e2+1) .... *(ek+1)
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
Well, in maths 3 / 2 = 1.5, and 91.5 = 27, so mathematically speaking it is absolutely correct.
thank you for answer now I understand
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.
Still waiting for someone to correct me.
OMG!! this can be easily coded with modular exponentiation ;_; .
Ignore
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).
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
First of all you want to bundle all primes with the same value. You now have n = p1e1p2e2...pmem
All divisors must be written in the form d = p1f1p2f2...pmfm, where 0 ≤ fi ≤ ei.
Then we know that the product of all divisors d is:
We see that all factors from i1 to im - 1 are not depending on im so we can put them outside the last product when we raise it to the (em + 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:
Which is equal to:
The inner product should be calculated by using two precalculated tables:
One table for the products from
i=0
toi=j-1
One table for the products from
i=j+1
toi=m-1
To prevent overflow, everything in the exponent of pj can be taken modulo 109 + 7 - 1, using Euler's theorem.
How could we apply modulo 109 + 7 - 1 in the exponent of pj, since we have a division (by 2) and 2 and 109 + 7 - 1 aren't coprimes?
ej is at most 200000, so we calculate ej·(ej + 1) without using modulo because it won't overflow. Then you can divide by 2 because it will either divide ej or ej + 1. Then after multiplying with the product you can take the modulo.
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?
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 ej(ej + 1). Otherwise it might overflow for large ej and then the value is negative, and might not be divisible by 2 anymore.
Got it! Thank you a lot for your explanations!
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
1LL * x * x * a
van produce an overflow when both x andere a are very large, so you could mod1LL * x * x
before multiplying it with a.Oh thanks
If you're using a language with fast enough arbitrary integer arithmetic, just compute the entire product. See 15259490.
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?
I have exactly the same trouble with you.
So, it's turned out that the second pretest is different from the second example. Never seen this in the past...
Compile your code with -O2
Nice problems, but bad performance by me :( I hope to do better next time :)
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 . Unless x is perfect square, in which case we want
I don't know about E I read till D. So according to me, the difficulty was A < D~=C < B.
A~E<B
I'm sorry, if the question is silly, but how do you make these formulas here? :)
You wrap the text in dollar signs. Like if it was a latex document.
How to pass the pretest 4 for D? I don't even figure out why I got WA.
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
Fuck, I always compute sqrt(n*t(n)), but there are 2 sqrt by module p...
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?
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
hmmm I don't see what is wrong with the code here: http://codeforces.net/contest/615/submission/15249100
hello , you can give me solution B , thank you so much
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.
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 :)
No, I was wrong. Don't read that long text :)
By the way, it's a nice case to study Einstellung Effect :)
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 :)
When does the editorial usually come out? Last time it came out as soon as the contest finished :)
recently it comes out real fast.so I don't think it will take more than "a few" hours
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.
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....
same ! got tle on test #20 ... I assume they were expecting some trie based solution for that :|
Could be also solved by Z-Function.
I used only std::string member-functions, very easy and straigtforward solution.
Submission: 15255098 46ms.
Greedy solutions works here?
It is easy to prove that it works.
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.
My solution got ML on test #23. after changing vector(27) to map I got accepted in 900ms
Same here :(
BTW: wasn't the time limit = 1.5sec
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.
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)
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 :(
You are free to generate maxtest and use "run" tab to see how long does your solution work.
But... how? I've never known about such a feature o.O Where can we find it ?
codeforces.com/contest/559/customtest
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... ?
my N^2 DP approach got stack overflow :D
I solved it using Z algorithm and it runs in 77 ms in the worst case. 15255258
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 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.
Completely agree with you, but anyways is a great problem.
Exactly. I understood this line after 15 minutes of reading the problem
Yes, initially I thought that there are no cycles. "Number of points increase" :P
Problem E saved some people :)
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
Hahaaha, you hacked forcer. He is fake Legendary Grandmaster
No way, I was sure he is real Lagendary Grandmaster :(
Hope one day you will do it ;)
link Can someone help me?
Take 1LL while calculating final answer
it makes me very very upset.
how can i avoid this?
should i define int long long int?
There are my two submissions: 15258474 and 15258091
I liked the problems, they were very nice but I hate B's statement.
I think it's safe we all did :-(
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
Eh, I forgot to use the current vertex in the dfs and got TLE (unfortunately it passed pretests ... ) :D :D :D
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 :)
http://www.codeforces.com/contest/615/submission/15255459
Though it is in practise now because i didnt took 1LL while i was calculating result so its got overflowed :(
Ratings updated
It is funny that for unrated people color wasn't changed:
And i rise again, just because i solved A fast enough. :D
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.
Nevermind, found my silly mistake
Could someone tells why this gives WA!! what I missed here?! problem D 15242486
number of divisors will overflow
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?
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! ^_^
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.
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.
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.
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.
My first solution failed Pretest 12 too. I think it's overflow since my resubmission changed some ints to long longs.
looks like the magic thingy has done something pretty weird with the "became .." portion
Why second test in problem E didn't match with second test from samples during the contest? But now it matches.
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
is this only me or there is a legendary master in div 2?
Dont worry, it's just a present from Santa Claus)
i didn't expect this to be down voted so many :) but i was dumbly confused, maybe i missed the news about this :D
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.
Try running your code on custom invocation using this random testcase
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.)
But as you see there is a function ( void bad() ) checks for TL, in that case i should get runtime error, instead TL.
Can anyone tell me why I am getting runtime error on test case 23 in problem D? http://codeforces.net/contest/615/submission/15258241
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)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
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
What about "Became unrated"?
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).
Can the problem B be solved using only dfs?
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.
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
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.
For problem D why does this solution give WA on case 23 ?
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.
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 ?
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:
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.
Can this solution be optimised to pass task C ? (right now it gives TLE on test 41)
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.
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.
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 (a1, a2, ..., an).
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: ai - 1 & ai (ai > ai - 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: ai - 1 & ai (ai ≤ ai - 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;
?
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
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
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 :/
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.
Tutorial?
according to this comment
solutions for problems mentioned in comments!!!
you have to read all comments to see solutions
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
When will the tutorials be translated?!
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
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!
That changes the result but is still not giving the right answer for the 21st test
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.
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!
I am getting same problem as yours..Can you tell me what did you do to remove WA in tc 21?
(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/15262138For those who haven't noticed : Link to Editorial
The explanation for the C problem is still the best explanation I've heard yet.
How could we notice it? Was it published anywhere else?
My rating didn't change, although I was not disqualified. I want to know the reason.
What color has zhangzj_is_our_sun?
In div2 winners he is gray, in his profile he is red/purple
3-colored man?)
And yes, I found a little bug with these colors. When I clicked 'preview', his handle was red, but you see a gray handle in this comment. MikeMirzayanov, fix please.
His magic color was Newbie before the contest afaik.
His current magic colour is Red.
His current actual color is Purple
Maybe the standings show the color the person had before the contest (which includes magic color)
What happened to the editorial post? It seems gone :(
Editorial link is not working.
Please activate the editorial link. It does not seem to be working. Without editorial there is nothing to learn from a contest.
Editorial link is now working again :) Thanks
http://codeforces.net/blog/entry/22658