Блог пользователя dalex

Автор dalex, 10 лет назад, По-русски

Не так давно в нашем вузе был проведен очередной отборочный контест на четвертьфинал ACM ICPC, по результатам которого мы отобрали команды, которые поедут в Саратов этой осенью. Тренировка по задачам этого контеста состоится в воскресенье, 21 сентября, в 11.00.

Ссылка на контест: 2014, Отборочный контест СГАУ на четвертьфинал ACM ICPC

Список предыдущих наших контестов:

Есть разбор задач на русском языке: https://www.youtube.com/watch?v=yLwyPXNEpYM Сразу извиняюсь за то, что я фигово разбираю задачи (мои были A, B, H, J), больше такого не повторится, т.к. я заставлю все задачи разбирать craus-а — он это делает наиболее круто.

  • Проголосовать: нравится
  • +104
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Thx~It seems Chinese have no time to participate in it because of the online contest

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А у нас отборочный в том году был таким: межвузовская олимпиада студентов, каждый сам за себя, 6 задач, пять из которых, благодаря своим ограничениям, решались с помощью полного перебора, и только по одной нужно было действительно динамику писать. Первые 6 человек в олимпиаде с нашего вуза образовали две команды, и было это всего за неделю до поездки на четвертьфинал. За эту неделю наша команда успела собраться 2-3 раза, совсем немного по-готовились, и на четвертьфинале смогла решить всего 2 задачи. Это был неплохой результат для первой поездки, так как обычно новички с нашего вуза решали ноль задач первый раз (собственно, именно такой результат продемонстрировала вторая команда).

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

Извините открылось.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Там же клар написан: использовать PDF-версию

»
10 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Задачи просто отличные!

Если бы не тупил так много, решил бы штук 7 :)

Столько глупых ошибок, оооох, надо работать над собой)

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    То есть в принципе есть резон командой их прорешать, да? Мы просто не очень скилловые, если сравнивать с Саратовом, в тренировках Станкевича решали 2 задачи максимум и поняли, что нет смысла его задачки решать, рановато...

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

      Фиолетовым самое то наши контесты решать, а потом еще в дорешку все задачи сдавать. Тренировки Станкевича намного сложнее (хм, я подумал, что ты про контесты Станкевича; хотя если имелись в виду neerc.ifmo.ru/trains, то они равно сложнее).

»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

How to solve E.? My idea was to use DP. Try all possible split points and solve sub-problem (like matrix chain multiplication) but I couldn't implement it (size of string was an issue as well).

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    no DP lol, just check for odd and each char contains less then n/2 times.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Could you elaborate?

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        map<char, int> s;
        	int i, count = 0;
        	char c;
        	scanf("%c", &c);
        	while (c != '\n')
        	{
        		s[c]++;
        		scanf("%c", &c);
        		count++;
        	}
        	if (count % 2)
        	{
        		cout << "NO";
        		return 0;
        	}
        	for (c = 'a'; c <= 'z'; c++)
        	{
        		if (s[c] > count / 2)
        		{
        			cout << "NO";
        			return 0;
        		}
        	}
        	cout << "YES" << endl;
        
        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Why is this correct?

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            When you have exact n/2 same letters (for ex. 'a') your strategy is to erase letter 'a' and not 'a'. After this operation you'll have again half 'a' letters.

            It is clear that it is possible.

            You can't erase more than 1 letter 'a' per turn. You are going to do n/2 turns, so you must have less or equal n/2 'a' letters =)

            Sorry for my bad english.

            • »
              »
              »
              »
              »
              »
              »
              10 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Could someone explain me why this is not correct?

              I have an stack, for each letter I check the letter on the top of my stack. If it's the same I "push" the new letter, otherwise I "pop" the last one (different letters so could be eliminated) At the end I check the size of my stack, if it's zero my answer is YES

              • »
                »
                »
                »
                »
                »
                »
                »
                10 лет назад, # ^ |
                  Проголосовать: нравится +5 Проголосовать: не нравится

                Your algorithm can't pass test "abcc":

                1. Push 'a'
                2. 'b' != 'a' => Pop 'a'
                3. Push 'c'
                4. 'c' == 'c' => Push 'c'

                Size of stack will be 2 and your answer will be "NO"

                But you can remove 'b' and 'c', then 'a' and 'c', so correct answer is "YES"

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I can be proved by math induction!

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    My friend solved this with an extremly short greedy algorithm. Define d[x] as the number of letter x in the string. Declare it as d[300] so that it cover all kind of letters in the ASCII table (not needed though).

    At the start of the algorithm: res = s.length(); Then we iterate through every possible character x, and decrease res by d[x]. If d[x] > res-d[x] then the result is NO, else if the algorithm reach the end, the result is YES.

»
10 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

Guys, can you explain why you write all these treaps and splay trees in problems that don't require them?

»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

What is the approach to solve problem I ? In sample test 3 , Why is there no possible answer : I think the possible answer might be 1 2 3 2 . I might be wrong , am I missing anything ?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    two region is differents color if only if these is neighbors. In other word if region u the same color region v -> these ara not neighbors

»
10 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

How to solve Problem K (Two Pirates)? Why is greedy approach not working for this problem? And what can be perfect approach to solve this question.Any help?

  • »
    »
    10 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

    A counterexample to greedy : 99,1,2,100.

    My method :

    Use DP, let dp[2k] denote the maximum that the first pirate can get after 2k turns, and the two pirates take only the first 2k items. So we can write dp[2k]=max( dp[2k-2]+a[2k-1] , dp[2k-2]+a[2k] , dp[2k-2]-m+a[2k-1]+a[2k] ),

    where m is the minimal value that the first pirate took in dp[2k-2].

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      My code gives 199 2 as output for this test case.That is as expected to happen.And can you please explain your DP .How you come to it ?

      Here is what I did : Suppose I am having a segment tree to update an elemnt and find maximum in a range. cin>>arrLength;

      long long  s=0;
      for(long long  i=0;i<arrLength;i++){
          cin>>data[i];
          s+=data[i];
      }
      initSegmentTree();
      buildSegmentTree();
      long long A=0;
      long long B=0;
      long long  c=0,j,d=0;
      for(long long  i=0;i<arrLength;i+=2){
              for(j=c;j<arrLength;j++){
                  if(data[j]!=INT_MIN)
                  break; 
              }
              c=j;
              for(j=c+1;j<arrLength;j++){
                  if(data[j]!=INT_MIN)
                  break;
              }
              if(j>=arrLength)
              {
                  A+=data[c];
                  break;
              }
              d=j;
              long long  pos = query(c,arrLength-1);
              if(data[pos]-data[c]>data[c]-data[d]){
                  A+=data[pos];
                  update(pos,INT_MIN);
                  update(c,INT_MIN);
                  c++;
              }
              else{
                  A+=data[c];
                  update(c,INT_MIN);
                  update(d,INT_MIN);
                  c++;
              }
      }
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      First of all, thanks for the solution. :)

      I tried to implement your idea, and it passes the 2 given test cases (and the ones I made) but I keep getting Wrong Answer on Test Case 1.

      Can somebody help me in figuring out where is my mistake?

      My code: 7949600

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Anti-greedy test: 6 3 8 7 2 4 1 5. We should take 8 and 7, and remain 6 and 3 at the first two iterations.

    The process described in the problem is equivalent to the following: the first pirate takes all items, but every even step he throws away the cheapest one. Easy to implement with priority queue.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Is answer for your test case 23 13 (As is provided by my approach)?Also whats the priority criteria to throw away the cheapest item.Please explain.Is position of element used as priority criteria?

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        Optimal solution is 24 12: first pirate takes 8, 7, 5 and 4.

        About priority criteria: is the word "cheapest" so unclear?

        On every prefix [1, k] of the array (k is even) first pirate must take no more than k/2 items. Think about it. But we take all items, and when we discover that we have taken too many items, we throw away the one with the lowest price. It happens after every even turn.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

someone explain the approach behind problem M

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    Answer:

    Length — a*b

    (b-1)*a+1, (b-1)*a+2, .. (b-1)*a+a, (b-2)*a+1,(b-2)*a+2,..,(b-2)*a+a, ..., 1,2..,a

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Excuse me, could anyone explain the meaning of Prob A? Where is the black hole and whether it could move? Thanks a lot!

Sorry for my poor English.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    You have a circle moving into a triangle, you cant move so 1 point of circle is out of triangle. Calculate the (surface where some point of circle can be)/(surface of triangle)

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Any hints for solving C and I( I don't understand simple test case #3)?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    To solve the problem I, read this: https://en.wikipedia.org/wiki/If_and_only_if

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Of course, i know what is "if and only if".

      But i understand from this: "The final version of the map two regions must have different color if and only if they are neighbour regions." => I can use only two colors or i'm wrong?

      Can you check my code 7895549?

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Why only two colors? If we invert that statement, we get "two regions must have the same color if and only if they are not neighbour regions". Create the inverse of the graph and paint each connected component its own color. Then check if all conditions are satisfied.

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Sorry , could you please elaborate . I didn't get your comment.

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            1. Condition (two regions must have different color if and only if they are neighbour regions) is equivalent to (two regions must have the same color if and only if they are not neighbour regions).

            2. Consider an inverse graph. All its neighbour vertices must have the same color.

            3. Find its connected components and paint each of them its own color.

            4. Check if the condition from (1) is true.

            • »
              »
              »
              »
              »
              »
              »
              10 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              At first I thought the problem was asking for whether the graph is k-color-able or not. Now I realize that I misunderstood the problem. "if and only if" really changed the meaning.

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    C Let a and b the desired numbers, then:

    a*b=n*(a+b) -> a*b-n*(a+b)+n*n=n*n -> (a-n)*(b-n)=n^2, so

    a-n and b-n — divisors of n^2. (a,b) = (d+n,n^2/d+n)

    We need to find all divisors of n^2.

    You can find the factorization of n for sqrt(n). n = p1^a1*...*pk^ak, n^2 = p1^(2*a1)*...*pk^(2*ak). And then recursively find all possible divisors of n^2 using factorization of n^2.

    http://pastebin.com/LVKRQaEq

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

      Another solution of C:

      n * (a + b) = ab

      Let's g = gcd(a, b), so a = g * a', b = g * b'

      n * g * (a' + b') = g * g * a' * b' -> n * (a' + b') = g * a' * b'

      g = n * (a' + b') / (a' * b')

      We can see, that gcd(a', b') == 1 -> a' and b' can't be divisors of (a' + b') -> a', b' are divisors of n

      So solution is: Iterate over all pairs(a', b') of divisors n, check gcd(a', b') == 1, find g = n * (a' + b') / (a' * b') -> a = g * a', b = g * b'

      http://pastebin.com/LtBR5Suh

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        This is how i solved the problem.

        ab = nab => b = na/(a-n)

        This is a function b(a). Graph has asymptote a = n. For all (a < n) => b < 0. => Our possible b looks like b = n + c = na/(a-n); where is c >= 1. Ok, lets solve this.

        a = n*n/c + n; b = n + c.

        code: http://pastebin.com/rU1cDd1L

»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Can someone tell me why my solution for problem E is not correct ? Basically, my idea consists of matching each character with another one different from it.

 string s;
	cin >> s;

	int al[26];
	for( int i = 0; i < 26; i++ )
		al[i] = 0;

	int n = s.size();
	for( int i = 0; i < n; i++ )
		al[s[i] - 'a']++;

	sort(al, al+26);
	reverse(al, al+26);
	
	bool ok = 1;
	for( int i = 0; i < 26; i++ ) {
		for( int j = i + 1; j < 26; j++ ) {
			int del = min(al[i], al[j]);

			al[i] -= del;
			al[j] -= del;
		}

		if( al[i] != 0 ) ok = 0;
	}

	if( ok ) cout << "YES" << endl;
	else	 cout << "NO"  << endl;

	return 0;
}
»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Does problem L use splay?Can it use other idea?

»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Can problem L use other idea other than splay?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +40 Проголосовать: не нравится

    Use three deques: for left, middle and right parts, and one boolean flag — if the middle part is reversed.

    ALMOST EVERYONE has used treaps or splay trees. It's just a three star local SSAU contest, of course, there is much easier solution!

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you explain it in more detail?How does the reverse operation update?

      • »
        »
        »
        »
        10 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Easy, just midReversed ^= true.

        Then, if you move one of the heads, let's say it's the left head moving to the left, you should 1) pop the last character from the left deque 2) push it into the mid deque, and depending on midReversed flag it is push_front or push_back.

»
10 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

How to solve A.?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Simple geometry: http://ideone.com/bEzVz0

    The key thing is a knowledge about similar triangles and their proportions: https://en.wikipedia.org/wiki/Triangle#Similarity_and_congruence

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I did not understand your solution. How did you use similar triangles? The only part I understood is using Heron's theorem for area. Please explain.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        1. S == p*r

        2. If S1 and S2 are the areas of two similar triangles, then S1 / S2 == k^2, where k is a ratio of their sides

        3. The same is correct for the areas of the similar parts of the similar triangles

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Let me try to explain it.(Atleast my solution, don't know if it is the best one) With Cosine Theorem, we can calculate angles of the given triangle. Now, we need to subtract from area 3 surfaces(in every corner, one), where some point of the circle will never be albe to be in. The picture will look like this: The famous picture You need to subtract the red surface from red+green one Colored one^^ Red+green one is 2*surface of right-angled triangle with sides r and the opposite angle one of the angles of the triangle/2(Can be easy calculated by some easy trigonometry) Red one is (PI-angle/2)/(2*PI)*(r*r*PI) (Surface of the circle) Do that for every 3 points(A,B,C), add the green surfaces, and print 1-(sum of green surfaces/area of rectangle(Can be calculated with Heron's formula. Wish I helped.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      It's like using splay trees in problem L, see my solution above :)

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In Problem G, I tried a greedy approach since all coins are multiples of each other ! But it doesn't work can someone give me a counter example!
My code is here

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    It doesn't work because you haven't thought about overflow of integer types.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thank you ! I thought that the max would be 109 × 105 while it is 109 × 105

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Just stop that if coinValue>sum, you wont be able to use that coin eitherway.

»
10 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

How to solve H,J,K?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    H: binary search on the cost of the cheapest trick made

    J: find the answer in the following form: aa..aabcaa..aadeaa..aafg......

    K: see in the comments above

»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

can we have an editorial?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You can find parts of editorial in comments here or ask for the missing problems

»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

How to solve I?

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What's test 24 of prob C? I got TLE but I don't know why.

»
10 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Спасибо авторам задач, очень понравились задания.

»
10 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

My codes: A B C D E F G H I J K L M