### Блог пользователя TheWishmaster

Автор TheWishmaster, 5 лет назад,

Всем привет!

Уже завтра состоится Codeforces Round #338 (Div. 2). Обратите внимание на необычное время проведения контеста! Раунд для вас готовили Максим Винниченко (maxkvant) и я, Александр Зойкин. Это наш первый раунд, очень надеемся, что все пройдет хорошо. Огромное спасибо GlebsHP за неоценимую помощь в подготовке контеста, Bobrosoft за тестирование и не только, Delinur за перевод условий на английский язык и, разумеется, MikeMirzayanov за системы Codeforces и Polygon.

разбалловка 500 — 12501750 — 2000 — 2500

Всем удачи на контесте!

upd Поздравляем победителей!

div 2:

zhangzj_is_our_sun

marcorezieho

Claris

ucfpt

div 1:

I_love_Tanya_Romanova

ngfam_kongu

sd0061

pavel.savchenkov

ershov.stanislav

Разбор

• +291

 » 5 лет назад, # | ← Rev. 3 →   +11 Для 2016-го года это тоже первый раунд =)
 » 5 лет назад, # |   +18 Для авторов первый контест, для нас тоже первый в этом году :) Желаю всем удачного начала!!!
 » 5 лет назад, # | ← Rev. 2 →   -37 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. :-|
 » 5 лет назад, # |   +33 I hope problem statements be as concise and clear as the post :D
•  » » 5 лет назад, # ^ |   +17 The statement of Problem B is really ugly...
 » 5 лет назад, # |   -13 I wish the contest would be later... I will miss it.
 » 5 лет назад, # |   +63 Сuriously, will magic color be changed after rated contest?
•  » » 5 лет назад, # ^ |   +55 The Standings must look very cool with all these popping red colors! :D
•  » » 5 лет назад, # ^ |   0 Curiously... then we won't be able to be Legendary grandmasters.
•  » » 5 лет назад, # ^ |   +7 i think the magic color will not change before 10/1 but your rating will change after the contest
•  » » 5 лет назад, # ^ |   +3 Finally after contest both magic color and my own color wasn't changed through i have up my rank...:(
 » 5 лет назад, # |   +5 A nice time for Chinese coder:),hope to work out 3 problems or four:D
 » 5 лет назад, # | ← Rev. 2 →   +4 Приятно видеть короткий блог :)Всем удачи на первом контесте за 2016 год!P.S. Маленькая ошибка -> Раунд для все.
•  » » 5 лет назад, # ^ |   +1 Спасибо, поправил.
 » 5 лет назад, # |   +31 This contest will be very interesting and there are many hacks , dp and graph problems.
•  » » 5 лет назад, # ^ |   -13 And data structure?
 » 5 лет назад, # |   +8 Hope to have some interesting Problems with Small , Concise & Easier to Understand Statement . All The Best .
 » 5 лет назад, # |   +3 Registration open during contest ? Is it indended or is it a bug ?
 » 5 лет назад, # |   +48 Should be called hello 2016...
•  » » 5 лет назад, # ^ | ← Rev. 3 →   +4 Just wait for PrinceOfPersia to prepare another Hello 201X contest.
•  » » 5 лет назад, # ^ |   +1 Maybe "cheers!2016" is nicer... Dala!
 » 5 лет назад, # |   +10 hope it will be good first round for you guys
 » 5 лет назад, # |   +3 Good luck to all of you! Hope you'll have fun with the first contest in 2016 :)
 » 5 лет назад, # | ← Rev. 3 →   +9 Sorry, I didn't have that long experience on codeforces. What's really that polygon for which you always thank MikeMirzayanov, TheWishmaster ?
•  » » 5 лет назад, # ^ |   -18 The platform that contests are hosted at. Their own, handwritted (handbuilt?) Ejudge. A pretty neat thing, if you ask me. Link.
•  » » 5 лет назад, # ^ |   +2 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.
 » 5 лет назад, # |   +24 A lot of Legendary grandmasters will take part in this round!
 » 5 лет назад, # |   +3 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?
•  » » 5 лет назад, # ^ |   -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
 » 5 лет назад, # |   +7 First time participating as a Legendary grandmaster :D thanks Codeforces for this opportunity :)
•  » » 5 лет назад, # ^ | ← Rev. 2 →   0 First time as Legendary Grandmaster as well for me! Feeling so nervous ^_^
•  » » » 5 лет назад, # ^ | ← Rev. 2 →   +1 That magic just changes the color of your name . that's all . it doesn't make you a real legendary grandmaster ! :))
•  » » » » 5 лет назад, # ^ |   0 Who cares? we can be legendary one day. This is just self satisfaction for us to become the real one :)
 » 5 лет назад, # |   0 Maybe the contest can be earlier. I can start the contest after dinner. XDD
 » 5 лет назад, # |   +1 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 :)
 » 5 лет назад, # |   -32 orzdyh orzjc orztourist orzWJMZBMR ORZ TooDifficult 23333333
 » 5 лет назад, # |   +2 Score distribution pls?
 » 5 лет назад, # |   +2 hope good rating this time
 » 5 лет назад, # |   -8 I missed the registration due to unusual time. Can i any how give the contest now?? Please _/_
 » 5 лет назад, # |   +1 I missed the registration due to unusual time. Can i any how give the contest now ??
•  » » 5 лет назад, # ^ |   0 there's always the 'Virtual Participation' way :)In the words of cf itself, "Virtual contest is a way to take part in past contest, as close as possible to participation on time. "
 » 5 лет назад, # |   0 Hey in the second problem what is 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?
 » 5 лет назад, # |   +6 Why do you change the time limit in problem C without notification?
•  » » 5 лет назад, # ^ |   0 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.
•  » » » 5 лет назад, # ^ |   +4 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.
•  » » » » 5 лет назад, # ^ |   0 Do you have O(N * N) complexity?
•  » » » » » 5 лет назад, # ^ |   0 Yes
•  » » » 5 лет назад, # ^ | ← Rev. 2 →   +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
 » 5 лет назад, # | ← 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
•  » » 5 лет назад, # ^ |   +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?
•  » » » 5 лет назад, # ^ | ← 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
•  » » » » 5 лет назад, # ^ |   +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".
•  » » » » » 5 лет назад, # ^ |   +6 Oh sorry for my comment then .. Thanks for clarifying
 » 5 лет назад, # | ← Rev. 2 →   0 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.
•  » » 5 лет назад, # ^ |   +5 but i cant find the pattern. can you tell me?
•  » » » 5 лет назад, # ^ |   +9 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
•  » » » » 5 лет назад, # ^ |   +2 You just nailed it!!!
•  » » » » » 5 лет назад, # ^ |   -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
•  » » » » » » 5 лет назад, # ^ |   0 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.
•  » » » » » » » 5 лет назад, # ^ |   0 umm.... he isn't a candidate master :v check his profile
•  » » » » » » » 5 лет назад, # ^ |   0 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.
•  » » » » » » » » 5 лет назад, # ^ |   0 you just have to do the dp using dfs and store the degree. Taking care of bends, storing endpoints are not necessary
•  » » » » » » » » » 5 лет назад, # ^ | ← Rev. 2 →   0 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?
•  » » » » » » » » » 5 лет назад, # ^ | ← Rev. 2 →   0 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
•  » » » » » » » » » 5 лет назад, # ^ |   0 Yeah, that's how you handle bends.
•  » » » » » » » » » 5 лет назад, # ^ |   0 Got it! Thanks :)
•  » » » 5 лет назад, # ^ |   0 its like Uva 10182. i use many for loop to simulate. this round want us to find the pattern :(
•  » » » 5 лет назад, # ^ | ← Rev. 2 →   0 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 :)
•  » » » » 5 лет назад, # ^ |   +5 Well, got WA on #103 :)
•  » » » » » 5 лет назад, # ^ |   +5 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.
•  » » 5 лет назад, # ^ |   +4 Why problem E problem E?
•  » » 5 лет назад, # ^ |   0 For me, C was easier than B, even though I didn't pass all the pretests. I couldn't figure out B.
•  » » 5 лет назад, # ^ |   0 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 -_-
 » 5 лет назад, # |   0 How to solve B?
•  » » 5 лет назад, # ^ | ← Rev. 2 →   -31 I didn't solve B. I think C was easier than B
•  » » 5 лет назад, # ^ |   +1 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).
•  » » » 5 лет назад, # ^ |   0 Thank you! With that description I managed to get the solution without the graph structure 15261877.Very beautiful :)
•  » » 5 лет назад, # ^ |   0 my solution is for node 1 to N it can be a node of a tail(a,b,c...N) a
•  » » » 5 лет назад, # ^ | ← Rev. 2 →   0 my solution is wrong because i compare int and long long
•  » » » » 5 лет назад, # ^ |   0 Yeah, there are my two submissions: 15258474 and 15258091
•  » » 5 лет назад, # ^ |   +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.
•  » » » 5 лет назад, # ^ | ← Rev. 2 →   +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.
•  » » » 5 лет назад, # ^ | ← Rev. 2 →   0 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. 10 9 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 Expected Answer: 9After 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;
•  » » » » 5 лет назад, # ^ |   0 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
•  » » » » » 5 лет назад, # ^ | ← Rev. 2 →   0 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
 » 5 лет назад, # | ← Rev. 2 →   0 What was 3-d pretest for D? Can't detrmine whats wrong...
 » 5 лет назад, # |   +9 Не мог взломать участника. Отправляю контр-тест -> получаю ответ, мол посылка уже взломана. Обновляю страницу комнаты — посылка участника все еще висит(так и провисела до конца контеста). У меня у одного такое было ?
•  » » 5 лет назад, # ^ |   0 Какая попытка?
•  » » » 5 лет назад, # ^ | ← Rev. 2 →   0 не совсем Вас понял, если вы о попытке участника, то вот она — http://codeforces.com/contest/615/submission/15247356. Мы находились в 116 комнате.P.s Похоже это все-таки моя вина, я неправильно понял систему взломов.
 » 5 лет назад, # |   +3 Extremely weak pretests in D killed me today :(
 » 5 лет назад, # |   0 What is the hack test for problem D!?
•  » » 5 лет назад, # ^ | ← Rev. 6 →   +18 Contestant's mistake: (ab)%MOD ≠ (a(b%MOD))%MOD What it actually is (ab)%MOD = (a(b%(MOD - 1)))%MODContestants solution were working if b < MOD - 1
•  » » » 5 лет назад, # ^ | ← Rev. 2 →   +1 could you please explain why to use b%(mod-1) my solution also failed for that reason.
•  » » » » 5 лет назад, # ^ |   +4 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.
•  » » » » 5 лет назад, # ^ | ← Rev. 7 →   +6 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%pHere r = b%(p - 1)
•  » » » » » 5 лет назад, # ^ |   -12 Except carmichael numbers
•  » » » » » 5 лет назад, # ^ |   0 I got the formula right, but used inverse of 2 while calculating (a ^ (p/2)%MOD-1)%MOD. It got WA. Why ?
•  » » » » » » 5 лет назад, # ^ |   0 That is because 2 and 109 + 6 are not co-prime and inverse exists only if the pair of numbers is co-prime.
•  » » » 5 лет назад, # ^ | ← Rev. 2 →   0 I used some value and understood that (a^b)%MOD ≠ (a^(b%MOD))%MODbut couldn't understand what would be the alternative. could u explain why (MOD-1) ?(upd) just saw your reply, thanks
•  » » » 5 лет назад, # ^ |   0 I took MOD -2 :(
 » 5 лет назад, # |   +3 Обида, не хватило 5 минут отдебажить C и решить все задачи =\Справедливости ради, задачки сегодня были очень простые.
 » 5 лет назад, # |   +5 Very well prepared round and the problemset was good! :)
 » 5 лет назад, # | ← Rev. 3 →   -41 Hmmm what's wrong with the code here?http://codeforces.com/contest/615/submission/15249100
•  » » 5 лет назад, # ^ |   +14 Please don't paste in long code, link to submission.
•  » » 5 лет назад, # ^ | ← Rev. 6 →   0 Please, use pastebin, ideone, paste.ubuntu or github for your code.It would be much better to read your code there.
 » 5 лет назад, # |   0 How to solve D??
•  » » 5 лет назад, # ^ |   +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.
•  » » » 5 лет назад, # ^ |   +5 but, why?
•  » » » 5 лет назад, # ^ |   0 So how do you calculate the number of divisors fast?
•  » » » » 5 лет назад, # ^ | ← Rev. 2 →   +4 n=p1^e1 * p2^e2 ... pk ^ eknumber of divisors is (e1+1)*(e2+1) .... *(ek+1)
•  » » » 5 лет назад, # ^ |   0 its not quite correct for example: 2 3 3d(n) = 3 d(n) / 2 = 3 / 2 = 1 9 ^ 1 = 9 the correct answer is 27
•  » » » » 5 лет назад, # ^ |   +1 Well, in maths 3 / 2 = 1.5, and 91.5 = 27, so mathematically speaking it is absolutely correct.
•  » » » » » 5 лет назад, # ^ |   0 thank you for answer now I understand
•  » » 5 лет назад, # ^ | ← Rev. 3 →   +3 Formula.(I think this is the formula. Feel free to correct me)let k=frequency of a primethen, ans=product of((prime^(2^k-1))^(sum/f(prime)))sum=product of(frequency of prime+1)f(prime)=frequency of prime+1.
•  » » » 5 лет назад, # ^ |   0 Still waiting for someone to correct me.OMG!! this can be easily coded with modular exponentiation ;_; .
•  » » » » 5 лет назад, # ^ | ← Rev. 2 →   -16 Ignore
•  » » 5 лет назад, # ^ |   +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).
•  » » » 5 лет назад, # ^ |   0 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
•  » » 5 лет назад, # ^ | ← Rev. 2 →   +13 First of all you want to bundle all primes with the same value. You now have n = p1e1p2e2...pmemAll 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 to i=j-1One table for the products from i=j+1 to i=m-1To prevent overflow, everything in the exponent of pj can be taken modulo 109 + 7 - 1, using Euler's theorem.
•  » » » 5 лет назад, # ^ |   0 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?
•  » » » » 5 лет назад, # ^ |   0 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.
•  » » » » » 5 лет назад, # ^ |   0 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?
•  » » » » » » 5 лет назад, # ^ |   0 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.
•  » » » » » » » 5 лет назад, # ^ |   0 Got it! Thank you a lot for your explanations!
•  » » » 5 лет назад, # ^ |   0 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
•  » » » » 5 лет назад, # ^ |   +5 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.
•  » » » » » 5 лет назад, # ^ |   0 Oh thanks
•  » » » 5 лет назад, # ^ | ← Rev. 2 →   0 If you're using a language with fast enough arbitrary integer arithmetic, just compute the entire product. See 15259490.
 » 5 лет назад, # |   +3 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?
•  » » 5 лет назад, # ^ | ← Rev. 3 →   0 I have exactly the same trouble with you.
•  » » 5 лет назад, # ^ |   +8 So, it's turned out that the second pretest is different from the second example. Never seen this in the past...
•  » » » 5 лет назад, # ^ |   0 Compile your code with -O2
 » 5 лет назад, # |   0 Nice problems, but bad performance by me :( I hope to do better next time :)
 » 5 лет назад, # | ← Rev. 3 →   +3 I think difficulty is:A,D,E,B,CAt 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
•  » » 5 лет назад, # ^ |   -15 I don't know about E I read till D. So according to me, the difficulty was A < D~=C < B.
•  » » » 5 лет назад, # ^ |   0 A~E
•  » » 5 лет назад, # ^ |   0 I'm sorry, if the question is silly, but how do you make these formulas here? :)
•  » » » 5 лет назад, # ^ |   0 You wrap the text in dollar signs. Like if it was a latex document.
 » 5 лет назад, # |   0 Кто-нибудь может объяcнить решение B? Хотя бы общий алгоритм, что ли..
•  » » 5 лет назад, # ^ |   0 Я пока не знаю, прошло ли моё решение, поэтому пока просто сделаю набросок словами. Будем перебирать в цикле все вершины (вообще все). Каждую вершину мы считаем за начало хвоста. Дальше мы удлиняем хвост с помощью dfs до тех пор, пока есть смежная вершина с номером больше текущего.После каждого удлинения на одну вершину, мы смотрим количество ВСЕХ смежных вершин с текущим концом хвоста. Это количество смежных вершин — все иголки ёжика. Умножаем количество иголок в данный момент времени, на размер текущего хвоста и сравниваем с лучшим результатом, который мы когда-либо достигали.Если мой подход пройдёт и никто не сделает более менее красивого описания этого решения, я сделаю более подробный комментарий с картинками =)
•  » » » 5 лет назад, # ^ |   0 Вот один в один как Вы сказали, получил TL на взломе, так же как и Вы на системных тестах только что( http://codeforces.com/contest/615/submission/15254540
•  » » » » 5 лет назад, # ^ |   +5 Да, я тоже в пролёте :)Ничего страшного, зато я изучу и отпрактикую новую для себя концепцию. Видимо концепция dfs сидит в моей голове крепче, чем то, что требуется в этой задаче.
•  » » » » » 5 лет назад, # ^ |   0 Легко решается динамическим программированием, и я получил-бы AC, если бы записывал результат в long long. Вот работающий код http://codeforces.com/contest/615/submission/15255627
•  » » » » » » 5 лет назад, # ^ |   0 Если бы я совершенно НЕ знал теории графов, то шансов решить эту задачу было бы намного больше. Вот такой вот абсурд — DFS было первое, что пришло в голову — а тут оно еще и претесты прошло
•  » » » » » » » 5 лет назад, # ^ |   0 Эта штука, которую ты сейчас описал, в психологии называется Einstellung Effect. Я вот сейчас сижу и размышляю — задачу я не решил, но я стал сильнее в психологии :)
•  » » 5 лет назад, # ^ | ← Rev. 2 →   0 Это задача на динамическое программирование (очень простая). Перебираешь вершины от 1 до n и смотришь, какой самый длинный хвост оканчивается в текущей вершине. А в ответ идёт максимум из степени вершины помноженную на длину хвоста.
 » 5 лет назад, # |   0 How to pass the pretest 4 for D? I don't even figure out why I got WA.
•  » » 5 лет назад, # ^ |   +3 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
•  » » 5 лет назад, # ^ |   0 Fuck, I always compute sqrt(n*t(n)), but there are 2 sqrt by module p...
 » 5 лет назад, # |   0 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?
•  » » 5 лет назад, # ^ |   0 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
 » 5 лет назад, # | ← Rev. 2 →   0 hmmm I don't see what is wrong with the code here: http://codeforces.com/contest/615/submission/15249100
 » 5 лет назад, # |   0 hello , you can give me solution B , thank you so much
•  » » 5 лет назад, # ^ | ← Rev. 2 →   +6 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.
•  » » 5 лет назад, # ^ |   +1 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 :)
•  » » » 5 лет назад, # ^ |   0 No, I was wrong. Don't read that long text :)
•  » » » 5 лет назад, # ^ |   0 By the way, it's a nice case to study Einstellung Effect :)
 » 5 лет назад, # |   +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 :)
 » 5 лет назад, # |   +4 When does the editorial usually come out? Last time it came out as soon as the contest finished :)
•  » » 5 лет назад, # ^ |   0 recently it comes out real fast.so I don't think it will take more than "a few" hours
•  » » 5 лет назад, # ^ |   +6 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.
 » 5 лет назад, # |   +5 Когда-нибудь наступит тот день, что я перестану в div1 проверять все решения в комнате в поисках очевиднейшего переполнения... Хотя на это уходит всего минут 5, но всё же...
 » 5 лет назад, # |   0 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....
•  » » 5 лет назад, # ^ |   0 I did n^2 log n but got WA on pretest 15, so I don't really know about that...
•  » » 5 лет назад, # ^ |   +3 same ! got tle on test #20 ... I assume they were expecting some trie based solution for that :|
•  » » » 5 лет назад, # ^ |   +11 Could be also solved by Z-Function.
•  » » » » 5 лет назад, # ^ | ← Rev. 2 →   +4 I used only std::string member-functions, very easy and straigtforward solution.Submission: 15255098 46ms.
•  » » » » » 5 лет назад, # ^ |   0 Greedy solutions works here?
•  » » » » » » 5 лет назад, # ^ |   +3 It is easy to prove that it works.
•  » » » 5 лет назад, # ^ | ← Rev. 2 →   +4 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.
•  » » » » 5 лет назад, # ^ |   +3 My solution got ML on test #23. after changing vector(27) to map I got accepted in 900ms
•  » » 5 лет назад, # ^ |   0 Same here :(BTW: wasn't the time limit = 1.5sec
•  » » 5 лет назад, # ^ |   +9 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.
•  » » » 5 лет назад, # ^ |   0 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)
•  » » » 5 лет назад, # ^ |   +6 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 :(
•  » » » » 5 лет назад, # ^ |   +19 You are free to generate maxtest and use "run" tab to see how long does your solution work.
•  » » » » » 5 лет назад, # ^ |   +1 But... how? I've never known about such a feature o.O Where can we find it ?
•  » » » » » » 5 лет назад, # ^ |   0 codeforces.com/contest/559/customtest
•  » » » » » 5 лет назад, # ^ |   0 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... ?
•  » » 5 лет назад, # ^ |   +1 my N^2 DP approach got stack overflow :D
•  » » 5 лет назад, # ^ | ← Rev. 3 →   0 I solved it using Z algorithm and it runs in 77 ms in the worst case. 15255258
 » 5 лет назад, # |   +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.
•  » » 5 лет назад, # ^ |   0 Completely agree with you, but anyways is a great problem.
•  » » 5 лет назад, # ^ |   +3 Exactly. I understood this line after 15 minutes of reading the problem
•  » » 5 лет назад, # ^ |   +3 Yes, initially I thought that there are no cycles. "Number of points increase" :P
 » 5 лет назад, # | ← Rev. 2 →   0 Problem E saved some people :)
 » 5 лет назад, # |   +11 Первый в 2016 году раунд на Codeforces, вне всяких сомнений, удался :)
 » 5 лет назад, # | ← Rev. 2 →   +7 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
•  » » 5 лет назад, # ^ |   0 Fake one or one with actual rating?
•  » » 5 лет назад, # ^ |   -8 Hahaaha, you hacked forcer. He is fake Legendary Grandmaster
•  » » » 5 лет назад, # ^ |   +1 No way, I was sure he is real Lagendary Grandmaster :(
•  » » » » 5 лет назад, # ^ |   0 Hope one day you will do it ;)
 » 5 лет назад, # |   0 link Can someone help me?
•  » » 5 лет назад, # ^ |   0 Take 1LL while calculating final answer
•  » » » 5 лет назад, # ^ |   0 it makes me very very upset. how can i avoid this? should i define int long long int?
•  » » » » 5 лет назад, # ^ |   0 There are my two submissions: 15258474 and 15258091
 » 5 лет назад, # |   +15 I liked the problems, they were very nice but I hate B's statement.
•  » » 5 лет назад, # ^ |   0 I think it's safe we all did :-(
•  » » 5 лет назад, # ^ |   0 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
•  » » » 5 лет назад, # ^ |   0 Eh, I forgot to use the current vertex in the dfs and got TLE (unfortunately it passed pretests ... ) :D :D :D
 » 5 лет назад, # |   0 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/15255459Though it is in practise now because i didnt took 1LL while i was calculating result so its got overflowed :(
 » 5 лет назад, # |   0 Можете объяснить почему RE на 4 тесте в задаче D? Если это переполнение типа, то как оптимально брать по модулю? Заранее спасибо!
•  » » 5 лет назад, # ^ |   0 Как минимум, вот эта строка некорректна: n *= x;Произведение введенных простых может быть очень большим.
 » 5 лет назад, # |   0 Ratings updated
•  » » 5 лет назад, # ^ |   +1 It is funny that for unrated people color wasn't changed:
 » 5 лет назад, # |   -9 And i rise again, just because i solved A fast enough. :D
•  » » 5 лет назад, # ^ |   0 And i took a dip again coz i did a silly mistake on A :(
 » 5 лет назад, # | ← Rev. 5 →   +6 Скажите, почему в D при нечетном количестве делителей работает:((число % MOD)((количество делителей % Phi(MOD)) / 2) % Phi(MOD) * (корень числа % MOD)) % MODгде "/ 2" -- обычное деление с отбрасыванием остатка. Смущает то, что в кольце Phi(MOD) существуют два числа, умножение которых на 2 даст количество делителей минус один: количество делителей % Phi(MOD) / 2 (количество делителей % Phi(MOD) / 2 + Phi(MOD) / 2) % Phi(MOD). Код: 15255053
 » 5 лет назад, # |   0 Кто может пояснить почему при выводе переменной ans через cout все выводится нормально, а при выводе через printf выводится пустота? (202 и 203 строки)http://paste.ubuntu.com/14439109/
•  » » 5 лет назад, # ^ |   0 ll — неправильный спецификатор формата для long long. Попробуй lld.
•  » » » 5 лет назад, # ^ |   0 Спасибо, при запуске все правильно отрабатывает, но при отсылке файла выдается "Пожалуйста, не используйте спецификатор %lld (или подобные) для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d."Почему так?
•  » » » » 5 лет назад, # ^ |   0 Нашел ответ http://codeforces.com/blog/entry/5444
•  » » » » 5 лет назад, # ^ |   0 Думаю, что потому, что вообще говоря, не гарантируется, что long long будет иметь длину 64 бита (может быть больше).Можно почитать подробнее здесь: http://stackoverflow.com/questions/15718039/why-the-use-of-cin-cout-or-i64d-is-preferred-over-lld-specifier-in-cВообще (ИМХО) в современном C++ более предпочтительно использовать int_64t (который гарантированно 64-битный) и cout/cin (за исключением случаев, когда вводимых данных больше миллиона).
 » 5 лет назад, # |   0 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.
•  » » 5 лет назад, # ^ |   +5 Nevermind, found my silly mistake
•  » » » 5 лет назад, # ^ |   0 I got WA on case 20 too. Still can't find my mistake :(
 » 5 лет назад, # |   0 Разбор будет?
•  » » 5 лет назад, # ^ |   +8 Да будет наверное как обычно. Codeforces хороший сайт и здесь на все задачи разборы есть ^_^
 » 5 лет назад, # |   0 Could someone tells why this gives WA!! what I missed here?! problem D 15242486
•  » » 5 лет назад, # ^ |   +6 number of divisors will overflow
 » 5 лет назад, # |   0 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?
•  » » 5 лет назад, # ^ |   +8 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! ^_^
•  » » 5 лет назад, # ^ |   0 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.
 » 5 лет назад, # |   +1 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.
•  » » 5 лет назад, # ^ |   +3 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.
•  » » » 5 лет назад, # ^ | ← Rev. 3 →   +5 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.
•  » » 5 лет назад, # ^ |   0 My first solution failed Pretest 12 too. I think it's overflow since my resubmission changed some ints to long longs.
 » 5 лет назад, # |   +3 looks like the magic thingy has done something pretty weird with the "became .." portion
 » 5 лет назад, # |   0 Why second test in problem E didn't match with second test from samples during the contest? But now it matches.
 » 5 лет назад, # | ← Rev. 5 →   0 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
 » 5 лет назад, # |   0 Masha ruined my day .... :( (failed to get what she want as she is a small girl :/ )
 » 5 лет назад, # |   -11 is this only me or there is a legendary master in div 2?
•  » » 5 лет назад, # ^ |   +3 Dont worry, it's just a present from Santa Claus)
•  » » » 5 лет назад, # ^ |   +3 i didn't expect this to be down voted so many :) but i was dumbly confused, maybe i missed the news about this :D
 » 5 лет назад, # | ← Rev. 2 →   0 Masha ruined my day :( (after all she is a small girl :/ )
 » 5 лет назад, # | ← Rev. 2 →   -7 Так почему были изменены ограничения в задаче С по времени и длине строк, да еще и не было оповещения? Это косяк, вообще-то
 » 5 лет назад, # |   0 Could you explain why my solution to problem C gets TL. Here is the link: http://codeforces.com/contest/615/submission/15258328 i made several assertions for TL ( bad() function ), but still can not get where the solution stuck.
•  » » 5 лет назад, # ^ |   0 Try running your code on custom invocation using this random testcase #include 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.)
•  » » » 5 лет назад, # ^ |   0 But as you see there is a function ( void bad() ) checks for TL, in that case i should get runtime error, instead TL.
 » 5 лет назад, # |   0 Why this submission is TLE? Click
 » 5 лет назад, # |   0 Can anyone tell me why I am getting runtime error on test case 23 in problem D? http://codeforces.com/contest/615/submission/15258241
•  » » 5 лет назад, # ^ |   0 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)
•  » » » 5 лет назад, # ^ |   0 Thanks a lot for help I changed f to f%(M-1) now I started getting WA in TC21 http://codeforces.com/contest/615/submission/15259163
 » 5 лет назад, # | ← Rev. 2 →   +3 Became Candidate Master! What a Magic :D picture above taken from rating change pageand some other people who didn't use magic and promoted today to another color their color didn't change :D
•  » » 5 лет назад, # ^ |   0 What about "Became unrated"?
 » 5 лет назад, # | ← Rev. 2 →   0 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).
 » 5 лет назад, # |   0 Can the problem B be solved using only dfs?
•  » » 5 лет назад, # ^ |   0 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.
•  » » 5 лет назад, # ^ |   0 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
 » 5 лет назад, # |   0 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.
 » 5 лет назад, # |   +3 For problem D why does this solution give WA on case 23 ?
•  » » 5 лет назад, # ^ |   0 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.
•  » » » 5 лет назад, # ^ |   0 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 ?
•  » » » » 5 лет назад, # ^ |   0 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::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.
 » 5 лет назад, # |   0 Can this solution be optimised to pass task C ? (right now it gives TLE on test 41)
 » 5 лет назад, # |   0 Когда разбор?
 » 5 лет назад, # |   0 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.
•  » » 5 лет назад, # ^ | ← Rev. 9 →   0 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 statementThe tail should be continuous, i.e. consists of some sequence of points,such that EVERY TWO neighbouring points are connected by a colored segment;?
•  » » 5 лет назад, # ^ |   0 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
•  » » » 5 лет назад, # ^ | ← Rev. 2 →   0 Maybe not too much — It's in the statementShe 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
•  » » » » 5 лет назад, # ^ |   0 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? :vYou 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 :/
•  » » 5 лет назад, # ^ |   +1 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.
 » 5 лет назад, # |   0 Tutorial?
•  » » 5 лет назад, # ^ |   +3 according to this commentsolutions for problems mentioned in comments!!!you have to read all comments to see solutions
 » 5 лет назад, # |   0 There is some problem with some users colors.
 » 5 лет назад, # |   0 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
 » 5 лет назад, # |   0 When will the tutorials be translated?!
 » 5 лет назад, # |   0 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.com/contest/615/submission/15260805
•  » » 5 лет назад, # ^ |   0 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!
•  » » » 5 лет назад, # ^ |   0 That changes the result but is still not giving the right answer for the 21st test
•  » » » » 5 лет назад, # ^ |   +1 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.
•  » » » » » 5 лет назад, # ^ |   +3 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!
•  » » » » » » 5 лет назад, # ^ |   0 I am getting same problem as yours..Can you tell me what did you do to remove WA in tc 21?
•  » » » » » » » 5 лет назад, # ^ | ← Rev. 2 →   0 (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 cant figure it out look at my hode here: http://codeforces.com/contest/615/submission/15262138
 » 5 лет назад, # | ← Rev. 2 →   0 Кто-нибудь может поподробнее объяснить проблему D? Пожалуйста!
 » 5 лет назад, # |   +3 For those who haven't noticed : Link to Editorial
•  » » 5 лет назад, # ^ |   0 The explanation for the C problem is still the best explanation I've heard yet.
•  » » 5 лет назад, # ^ |   0 How could we notice it? Was it published anywhere else?
 » 5 лет назад, # |   +1 My rating didn't change, although I was not disqualified. I want to know the reason.
 » 5 лет назад, # | ← Rev. 7 →   0 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.
•  » » 5 лет назад, # ^ | ← Rev. 2 →   0 His magic color was Newbie before the contest afaik. His current magic colour is Red. His current actual color is PurpleMaybe the standings show the color the person had before the contest (which includes magic color)
 » 5 лет назад, # |   +20 What happened to the editorial post? It seems gone :(
 » 5 лет назад, # |   +18 Editorial link is not working.
 » 5 лет назад, # |   0