### Ripatti's blog

By Ripatti, 11 years ago, translation,
A. In this problem you can just do what is written in the statement. Let read all words. For each of them compute its length L, its the first and the last letter. If L > 10, output word without any changes, otherwise output the first letter, next L - 2 and finally the last letter.

B. At first, compute . It equals mnk / 100⌋, where x is rounding down. Next we fill first z / k squares with a saturation k. (⌊ z / k⌋ + 1)-th square (if it exists) we fill in a saturation z - ⌊ z / kk. All other squares we leave with a saturation 0.

C. Define an good polygon as a regular polygon which has a knight in a good mood in every of its vertex. Side of polygon we will measure in arcs which is obtained by dividing border of round table with knights.

Freeze the length of the side. Let this length equals k. Observe that the regular polygon with such length of side exists only if k divides n. We have exactly k of such polygons. Every of them has exactly n / k vertices. Check every of the polygons for goodness by review all of its vertices.

If sum of vertices with knight in a good mood equals to n / k, this polygon is good. Checking of all polygons with some frozen length of side works in an O(n).

Now observe that n has of divisors. Really, all divisors (may be except only one) we can divide into pairs (for i corresponds n / i, for i = n / i there is no pair). One of divisors in every pair less than . It means thah number of pairs no more than and number of divisors no more than .

It gives solution - iterate over all divisors of n and for every of them check existence of good polygon with length side equals this divisor. Solution has an time.

In reality for big n is has divisors. So solution actually has O(n4 / 3)-complexity. For all numbers less than 105 maximal number of divisors is 128.

UPD. There was found an solution by some participants. This solution uses following idea. If we have a good polygon with xy vertices, we also have a good polygon with x vertices. So we can check only prime divisors of n (except 2 - here we must check 4).

D. This problem can be divided into some subproblems.
Author's solution means following ones:

1. Check validness of square 3 × 3. Square is valid if all cards in it has equal suit or different rank. You may not check equal suit because equal suits imply different ranks.

2. Find 2 valid noninetsect squares 3 × 3 or return thah there are no ones. You can check all pairs of squares for inetsection. If some pair has no intersections check them with solution of subproblem 1.

3. Build set of cards which can be replaced with jokers. Generate full deck without jokers and drop from it all cards which in rectangle n × m are present.

4. Find number of jokers and its positions in rectangle.

5. Main subproblem. At first, solve subproblems 3 and 4. Now replace jokers in rectangle with cards from deck from subproblem 3 by all possible ways. For every replace solve subproblem 2. Arter all of variants of replacement just output answer.

There are O(n2m2) solution with small constant.

E. At first, you can use some search engine for find periodic table in some printable form. Next use copy-paste (one or several times) and format it by deleting all excess. It is mechanical work for no more than 5 minutes. Also some parser may be written. Note than author's solution does not mean write 100 symbols by hand from a picture. Next build some functions which transform symbols into numbers and vice versa.

So, we have some set of numbers. We need summarize some from them and get some another set of numbers. We will use dymanic programming over subsets.

Compute the first dp dp1[mask]->sum. For each subset calculate sum of numbers of all atoms in this subset. It can be done in O(2nn).

Now compute the second dp dp2[mask]->length. The "length" is a length of some prefix of result sequence of atoms which can be obtained by subset mask. If length -1, it means that it is impossible to get any prefix from this subset.

The second dp we can calculate in O(3n). Iterate over all masks and if dp2[mask]!=-1, iterate all its subsets of remained atoms (invert mask and get all its submasks). If some subset has sum of numbers which equals number of (dp2[маска]+1)-th atom from result set, recalculate dp2[mask XOR submask]=dp2[mask]+1.

At end, if dp2[2n - 1]=k, there are solution.

There are O(3n + 2nn) solution.

In this problem some brutforce solutions are passed because it is difficult to pick up some counterexample.

UPD. SkorKNURE found a solution in O(2nn). This solution is some modification of the author's solution.

Instead of dp2 calculate dp dp2'[mask]->(i,j), where i is a length of prefix which mask covers and j is part of number of (i+1)-th atom which mask covers.

Iterate over all masks. For each mask iterate over all its 0-bits (they are atoms which cover nothing from the finish set). We try to cover with this 0-bit a remainder of number of the (i+1)-th atom from the finish set. Let atomic number of an atom for current 0-bit is p and this atom is q-th in the start set. If we cover with this atom only part of the remainder of number of the (i+1)-th atom, dp2'[mask XOR (1<<q)]=(i,j+p). If we cover with this atom the remainder fully (and exactly this remainder, no more!), dp2'[mask XOR (1<<q)]=(i+1,0).

Now dp1 is useless. If at end dp2'[2n - 1]=(k,0), solution exists (it is easy to restore it), otherwise there is no solution.

• +47

 11 years ago, # |   +1 system testing took very long time.. and on the middle of contest, server down once.. what happened here?
 11 years ago, # |   +4 bd
•  11 years ago, # ^ |   +1 cool. I understand you. Its great!
•  11 years ago, # ^ |   +1 I can't understand , tell me what is bd?
•  11 years ago, # ^ |   +1 looks like "thumbs up"(I feel proud of myself for this guess :))
•  11 years ago, # ^ |   +1 It's ....Just like ORZ....
•  2 years ago, # ^ |   0 Bangladesh
•  23 months ago, # ^ |   0 hahahhahaha
 11 years ago, # |   +7 In problem C we can consider only _prime_ divisors of n (at most 6 :), as number of vertices. But there is one tricky case that i've missed, unfortunately.
 11 years ago, # |   0 In problem E, can you explain what is a mask and its submasks ?
•  11 years ago, # ^ | ← Rev. 2 →   0
•  11 years ago, # ^ |   0 I will rewrite editorial more detail later.
 11 years ago, # | ← Rev. 2 →   0 edit: I'm sorry that I didn't notice Lepetrandr's post.For (C) it suffices to check polygons with a prime number of sides (except for 2, then check 4), that gives O(log n) divisors to check.
•  11 years ago, # ^ |   0 Yes , because if the - polygon with length equal to n -  is regular , we can create another regular polygons which have the length of any prime divisors of n..but this number is not equal to log(n). This is equal to prime divisors of n.
•  11 years ago, # ^ |   +3 Number of prime divisors is about equal to ln (n) in case of big n.
 11 years ago, # |   +1 In the first problem explanation there's a type error: If L > 10, output word without any changes, otherwise output the first letter, next L - 2 and finally the last letter.Should be "If L ≤ 10"
•  11 years ago, # ^ |   0 Where did you find it? The statement is correct.
•  11 years ago, # ^ |   0
•  11 years ago, # ^ |   0 Oh, yes, i see.
 11 years ago, # |   0 In author's solution of problem E, does dp1 calculation really need dynamic programming? I think, this part can be done by simple 2 loops. for(int mask=0;mask<(1<
•  11 years ago, # ^ |   0 You are right. It can be calculated by your way. Also it is calculated in this way in the author's solution.
 11 years ago, # |   0 can you please explain O(nlog(n)) solution for question C ?
•  11 years ago, # ^ | ← Rev. 3 →   0 assume n= p1q1 * p2q2 * ... * pmqm, where all the pi is prime.then for each i, (1<=i<=m), check if exist good polygyn with exactly pi vertex. if at least one of this question has positive answer then output "YES", otherwise output "NO". because if we have a good polygyn with A*B vertex, then we have a good polygyn with A vertex.sorry for my poor english!
•  11 years ago, # ^ |   0 sorry, couldn't understand, can you explain with one example ?
•  11 years ago, # ^ | ← Rev. 2 →   0 assume this good polygyn with A*B vertex:S1, S2, ... , SA*Bnow we have subpolygyn which have only A vertex, like this:S1*B, S2*B, ... , SA*B.now it's obviously that if the circle  has a good polygyn then it has a polygyn with prime vertex. it's algo is O(nlgn) because for each i, pi >=2so m<=lgn, and check function is O(n). therefore main algo is O(nlgn).
 11 years ago, # | ← Rev. 3 →   0 Some help for Java users with problem E: http://pastebin.com/ZsDc3P1E(Yes, I'm a necroposter)
•  23 months ago, # ^ |   -8 Me too apparently
 » 4 years ago, # | ← Rev. 3 →   0 For problem C: Why don't we just find the largest bad mood gap between two good mood knights..0 1 0 0 1 1 0 0Then the largest gap is 3 (between 6th and 2nd knight) circular.And check whether there are 3 or more vertices having the same gap in between ?
•  » » 4 years ago, # ^ |   0 Never mind. Got it.
•  » » » 2 years ago, # ^ |   0 what was the mistake ???
•  » » » 22 months ago, # ^ |   0 Since I was also kind of wondering this, and got annoyed when op found out why, but didn't explain so that others could understand it as well, I couldn't help but get reminded of this, and I just had to post it.Anyway, if you're reading this, please don't be like op, since the explanation for something will surely be read by someone in the future, who'll be happy he found an answer to the question(s) he had.
• »
»
4 years ago, # ^ |
Rev. 2   0

I am getting run time error in A

# include <string.h>

void main() { int n,l; scanf("%d",&n); char arr[105]; for(int i=0;i<n;i++) { scanf("%s",arr); l = strlen(arr); if(l>10) printf("%c%d%c\n",arr[0],l-2,arr[l-1]); else printf("%s\n",arr); } } can somebody explain

 » 2 years ago, # |   0 Hi everyone i am not able to submit my code because there is Runtime error test 1 Codeforces round 65 A — Way Too Long Words Submission Id :- 76778006 There is an issue regarding input when i run it from eclipse , as the last line of input is not read until i hit enter button. Please can anyone help me out , I am new to codeforces and i know i am making a naive mistake.
 » 23 months ago, # |   0 Can someone help me with problem A?
 » 23 months ago, # |   0 Hi guys, can we help me when python implementation for read 'n' lines, please? Thanks a lot!
 » 23 months ago, # |   0 I know that this is a trivial and old problem but nevertheless, what is the exact input type for problem A? I've written code that assumes the input is either singular or an array; both yield the following error: "wrong output format Unexpected end of file — token expected".Using Python3.
•  » » 23 months ago, # ^ |   0 Ok, I know that nobody will probably care but I figured it out looking at other solutions:The question is worded quite poorly. You have to take the first line as the amount of times to iterate the process of collecting input.Have a look at previous solutions in Python to make more sense of this:https://codeforces.com/problemset/status/71/problem/A/page/1?order=BY_PROGRAM_LENGTH_ASC
 » 14 months ago, # |   0 hey can anyone tell me what's "m" in the explanation of PROBLEM 'B'
 » 6 months ago, # |   0 I think there's a small mistake in problem A editorial, one outputs the word without any changes if it's size is not greater than 10. Thank you for the editorial.