Привет, Codeforces!
6 октября 2015 года в 19:30 MSK состоится очередной раунд Codeforces #324 для участников из второго дивизиона. Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса.
Хотелось бы сказать большое спасибо Zlobober (Максиму Ахмедову) за помощь в подготовке задач, Delinur (Марии Беловой) за перевод условий на английский, MikeMirzayanov (Михаилу Мирзаянову) за системы Codeforces и Polygon. Это мой первый раунд на codeforces, и, надеюсь, что не последний.
Участникам будет предложено пять задач и два часа на их решение. Разбалловка будет объявлена позднее.
Все герои задач имеют своих прототипов — моих друзей, знакомых, родных, которым и посвящается этот раунд.
Желаю удачи и высокого рейтинга!
UPD: Разбаловка стандартная 500-1000-1500-2000-2500
UPD2 Раунд завершен, всем спасибо за участие!
Поздравляем победителей!
1). Siunaus
2). aasddf
3). M_H_M
4). lal
5). femsub
Автокомментарий: текст был обновлен пользователем ZhNV (предыдущая версия, новая версия, сравнить).
Hope it will be a great Round :-) Happy coding :-)
Hope it's another interesting round. Good luck to all :)
I think clear problems with no story are better because there are many coders at codeforces that their main language is not english or Russian
Totally agree. For me it is quite difficult to read and understand the storylines in English. Sometimes I even look up a dictionary for words that I don't know.
It's a part of problem! You must have good English skills to understand storyline clearly. I think English tasks for Russian users will be more fair.
and Russian tasks for American and UK users? =). It is nonsense.
English is the main language of interaction between countries. You can't code in Russian; you code in English. So it makes sense that tasks should be in English.
1C is progaramming language (guess on what) on Russian. Now you know more.
1C, not C1.
:D
Best wishes to ACM ICPC — 2015 regional/sub-regional participants for their upcoming regional/sub-regional contest and congrats to those who already manage to qualify for ACM-ICPC World Finals 2016 — Phuket :)
"The scoring distribution will be announced later."
So mainstream ;)
Все герои задач имеют своих прототипов — моих друзей, знакомых, родных, которым и посвящается этот раунд.Как скучно...
Лучше чем герои мультфильмов :)
Меньше, чем раньше . . . :)
So much grey。。
Lots of down votes here :D :v
Заметили? Минусуют одних серых-зеленых-синих, явно же по цвету!
Теперь почти все серые-зеленые-серые...
This parrot seems angry :P
I had green parrot, but when cf change color, I changed color of that parrot too
You are very brave to comment here today. Look at all the downvotes.
"Downvote squad" hard at work :p
Same
Yeah! The color matches with your CF color. Hopefully you'll get a blue parrot soon :)
Желать удачи всем — бессмысленно. Но пусть тебя, дорогой читатель этого поста, посетят вдохновение, пусть твои пальцы порхают над клавиатурой, как синицы в небе; пусть код получается с первой компиляции правильным, пусть идеи решений задач мгновенно настигают и каждый нюанс каждой задачи пусть сразу оседает в твоей голове, не только защищая от хитрых тестов, но и подготавливая персонально для тебя целый ящик со взломами. Удачи тебе, дорогой читатель, и хорошего настроения!
В первый раз — приятно, Спасибо, хз)
Сам написал? Если да, то круто.
Мой друг. Конечно, сам.
Ну сам подумай, кто посмеет,
Вопреки вышестоящим минусам,
Писать о том, что смысла не имеет?
Ну сам подумай, кто еще
Будет писать о неизвестном чуде,
Когда у всех вдруг загорится голова,
И все задачи все сдадут за полчаса?
Такого ведь, как автор сознает, не будет никогда.
А, если и случится чудо спорадически,
То у координатора поседеет голова.
(за ритм извиняюсь — нет похожих слов, короче синтаксически)
Так что, прости, но все, что я писал,
Оно случится только на бумаге. Но главное я сделал: плюсиков набрал
А, может, и настроение поднял?..
Написал этот текст для себя, чтобы чуть-чуть разгрузиться перед контестом. И тут обнаруживается, что контест написать не могу, компьютер глючит по полной, похоже, какие-то проблемы с жестким диском. В общем, дорогие участники, это для вас :) .
Gayle Laakmann live session or this contest :D
Isn't she over-rated?
check this quora link quora. With all due respect ma'am, try to accept that there are people in this world a lot more smarter than u and being a bit** will not change that. :)
Isn't she stupid for saying that? Gennady won't even care, let alone give her a comeback.
yes i know.. in comments section she clearly states she knows him and compares herself and him as apples and oranges . LMAO XD
WHAAAAAAAAAAAAAAAAAAA????? brb,, dying on the floor laughing :D
Obligatory: Who?
спасибо
Пресвятая шоколадница, тут просто кладбище комментариев!
All participants good luck.
Автокомментарий: текст был обновлен пользователем ZhNV (предыдущая версия, новая версия, сравнить).
The scoring distribution will be announced later later later late lat la l..........
where is scoring distribution ??
Auto comment: topic has been updated by ZhNV (previous revision, new revision, compare).
z
Ответ по модулю в Div 2 B, серьезно?
(Для справки: люди, не знакомые с олимпиадами, или только начинающие знакомиться, не знают, как это делать. В лучшем случае они используют Python / Java / C# с их BigInteger-ами, а если они пишут на другом языке — не сдают задачу. Проверено на локальных контестах в университете)
Зато все кто не знал как считать ответ по модулю — узнали. Что в этом плохого? По-моему наоборот здорово.
В том, что они потратили на это 1 час и 50 минут контеста. Не надо так издеваться. В одном из прошлых раундов вот дали два указателя, это еще хуже было. Тебе было бы приятно подолбаться в эту задачу, если бы ты был совсем еще новичком? На A, B div 2 любые алгоритмы и олимпиадные приемы противопоказаны.
Чтож тогда по твоей логике в div 2 A нельзя задачу на цикл давать? Чтобы совсем новые участники не "долбились" в нее? Как развиваться вообще тогда?
Цикл — это конструкция языка программирования. Так что его давать можно. А два указателя, вывод ответа по модулю, динамика, можно много чего еще назвать — это олимпиадные приемы. Если давать это в ранних задачах Div 2, куча народу будет сидеть без дела, а после контеста еще подумает, а принимать ли участие в следующем раунде.
Мне кажется, развиваться на начальных этапах правильно с помощью архива задач и тренера/друзей/статей, которые расскажут что-то новое. Но не во время контеста! Ну дали тебе задачу с двумя указателями, ну написал ты два вложенных for-а, многому научился? Многим интереснее писать раунды, ведь это PvP и в общем случае весело, однако такие задачи, как сегодняшняя B, отбивают желание участвовать в олимпиадах. Поэтому надо делать задачи как можно более лояльными к новичкам.
В общем я считаю, что если автор считает нужным дать ответ по модулю в div2 B — пусть дает, это его право. А так как с тобой к консенсусу мы не придем, я завязываю)
Ну ок. У тебя просто ферлоновские взгляды в этом вопросе, у меня нет) А плюсуют пока обоих.
Вот что точно нужно было сделать, так это дать ещё один тестовый пример с переполнением. Это было бы более лояльно.
Ничего себе, уже не плюсуют. Но у меня рейтинг выше! Huyum_nik, твоя теория терпит крах!
В этой задаче можно было заставить возводить в степень за логарифм, но автор оказался гуманным :)
Не вижу ничего сложного для "зеленого" и выше в вычислении остатка.
Ты не видишь ничего сложного, потому что ты уже знаешь этот прием. В реальности абсолютно все новички сначала считают ответ как он есть (с переполнением), а потом выводят остаток.
Вообще-то теория сравнений ещё в советской школе изучалась на факультативе в 7 классе.
Лично мне тоже не очень нравится эта задача на позицию Б див2. По крайней мере потому, что это не просто возвести что-то в степень, но еще нужно вычесть одно слагаемое из другого. Даже не очень большие ограничения не делают задачу лучше.
По-моему на позицию Б див2 лучше подойдет реализация на 2 цикла, возможно с каким нибудь крайним случаем.
По-моему, если вы хотите сделать своих друзей и родственников героями задач, то не делайте это так. О самих друзьях и родственниках сказано только в начале каждой задачи по одному вводному предложению, которые всё равно никто не читает, и в названии, в результате чего по названиям задач невозможно вспомнить, о чём была задача.
At D I output
3 2 2 23 and I have wrong answer on pretest 1, where n = 27. Why?
Maybe somebody will help you, but only after end of contest
may be you had to write k in the first line, and prime numbers in the next line.
3
2 2 23
at problem d i output 3
2 2 23 i have wrong answer on pretest 1 , which has n=27 why? LE : my bad, sorry
What was the problem?
I forgot a return 1;
The windows returns it automatically,but on linux is a big problem. Sorry guys for the misunderstanding
z
why did you copy? this is bad
B — What's wrong with the solution
3^(3n) - 7^n?Nothing.
So it is actually right? I kept getting WA. Maybe I've got some mistakes in modular arithmetic ?
Yep, with modulo formula is like this ((3^n) % MOD — (7^n) % MOD + MOD) % MOD. Because we can get negative number)
P.S. sorry, didn't read posts below
if(ans < 0) ans += MOD;?cout << (g-s+mod)%mod;
I feel so embarrassed :\
And still. How could it possibly be negative?
because 1000000007 mod 1000000007 is less than 100 mod 1000000007
Got it now. Thank you.
-3/2=-1 -3%2=-1 I don't like this either. It causes so many troubles...
(g-s)%mod could be negative
when u will get ans < 0 as 27^n — 7^n can never be zero
That is what i did and it passed pretests
check overflows.
Logic behind formula? I failed very hard today ;_;
There are total 27 possible way to distribute coins to 3 gnomes out of which 7 will have have sum equal to 6. And in our required answer we need to exclude that case. Since there are n such combinations we will have 27 ^ n — 7 ^ n.
Thanks
I don't know why i was getting WA in 7th test case. :-(
It's very cool to understand some dependence or notice combinatoric, but I simly considered second test and suggested, that it could be true. In a result, I was lucky :)
Все заметели, что в топе стало меньше нерейтинговых))
Problem 2: Just 3^(3*n)-7^n ;))
27^n — 7^n : Still got wrong answer ...dont know why ...maybe becauze of MOD operation
maybe when
(7^n)%mod > (27^n)%mod, then you should write:((27^n)%mod-(7^n)%mod+mod)%modyou forgot to add MOD if the answer becomes -ve. You should write like this: (27^n — 7^n + MOD)%MOD
code by JAVA (3^(3*n)-7^n) % mod
dafuq is C pretest 9?
seriously it's killing me to know
I'm guessing something like this:
INPUT
5 1
baset
easej
OUTPUT
basej
Tested with my program (which failed at pretest 9), and I got the correct output for that input.
Yup Mine Passed that too :/
may be some thing like it!
4 2 abcd ebfg
How to solve problem E ?
Greedily. Problem: sort the permutation with minimum cost. Let's assume that we already sorted first i elements(0-based). Let's p[j] = i. Then we need to find maximum ind such that i ≤ ind < j and j ≤ p[ind], it can be easily done by segment tree. Then swap elements at index ind and j. For each index i you will make O(n) swaps. Complexity O(n2logn)
Are you certain this works? I submitted this and got stuck on pretest 14, and looking at your profile you didn't pass the pretests either (getting stuck much earlier than me).
I wanted to write the same but was sure that it doesn't work;)
Yes, that works. I didn't passed because I had wrong idea. I looked for maximum ind such that i ≤ ind < j and p[ind] > ind. This idea doesn't work for test: 4 4 3 2 1 1 2 3 4
The minimum cost is achieved using any strategy that never moves any element further from its final location, since |i - j| is just the distance by which each element is moved (·0.5).
One way to solve this would be putting all elements that need to be moved to the right in one set, those which need to be moved to the left in another set and always swapping the first element of the latter set with the last smaller element of the former.
Can't believe E can be so simple, thanks for the explanation :D
How to solve D?
If n is prime we print 1 n
If n — 2 is prime we print 2 2 n — 2
If n — 4 is prime we print 3 2 2 n — 4
Else n = p1 + p2 + p3. We find closest prime number to n (p1). And we've got n — k = p2 + p3.
n — k ~ log(N) (Don't remember why, shame on me). And just by brute force find p2 and p3.
What's the complexity of finding the closest prime number?
1700 * sqrt(n) maximum distance between 2 primes if they are both not greater than 10^9 is 1700
Maximum prime gap less than 10^9 is 282.
As I said n — k ~ log(N). Checking whether number is prime O(sqrt(N)). So finding closest prime number is log(N)sqrt(N).
If I'm wrong correct me please.
It seems that its O(log^2(N)). https://en.wikipedia.org/wiki/Prime_gap#Conjectures_about_gaps_between_primes
https://en.wikipedia.org/wiki/Goldbach%27s_conjecture
Seriously, without knowing this conjecture, can anybody solve problem D? This kind of problem just piss me off!!!
I solved D without this knowledge:D
Then you (maybe without realizing) assumed that there is always valid p2 and p3 whose sum equals to n — p1. Problem guarantees there is a solution. It doesn't guarantee there is a valid (p2, p3) pair; that's why, you need to know Goldbach's conjecture.
Yeah, you're right... This was just guess.
You don't need to know it since the problem is simple enough to brute force. First check if n is prime, if so print. Else find largest prime smaller than n, now check if you can find one or two primes adding up to this (goes very fast since prime density is quite high), if so print. Else iterate.
You know from the problem description that there is a solution, and you know that finding multiple fitting large primes is too slow so the only way left is to just find large primes and then see if you can find one or two smaller primes adding up to the result.
This way you can solve for odd n as well since it is so easy to find a solution.
Seriously, http://www.lmgtfy.com/?q=+integer+as+sum+of+three+different+primes
I used Levy's Conjecture and Fermat's Little Theorem to solve D.
I can't solve it during the contest due to a small mistake. But i did it right after the ending of the contest :/
If n = 3, output 1 3 if n = 5 output 2 2 3 else
since n is odd, n — 3 is even, and then we can use strong goldbach conjecture to solve the problem. Every number N even, greater than 2, can be written as sum of two primes. Since n — 3 is even, we can find this two primes that added form n — 3 and then add it to 3, which is prime. output
3 3 prime[i] (N — 3 — prime[i])
I used Sieve of Eratosthenes to find primes between 2 and 10^7, and if some number K didn't fit in this interval, I test it's primality by brute force. And used binary search to try to find N — 3 — prime[i] in vector of primes;
http://codeforces.net/contest/584/submission/13459478
Problem A and Problem B is a joke in Python
yeh! partiality with c programmer ;)
Bahut Na insafi hai
how so?
D also=)
What is The Solution Of div2 E? I tried to find symmetric group, but it seems hard to calculate the minimum step to sort the permutation
How to slove D? Damn I spend all contest to it
https://en.wikipedia.org/wiki/Goldbach%27s_conjecture
Still not sure how to do it.
It is basically coding Goldbach's weak conjecture, right?
3, and express n-3 as sum of two primes. Do you just brute force it? What about the time complexity?
No.4 cannot be expressed by your logic
The question says input is an odd number.
Then we are assuming that '3' is definitely in the answer. Can you prove it?
That is Goldbach's weak conjecture and it has been verified for numbers larger than the input in the question.
In fact, Goldbach's weak conjecture has been mathematically proven to be valid in general.
So handle small numbers manually for simplicity. (Since n is odd, n-3 is even, and you can brute for 2 remaining 2 primes numbers(other than 3) summing upto n). Handle cases of n=3, etc manually.
For larger n, always try and express it as sum of exactly 3 primes. Find a prime number g below n and close to it.This is one of your 3 primes. Since prime numbers are not too far apart, n-g is now a small even number(my bound was 50000) and you can brute for how to express it as 2 primes.
Thanks. Your gap was 50,000? According to wiki, a gap of 300 would suffice.
https://en.wikipedia.org/wiki/Prime_gap
I did not know that. Just wanted to be safe :P
There's no need of different method for larger numbers. You can always brute force to express n-3 as sum of two primes. My solution passed with this method. I think the reason for this is that even when n is around 10^9, there is a very high probability of finding a small prime p(upto which you can iterate in time) such that n-3-p is also prime.
Yes, I realized my solution during the contest failed only because my brain missed the "at most 3" condition. I ended up missing primes below 7 (3 and 5) — I thought they wouldn't be in the input since solution was guaranteed... Unfortunate error.
BTW, check this problem: http://acm.timus.ru/problem.aspx?space=1&num=1356. It's almost the same as the problem D, just a bit harder (but the solution for 1356 works here in problem D).
This problem was on National Olympiad of Kazakhstan 2013-2014, as I remember.
C pretest 9 ahhhr.
C looks straightforward but did not work out.
My thought.
System rating finished
Hello! I have a question at the second problem, Div 2. During the contest I printed
(put(3,3*n)-put(7,n))%m;and i have got wrong answer on test 7. Now I am printing(put(3,3*n)-put(7,n)+m)%m;and I have got accepted. Why the second method works? Thanks!put(3,3*n)-put(7,n) may be negative number. So first method would be incorrect (returns m minus right answer).
but why should i add m? m is 10^9 + 7. i don't understant..
put(3,3*n)-put(7,n) = Km + ans
may be less than zero. 0<=put(3, 3*n)<m ans 0<=put(7,n)<m. So -m<put(3,3*n)-put(7,n)<m
put(3,3*n)-put(7,n) + m guarantee positive. So mod operation would be correct.
For D, I just generated primes upto 10^6 and tried to find the answer with simple check. And it passes. Why does it pass?
Because primes are distributed pretty randomly with log(n) distance between them in average. So, there is no such number N that for all small prime numbers M up to 10^6, N — M is not prime.
Well, didn't know that. Thanks.
Очень радует, что в сегодняшнем раунде в Топ-40 находятся только пять "нерейтинговых восходящих звезд".
Цветовая революция пошла на пользу :)
Возможно, многие из них — фейки красных. Те самые, что когда-то давно за один контест стали фиолетовыми.
I don't understand.Why 2000 points for problem D??? :o :o :o It was far far easier than B and C.
Task C is more difficult than D . . . It's injustice!
why this submission get WA?
1 should not be considered prime
1 isn't prime number!
how to solve C ?
greedy . . .
Can you explain?
Codeforces should have a problem tag called "case handling"
just added the condition of a+b+c=n and D passed :( :( :( :(
Автокомментарий: текст был обновлен пользователем ZhNV (предыдущая версия, новая версия, сравнить).
Auto comment: topic has been updated by ZhNV (previous revision, new revision, compare).
i forget to say :thanks for no delay
Some help on E? I can find the minimum cost but I cannot restore the swaps. I thought about going from left to right and if we see an element which is not on its place (it must go to the right) then let's say his position is i and it must go to position j. Let's first handle all elements that are greater than Ai in the interval [i+1,j] and then somehow solve for the current element. Can you please give me a hint?
can E be solved using greedy method ?
Well, the first part (minimum cost) can be called greedy, I guess. The idea is to find for each number its position in B. Then if we want A to become B, that means that some elements will go to the left and some to the right. We can make the observation that we need to consider only those elements which go to the right. Let's assume that after considering them, there is an element that must go to the left (if there is more than one, consider the leftmost). Moving it to the left means moving one element to the right. A contradiction! So if pos[k] is the position of the element with value k in B, we add to the answer max(pos[Ai]-i,0) for each i.
My solution is actually greedy. What I do is in each step I have a vector that keeps all the numbers that have to go to the right (I iterate the numbers from left to right) and whenever I find a number that has to go to the left I just swap them and move the index of my iteration back so I can start from the number I moved.
Before that I change the permutations so the second permutation is 1 2 3 ... N and the first one changes so it's the same problem but having to move a permutation to the sorted permutation.
Let's see an example:
4 4 3 1 2 1 2 4 3
The problem is the same as solving
4 3 4 1 2 1 2 3 4
Now I start with 3, it has to go to the right so my vector is (3), then 4 has to go to the right so my vector is (3,4), then 1 has to go to the left so I swap 1 and 4 now it's
3 1 4 2
And my iterator moves back to where the 1 is, now 1 still has to go to the right so I swap 1 with 3 that is the top of my vector (or stack if you want to see it like a stack). Now it's
1 3 4 2
Then I continue iterating, 1 has to stay where it is and the vector is empty, then 3 has to go to the right, 4 has to go to the right too, and 2 has to go to the left, and when I analyze 2 my vector is (3,4) so I move 2 to the left and it's
1 3 2 4
And in the last step I change 3 with 2 so it's
1 2 3 4
And it finishes the process. This is a greedy approach and it's similar to selection sort I think.
I start with 4 (it
You can maintain an ordered set (balanced binary search tree) of all elements that need to go to the left (call this set L), and all that need to go to the right of the permutation (call this set R).
In each iteration you perform one swap, that involves swapping the leftmost element in L with its closest element in R to the left (it clearly has to exist). If you store both the elements and their positions, you can efficiently maintain this structure as you go along in logarithmic complexity.
You may refer to my code: http://codeforces.net/contest/584/submission/13456405
You don't need such complicated structures as O(N^2) is ok for this problem.
The complexity of my solution is actually something along the lines of O(N^2 log N) in the worst case (something like 5 6 7 8 1 2 3 4) anyway. I try to follow the approach which is easiest for me to comprehend on a high level. If it requires complicated structures, so be it (especially if they're already part of the STL). :)
Consider the element that needs to go to the rightmost location. Lets say that element is in the ith position and needs to go to the nth position. Then, surely there must be an element from positions i+1 to n which needs to go to a position j where j <= i. If no such element exists, then there are (n-i) elements which final location is from (i+1) to (n-1), a contradiction! Find the leftmost element which matches this criteria using a pointer sweep and then swap it with position i then keep repeating until it is moved to its correct location. This is an O(n^2) algorithm.
Problem E : For the first time on codeforces, a solution didn't pass for me with cin,cout. My solution failed system tests after passing the pretests. And when I changed it to printf,scanf it passed. I think the problem setters should be careful the next time, as when crtical points and rating gets affected due to such reasons, it feels sad.
Why are you blaming the problem setters for this? It was your fault!
What should be tested is our knowledge, not whether we use fast i/o. And in fact such things have never happened on Codeforces before. Also when you get a problem wrong because of such reasons, it doesnt feel good. I'm not blaming them, but I feel if someone loses out on points for a hard problem, because they didnt use fast i/o, that is just not fair.
If problemsetter increase time limit in order cin/cout submition past, it can cause that slow solutions will past with scanf/printf! Cin/cout speed is well-known fact, be careful, when you use it
Do you use
ios_base::sync_with_stdio(false);?
That line can save you from time limits if you use cin/cout
Yes I did use it, still didn't pass :(
You can add these lines to speed up cin/cout.
It is time to midnight,but still waiting for Rating.
It is almost sunrise, still waiting for Rating :P
it's night and i have n't done my homeworks! but still waiting for ratings!
Me too , it's weird how sometimes human being is not able to wait and do assignments both at once!
we have the same time midnight. already tired
MikeMirzayanov. When you declare a rating?
Happy New Year CF!!! wait(wow), rating still not updated?
Wow, my rating is changed to
+0:)What is this?
Oops, it will be fixed tomorrow.
Auto comment: topic has been updated by ZhNV (previous revision, new revision, compare).