Добро пожаловать на 2016-2017 CT S03E02: Codeforces Trainings Season 3 Episode 2 - 2004-2005 Open Cup, Volga Grand Prix. Продолжительность тренировки — 4 часа 30 минут. Тренировка открыта как для команд, так и для индивидуальных участников. После ее окончания вы можете дорешивать задачи тренировки или поучаствовать в ней виртуально, если не смогли принять участие одновременно со всеми. Пожалуйста, участвуйте в тренировке честно.
Ориентировочный старт: 14 сентября 2016 г., 16:10 (Московское время).
Так как это тренировка, то возможно набор задач будет расширен, если для значительного количества участников он окажется простым.
Условия задач будут на английском языке, ведь мы же готовимся к ACM-ICPC!
Удачи!
if editorials of season 1 were published or atleast the codes of other people are made visible then it would be quite helpful.. :) thank you.. :)
editorials are available here
where I can find editorials for I-J-K-L?
Download this PDF
missing solutions for K-L
can you share how can we find the editorials ?
The questions for the last episode were from BAPC 2010. Just google BAPC 2010 and you'll find a link saying Outlines of the solution
you mean all i need to do is to find out the source of the gym contest ?
Yes. Also, in the last contest, if you see the questions PDF, it says BAPC 2010 on the top left corner.
Are they the same problems?
how to a beginner can participate this season ?
thank you :)
go to gym and click in register after the registration be enabled
Why does the title say "S03 E01", but the episode is Episode 02?
Fixed, thanks.
Wrong Ans on TestCase 104 20243522 isn't it more pathetic ? :p
I had WA on test 163, recently. I wonder if somebody has ever known worse than this. :/
20125823
Please reopen registration :(
It is open
Unrelated, but can I use the image in the post as my avatar?
Of course you can :)
Could you give more explanation about the question Fence. What does "if there are two red boards in the fence with the number of boards between them multiple to K" mean?
You should find such i, j (i != j) that:
1) a[i] is red
2) a[j] is red
3) distance between i and j is the number that can be divided by K
So the distance between i = 2 and j = 3 is supposed to be 1 ?
In this problem distance is the number of elements that are situated between i and j
So distance between i = 2 and j = 3 is 0
Testcase 22 in H? :D
any K
11
I don't understand, please clarify.
if you have two Consecutive ones, then the distance between them is 0, and number 0 is a multiple of any k.
Thanks
How to solve H?
For all
keep indices xmod that are 1's.
Segment [l, r] is good, if l mod k = (r + 1) mod k.
So we just need to check that there are exists modulo mod, such that xmod and xmod + 1 are both non-empty.
Hint:
Simplified the problem as : Find a subarray of an array whose sum is divided by given number K . If the sum of the numbers in the range [a, b] is divisible by K, then: (∑i=1 to a-1 arr[i]) % K = (∑i=1 to b arr[i]) % K
Construct a hash-map which will store the cumulative sum of all the numbers thus far mod K.
How do you solve E?
Can someone tell how to solve I please?
Solution for I.
Claim: For i subsets, we can partition
.
Proof: Induct. i = 1 is trivial.
Start with
.
Then, perform
Then, set
.
It is not difficult to prove that
and each T is sum free.
This solves the problem, since
can u please explain your solution in detail.
http://pastebin.com/Ykmg7iWn
Let me explain this solution in a better detail.
First, let us reword the problem.
Problem: Can we partition the set {1, 2, ... n} into 10 sum-free sets?
(Note: Sum-Free Set is a set A such that if
, 
.)
Let us make the trivial observation — if {1, 2, ... n} can be partitioned, so can {1, 2, ... n - 1}.
Now, we use the Claim above. Since
, every n ≤ 25000 is okay.
Therefore, construct the sets T_1 ~ T_10 inductively as described above and print which set a number is included in from 1 to n.
Well, it seems the fact that the graph isn't guaranteed to be connected makes C so much harder (adding edges carelessly to make it connected doesn't work). What was the expected solution?
LOL. You need to connect components by leaves. So much harder.
Each connected component can be compressed as a trees where nodes are biconnected components
Can problem B be solved in C++???
all the Accepted solutions were either in Python or Java, I know that it could be solved using the BigDecimal Class in Java, but is there anyway to solve it with C++???
Is there any editorial available for this round?
Can someone give me idea about G and H just getting TLE there
For G Get locations for each value first. Then iterate over 1 ≤ i ≤ n, and j such that i|j and check if both numbers appear in the sequence. Since
, this solution is 
.
For L (OOPS) Control two arrays, for color blue and red. Let the number of blue fence be bs and red fence be rs. Clearly, we use min(bs, rs) fences of each color. Sort the two arrays and choose the largest ones. The solution runs in
.
Would you please explain the iteration for problem G ...... what do you mean by i|j????
I think it means increment
j += i.Nope it means j is divisible by i :)
You mixed problem L and H :! Your soln for H is the soln for L
How to solve B & I ?
B: Just iterate several times
. This thing goes to 
really fast.
I: Suppose, you know how to color N cells using just K colors. Then using K + 1 colors you can easily color 3 * N + 1 cells, like this:
{ old thing with K colors }{ N + 1 cells with new color }{ old thing with K colors }
This will give 0110222220110 for 3 colors. Overall it allows you to color up to 29k cells with 10 colors.
Could you explain your solution for problem B in detail ?
Here is my AC code in python:
http://paste.org.ru/?c8n5wo
Python don't have long float arithmetics, so I was forced to use long int arithmetics.
There is actually long float arithmetics: class Decimal exactly.
Here's AC code.
Thanks! It's good to know!
That's Newton-Raphson Method for finding roots.
Nice and simple explanation for problem I.
I was far from this solution trying with binary operations and congruences, and I solved up to 3125 :(
I wonder if there is a different approach.
Can that B solution pass with C++ too?
Apparently you need some king of long arithmetics here. Usually the best way in this case is to either use Java or Python.
If you are brave enough and can write long arithmetics in c++ quick and bugless (and reasonably fast algos), then you are free to go and AC this problem in c++ =)
Why can't I see test cases?!
Can anyone tell me the test # 1 for task G?
Test 1 is usually the sample given in problem statement
test 12 in A?
How to solve A?
Can anybody share there approach to the problem I ??
problem k : wa on test 5 ? i dont know what did i miss ? can anyone help ?
i think its better to add the time limit to the statement for each problem.
When can we see the test cases ?
Depends on how hard you train :D (you need to participate in 30 contests and have 1900+ rating)
test 3 in E?
Can anyone tell me how this solution for G is wrong ? Code
You are only looking at pairs (i, 2 * i).
I'm guessing that you looked at
and thought that there exists a pair with (i, 2 * i) by Pigeonhole or something.
However, just look at n = 5, k = 3 and 1, 4, 5.
To solve the problem, you have to look for every (i, x * i) which takes
Can anyone give me ideas for solution of A or C?
In A, can you modify convex hull and do it?
In C, the graph should have a Hamiltonian cycle, that's all I could think of. How to add minimum edges to make it happen, I have no idea
In the light of the upcoming ACM contest I looked into the last year Moscow quarterfinal problems: http://codeforces.net/gym/100792
I wanted to peek at solutions of some problems, but I didn't find any editorials or sourcecodes. Here on cf sourcecodes and tests are also not shown. So I have two questions:
Does anybody know where to find editorial/outlines for solution/sourecodes of someone's solutions?
If no, am I allowed to write and publish the editorial myself (at least partially), or is it forbidden for some reasons?
I think it's okay to create a blog where everyone contributes to make an editorial. They will not link it to the contest, but as a discussion, I think it's alright
Regarding problem H (The Fence), there is a missing test case that makes some solutions fail due to exceeding the time limit. I think you should add it and rejudge all solutions.
The test case can be generated by this C++ code:
Is there any official outlines for this contest? can't find them anywhere
Problem F was one of the least solved problems in the contest. I wonder why nobody has asked for a solution/hint yet. So let me do the honors. The statement is amazingly simple, but I haven't been able to make any headway on this. Any ideas in the right direction would be appreciated. :-)
How to solve K?
Someone please post their approach to problem K- Parquet ?