Codeforces Round #308 (Div 2) Editorial
Difference between en11 and en12, changed 0 character(s)
[problem:552A]↵
For each rectangle she adds ,the value of all the cells in that rectangle is increased by one.↵
Hence it is obvious that if a rectangle of side n*m is added ,the ans increases by n*m↵

for each rectangle↵

  scan(x1)↵

  scan(y1)↵

  scan(x2)↵

  scan(y1)↵

  ans=ans+(x2-x1)*(y2-y1)↵

**Time Complexity** O(n)↵

**My submission:**: [submission:11637017]↵

[problem:552B]↵
By number of digits the question means the total number of digits.↵

Hence number of digits for 1=1↵

number of digits for 10=2↵

number of digits for 100=3↵

We need to write all numbers from 1-n↵
We find the number of digits in n (lets call it k).↵

Ans=(the number of digits in all 1 digit numbers)+(number of digits in all 2 digit numbers)+...(number of digits in all k-1 digit numbers)+number of digits from 10^k to n.↵

As the number of p digit numbers = 9*pow(10,p-1)↵

for(i from 1 to k-1)↵

-  ans=ans+i*(9*pow(10,k-1))↵

And finally ans=ans+(n-pow(10,k-1)+1)*k↵

**My submission:** O(log(n))↵

My submission :[submission:11639835]↵

[problem:552C]↵
The problem is a simple case of recursion.We have weights of the form w^k(0<k<100).↵

if there exists a combination of weights that forms the mass M , then ↵

M=summation(w^k1)-summation(w*k2)↵

Hence M has to be of the form w*t+k (-1<=k<=1)↵

t also has to be of the form w*t1+k1 (-1<=k1<=1)↵

Hence the recursion continues .↵
The base case is when t<w.The answer will be yes if t=w-1||t=1||t=0↵

**Time Complexity** O(log(M))↵

**My submission:**[submission:11644642]↵

[problem:552D]↵

The problem can be solved by a simple brute force for all the points in pairs of 3.If the area of a given pair of 3 triangles is not zero , then it is a possible triangle.↵

- for(i from 0,n-1)↵
- -  for(j from i,n-1)↵

- - - for(k from j,n-1)↵

- - - - if (area (i,j,k)!=0)↵

- - - - ans++;↵

**Time Complexity** O(n^3)↵

The problem can however be solved in n^2 complexity.By iterating over all points in pairs of 2 , we can store their slopes in a map.↵

Then on iterating over the map we can find the number of triangles which wont contribute to the answer.↵

for(it in map)↵

- k += (it*(it-1)*(it-2)/6)↵

answer=n*(n-1)*(n-2)/6-k↵

**Time Complexity** O(n^2)↵

**My submission:** [submission:11727314]↵

[problem:552E]↵

An easy analysis shows that the brackets must be placed adjacent to * sign since they wont have any effect next to a + sign.↵

We need to store the indexes of all the * in the string and iterate over all possible pairs.↵
One thing to keep in mind is the maximum case may be one in which the brackets starts at the 0th index or the one in which it ends at the last index.↵

 **Time Complexity** O((length of string)*15*15)↵

**My submission:** [submission:11726590]

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en13 English hsk 2015-06-24 14:58:11 11
en12 English hsk 2015-06-23 23:59:39 0 (published)
en11 English hsk 2015-06-23 23:58:44 11
en10 English hsk 2015-06-23 23:56:40 41
en9 English hsk 2015-06-23 23:54:56 4
en8 English hsk 2015-06-23 23:54:23 198
en7 English hsk 2015-06-23 23:49:57 48
en6 English hsk 2015-06-23 23:48:05 2 Tiny change: 'rom 1 to k)\n\n- an' -> 'rom 1 to k-1)\n\n- an'
en5 English hsk 2015-06-23 23:47:17 3 Tiny change: ' 1 to k)\n ans=ans+' -> ' 1 to k)\n\n- ans=ans+'
en4 English hsk 2015-06-23 23:46:04 458
en3 English hsk 2015-06-23 23:41:00 345
en2 English hsk 2015-06-23 23:37:43 361
en1 English hsk 2015-06-23 23:34:36 1453 Initial revision (saved to drafts)