rng_58's blog

Codeforces Round #162 Tutorial
By rng_58, 12 years ago, In English

Div2 A Colorful Stones (Simplified Edition) (Author: rng_58)

In this problem you just need to implement what is written in the statement. Make a variable that holds the position of Liss, and simulate the instructions one by one.

Div2 B Roadside Trees (Simplified Edition) (Author: snuke)

The optimal path of Liss is as follows: First she starts from the root of tree 1. Walk up the tree to the top and eat a nut. Walk down to the height min(h1, h2). Jump to the tree 2. Walk up the tree to the top and eat a nut. Walk down to the height min(h2, h3), ... and so on.

Div1 A / Div2 C Escape from Stones (Author: DEGwer)

In this problem, there are many simple algorithms which works in O(n). One of them (which I intended) is following:

You should prepare 2 vectors. If s[i] = 'l', you should push i to the first vector, and if s[i] = 'r', you should push i to the second vector. Finally, you should print the integers in the second vector by default order, after that, you should print the integers in the first vector in the reverse order.

This algorithm works because if Liss divides an interval into two intervals A and B and she enters A, she will never enter B.

Div1 B / Div2 D Good Sequences (Author: DEGwer)

The main idea is DP. Let's define dp[x] as the maximal value of the length of the good sequence whose last element is x, and define d[i] as the (maximal value of dp[x] where x is divisible by i).

You should calculate dp[x] in the increasing order of x. The value of dp[x] is (maximal value of d[i] where i is a divisor of x) + 1. After you calculate dp[x], for each divisor i of x, you should update d[i] too.

This algorithm works in O(nlogn) because the sum of the number of the divisor from 1 to n is O(nlogn).

Note that there is a corner case. When the set is {1}, you should output 1.

Div1 C / Div2 E Choosing Balls (Author: hogloid)

There are many O(Q * N * logN) solutions using segment trees or other data structures, but probably they will get time limit exceeded.

We can solve each query independently. First, let's consider the following DP algorithm.

dp[c] := the maximal value of a sequence whose last ball's color is c

For each ball i, we want to update the array. Let the i-th ball's color be col[i], the i-th ball's value be val[i], and the maximal value of dp array other than dp[col[i]] be otherMAX. We can update the value of dp[col[i]] to dp[col[i]] + val[i] × a or otherMAX + val[i] × b. Here, we only need to know dp[col[i]] and otherMAX. If we remember the biggest two values of dp array in that time and their indexes in the array, otherMAX can be calculated using the biggest two values, which always include maximal values of dp array other than any particular color.

Since the values of dp array don't decrease, we can update the biggest two values in O(1). Finally, the answer for the query is the maximal value of dp array.

The complexity of the described algorithm is O(QN).

Div1 D Colorful Stones (Author: rng_58)

First, let's consider a simpler version of the problem: You are given a start state and a goal state. Check whether the goal state is reachable from the start state.

Define A, B, C, and D as in the picture below, and let I be the string of your instructions. A and B are substrings of s, and C and D are substrings of t.

It is possible to reach the goal state from the start state if there exists an instruction I such that:

  • 1 A is a subsequence of I.
  • 2 B is not a subsequence of I.
  • 3 C is a subsequence of I.
  • 4 D is not a subsequence of I.

So we want to check if such string I exists. (string s1 is called a subsequence of s2 if it is possible to get s2 by removing some characters of s1)

There are some obvious "NO" cases. When D is a subsequence of A, it is impossible to satisfy both conditions 1 and 4. Similarly, B must not be a subsequence of C. Are these sufficient conditions? Let's try to prove this hypothesis.

To simplify the description we will introduce some new variables. Let A', B', C', and D' be strings that can be obtained by removing the first characters of A, B, C, and D. Let c1 and c2 be the first characters of A and C.

Suppose that currently the conditions are satisfied (i.e. D is not a subsequence of A and B is not a subsequence of C).

  • If c1 = c2, you should perform the instruction c1 = c2. The new quatruplet will be (A', B', C', D') and this also satisies the conditions.
  • If c1 ≠ c2 and B' is not a subsequnce of C, you should perform the instruction c1. The new quatruplet will be (A', B', C, D) and this also satisies the conditions.
  • If c1 ≠ c2 and D' is not a subsequnce of A, you should perform the instruction c2. The new quatruplet will be (A, B, C', D') and this also satisies the conditions.

What happens if all of the above three conditions don't hold? In this case A and C have the same length and A = c1c2c1c2..., B = c2c1c2c1. In particular the last two characters of A and B are swapped: there are different characters x and y and A = ...xy, B = ...yx. Now you found a new necessary condition! Generally, if A and B are of the form A = ...xy and B = ...yx, the goal state is unreachable. If the last instruction is x, Vasya must be in the goal before the last instruction, but then Vasya will go further after the last instruction. If the last instruction is y, we will also get a contradiction.

Finally we have a solution. The goal state is reachable from the start state if and only if D is not a subsequence of A, B is not a subsequnce of C, and A and C are not of the form A = ...xy, C = ...yx. The remaining part is relatively easy, so I'll leave it as an exercise for readers.

Div1 E Roadside Trees (Author: snuke)

For this problem there are slides: Please check here.

UPD: Thank you for pointing out mistakes. They are fixed.

  • Vote: I like it
  • +54
  • Vote: I do not like it

Comments Comments (55)
| Write comment?
»
12 years ago, # |
← Rev. 2   Vote: I like it +17 Vote: I do not like it

It's nice to know that you idea for hard problem (Div 1 C) (for me certainly) is absolutely right=) But not enough time for debugging and AC=(

→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I have solved the div1 A problem using the mentioned algorithm, but I still receive that TLE error on the 31st test. I use Ruby. Is there a Ruby solution, which will pass the time test?

Here is my algorithm:

q = gets.chomp
left = []
right = []
i = 0
q.each_char do |char|
  i += 1
  ((char == 'l') ? right : left) << i
end
puts left
puts right.reverse

Thanks in advance!

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Ruby is slow. Use C++, FPC, Java, C# and it will be accepted.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My C++ Solution got also TLE. I used vectors and Microsoft Visual C++ Compiler! But using Gnu C++, It got Accepted!

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    A citation from here:

    It is not guaranteed that all the problems will have solutions in all the given languages (it's especially about the scripting ones).

    Some folks managed to pass with Python, but it may happen that in Ruby I/O functions are much too slow to get AC.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you. Tommorow there will be a match, and now I'm deciding which language to use. I have looked through all the submissions to that tasks, way most of them are written with C++, some Java, and even two Python solutions. Nothing else. My "second favourite" language is C#, and I have written a solution to the same problem in C#, but... Превышено ограничение времени на тесте 35 (TLE on 35th). So, C# is too slow too? Here is my C# code

      using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication
{
    class Program
    {
        public static void Main(string[] args)
        {
            var s = Console.ReadLine();
            var l = new List<int>();
            var r = new List<int>();
            var i = 0;
            foreach (char c in s)
            {
                i++;
                if(c=='l')
                {
                    r.Add(i);
                }
                else
                {
                    l.Add(i);
                }
            }
            foreach (int i12 in l)
            {
                Console.WriteLine(i12);
            }
            r.Reverse();
            foreach (int i2 in r)
            {
                Console.WriteLine(i2);
            }
        }
    }
}

      In one of Java solutions I've seen class "FastScanner" with only method "FastRead", which reads from STDIO. If you think that the time issue is in IO, maybe there is a possibility to write some wrappers aroung Ruby's gets and puts?

      → Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can't view images from the problem Div1 D: 403 forbitten. :-(

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Fixed now.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It seems in problem D should be "A = c1c2c1c2..., C = c2c1c2c1." instead of "A = c1c2c1c2..., B = c2c1c2c1." And further should be C instead of B.

      → Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

I assume you meant “when i is a divisor of x” instead of “when i is a multiple of x.”, in Good Sequences.

→ Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    why only divisors it should be multiples of all prime factor of x which are less than x

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For Div2 D Good Sequences, I don't understand why the sum of the number of the diviser from 1 to n is O(nlogn). Can someone prove it?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Let p be a number in the range 1 — n Now, p will divide n/p no.s Sum of no. of divisors — {Summation(p = 1 to n)} n/p <= n * {Summation(p = 1 to n)} 1/p = n * H(n) ( H is sum of harmonic series ) and since ln(n) < H(n) < ln(n) + 1 thus, n * ln(n) < Answer < n * (ln(n) + 1)

    → Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it +4 Vote: I do not like it

Div1 A / Div2 C Escape from Stones (Author: DEGwer) :

My solution is in O(2n), But code is so simple like it,

int main(){
	string a;
	cin>>a;
	for(long i=0; i<a.size(); i++)
	if(a[i]=='r') cout<<i+1<<endl;
		
	for(long i=a.size()-1; i>=0; i--)
	if(a[i]=='l') cout<<i+1<<endl;
	
    return 0;
}
→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    nice! But actually O(2n) = O(n) by the definition.

    → Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Div1 A/Div2 C

Finally, you should print the integers in the first vector by default order, after that, you should print the integers in the second vector in the reverse order.

should be: Finally, you should print the integers in the second vector by default order, after that, you should print the integers in the first vector in the reverse order.

→ Reply
»
12 years ago, # |
  Vote: I like it -11 Vote: I do not like it

2 problems of 7 are made by round author)

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved DIV 2 C by looking at the input and output, I never understood the problem statement !!

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone explain DIV1-C in more detail? Thanks.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Div2 C Escape from Stones can also be solved using Doubly Linked Lists.

Maintain a pointer operatingPointer which is initialized to the head of list (head of the list contains 1).

if we encounter 'l' at ith position of input add i+1 to the left of operatingPointer and update operatingPointer to newly created node.

Similarly if we encounter 'r' at ith position of the string add i+1 to the right of operatingPointer and update operatingPointer to newly created node.

Then print the whole list.

Implementation using Doubly Linked Lists

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For Div 2 D/ Div 1 B, why do we have to update d[i] for all divisors of x? Can someone explain? Thanks in advance.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Getting wrong answer for test 13 in div1 b......Can someone explain what is wrong in this?

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Could a top-down approach be used for div1 B/div2 D? I tried a top down approach but I am not able to memoize it.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Div A/Div2 C Escape from Stones the algorithm is easy to understand if someone explains it,

but I don't understand how this solution came to be, which trail of thought led to this solution.

can someone please explain it.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't think editorial nor comments explanation on solution 264A - Спастись от камней are intuitive so I'll try to explain how I came up with a solution.

You can visualize the problem as a binary tree. Each node is responsable for a interval [a, b]. Starting from the root, responsable for [0, 1], if you go left then root will have a left child responsable for interval [0, 1 / 2]. Since you're a left child, last time the stone fell on position 1 / 2, the end point of the interval.

Note that from that child, it doesn't matter if you go left or right: the stone will never fall on a position bigger than 1 / 2 (the end point). The ideia is: since a stone always fall on the midpoint (a + b) / 2 of the lower and end points, it can never fall after the endpoint. In fact, the stone must fall infinitely many times to the right to reach that endpoint. So, we were on a node [0, 1], the stone fell and we jumped to the left, creating a left child [0, 1 / 2] and we now know that there is no way the stone will every fall to a position > 1 / 2. This means that in the final solution, the current node [0, 1 / 2] will come AFTER all nodes (descendents) that come after this one.

If we jumped to the right instead, creating a right child responsable for interval [1 / 2, 1] we can show the same way that the stone will never fall before the starting point 1 / 2. This means that the current node will com BEFORE all nodes (descendents) that come after this one, since we know that the stone can't fall on a postion < 1 / 2 from now on.

This is an algorithm: if in the i'th stone we jumped to the left, we now that stone i will become AFTER all next stones. If we jumped right, stone i will become BEFORE all next stones.

Code: 23071895

→ Reply
»
8 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Strange! My C++ code got accepted with printf but got TLE with cout. This is too harsh

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    printf is faster than cout. if u want to use cout its better type ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); in your code this make cout fast

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I'm unable to solve Escape from Stones in java. In spite of using fast io, it always gives me a TLE now matter how much i optimize it sol did anyone get it AC in java?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi akhi29
    Two points-
    1. Try to use StringBuilder (popular practice among Java user's) instead of directly printing to the output console.
    2. When you call, close() of PrintStream, it isn't obliged to flush your output to the console. You need to call flush() explicitly to ensure that the data, if present in the buffer is flushed to the output console. You can refer the modified submission 30322735

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In DIV 2 C I took 2 variables hi = 1 and lo = 0, if character is 'l' then I just change hi = (hi + lo) / 2 otherwise lo = (hi + lo) / 2 and mapped the value, sort them and print them, but got WA on Testcase 11, could you please tell me what is I'm missing?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I hope it may be because of the precision problem. I am also facing the same and below is my solution

    30185936

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      in DIV2 D what will be answer in case 5 : 2 4 8 6 9. My solution that got AC. outputs 5, but how? 8 is bigger than 6 they can't form a sequence

      → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In Div 1 A Stones falls in 'k' position and print the stone position from left

I calculated 'k' and 'd' as k=(X+Y)/2 and d=(Y-X)/2 And if 'l' then x-=d otherwise y+=d. then sorted the array which contains 'k' s value and its position no. but my implementation isn't matching with the test case..

Did I misunderstood the ques or my idea is wrong?

CODE

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The thing is that, suppose you only go left then it means that the stones would be at 1/2,1/4,1/8,...till 1/(2^(10^6)) (considering maximum length of the string) which can't be stored in the float value.

    → Reply
»
6 years ago, # |
  Vote: I like it -10 Vote: I do not like it

For those facing TLE in the problem Div1 A (Div2 C Escape from Stones) in C++ even with O(N) time complexity the reason can be endl vs '\n'.

'\n' inserts a new line to the output stream while

endl inserts a new line as well as flushes the output stream.

So using '\n'can solve the TLE issue.

Also you can use fast IO with cin/cout too instead of using scanf/printf by adding these lines in your code.

ios::sync_with_stdio(false);

cin.tie(0);

cout.tie(0);

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Believe it or not this actually solved the problem for me. I was using a linked list and basically pushing to the front and back and was confused how I was getting TLE with 1,000,000 O(1) operations. I ended up writing my own code for a linked list and still failed case 31, changing the endl to \n made it accepted. This made it go from 2000 ms TLE to 233 ms, thank you for your post.

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I solved div1A using a binary tree, if character is l then i add to the left of parent node otherwise i add to the right, then an inorder traversal will give the answer but im getting TLE at testcase 31 idk why since my code is implemented in O(n) complexity. My solution(https://mirror.codeforces.com/contest/264/submission/54413614)

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Something is wrong with the testing of the question Div 1(A)/ Div2(C) . Got 2 TLE's on a O(n) solution [Test Case 31] , changed endl and to '\n' and then got runtime error on test 41.

TLE — https://mirror.codeforces.com/contest/265/submission/63245660 Runtime Error — https://mirror.codeforces.com/contest/265/submission/63246396

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am facing the same problem. Were you able to fix it ?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No, i kept on getting runtime error with that approach.. so i changed my implementation a little bit, and it got accepted. Accepted Solution.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        I had to do this too. I guess the problem was caused because the second loop ( which is being run backwards ) was trying to access some invalid memory. The problems gets fixed when the array is reversed and loop is run forward.

        → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I have an another approach for div1B. for each number check the maxm times a divisor has occurred from all the divisors of a number and then increase the maxm by 1 and iterate again and update all the divisors

code 87253298

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain problem div2 B in more detail?

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Note that we can only move to the next tree, but not to the previous one. So, to eat all the nuts, we must start from the first tree and visit one by one until we reach the final one. When we are on the top of some tree-i (because we must go to the top to eat that nut), and eat the nut, then we should move to the next tree. If next tree has lower height, we have to move down to the same height and then jump (to save time). Otherwise, we can directly jump to the next tree (also to save time).

    → Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

DIV 1B / DIV 2D is there any other way to solve this problem without dp because i am not able to understand the editorial solution.

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

great contest

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good

→ Reply