Codeforces исполнилось 10 лет! Мы рады анонсировать краудфандинг-кампанию. Поздравьте нас по ссылке https://codeforces.com/10years. ×

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

Автор veschii_nevstrui, 2 года назад, По-русски,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Проголосовать: нравится
  • +53
  • Проголосовать: не нравится

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

why problems A to C are Russian ?

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

    because the problemsetters realized their mistakes in statements during the contest and now they are checking translation twice before publishing. be patient

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

How to prove that the order of the selected guests is not important in 907E - Вечеринка ?

Sorry, I think the Russian version analyzes this fact and so the English will. This comment has no point.

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

    We can think of it this way -- the problem can also be thought of this way.

    Given a graph G = (V, E), what's the fewest number of vertices we can mark such that for every a and b in the graph G, there is a path between a and b such that all vertices on this path (except for possibly a and b) are marked.

    This restatement makes it clear that the order of the guests is not important.

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

    Here is another way of thinking about it:

    Consider two guests a,b with a being friends with b and x, while b is friends with a and y.

    If a is processed first, then x and b will become friends, then when b is processed a and y, x and y will become friends.

    If b is processed first, then a and y will become friends, then when a is processed b and x, x and y will become friends.

    Either way the same endstate is reached.

    Thus we can switch any adjacent guests without changing the endstate, so we can order the processing of the guests in any way we want (sort of like bubble sort) without changing the endstate.

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

"There are a couple of corner cases:" Goes onto listing 9 of them.

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

    To be fair 6 and 7 can be combined by putting the segment with the even numbers first, but thats still 8 cases.

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

The images in 906E — Reverses are broken.

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

For 906E, what is the algorithm to split a string into a minimum number of palindromes (presumably in linear time, given the constraints)?

I've found a description of an algorithm for deciding whether a string can be written as a sequence of even palindromes (P*) here, but it doesn't seem like it could be easily extended to find the minimum number of such palindromes.

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

    I've also just come across this paper from 2014, which gives a O(N log N) algorithm for finding the minimum number of palindromes in a decomposition — that still sounds too slow for N = 5 × 105.

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

      O(N log N) too slow for N = 5 * 105?

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

      Actually, I use the algorithm described in this paper. I have no idea why it is more than 20 times slower than one using the palindromic tree. It is also very unbelievable to me that solution with n = 106 can finish in 62ms.

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

        To be honest, problem was changed few hours before the contest and I had not much time to prepare good testset. It is possible that bound on length of series isn't met in tests in such way that it lead the complexity to be in total.

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

    You can check out my old entry on this topic.

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

      Thanks, I'll give it a read when my brain is more awake — but it's still O(N log N) rather than linear. Is that fast enough for N = 5 × 105 (actually 106 since you interleave the two strings)?

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

        Why would it be too slow? I think is just fine for n = 106 and 2s TL. And this solution also tends to have really good constant..

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

          Also in practice the length of the serial links chain should be less than (I seriously don't know how to create a test for which to have a decent amount of chains with length approximately ).

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

          Frequently O(N log N) isn't fast enough for problems with n = 106, but as you say, the constant factor is low. It probably also helps that the I/O is very cheap.

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

Can anyone help me to understand why is it possible to use random approach in div2E?

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

Good tutorial! But in problem div.1 D, I wonder why  holds? Can anyone explain it a little bit? Thanks a lot!

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

I think in the tutorial to Problem 907A — Masha and Bears, the point 4-->(Masha likes last car, so it's size is not more than 2·V3) must be (Masha likes last car, so it's size is not more than 2·Vm) . @veschii_nevstrui

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

What am i doing wrong here for D?

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

Does anybody know any link for proof for statements made in 906D?

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

plzz help in problem C??

in test case 7, I m getting 12 as the answer but the answer is 67?

Your code here...

#include<iostream>
#include<bits/stdc++.h>
#include<string.h>
using namespace std;
char b[1000000];
int main(){
	int n;	
	vector<int> st(26);	
	cin>>n;
	char  a;
	int cnt=0,i;
	int stt=0;
	for(i=0;i<n;i++){
		if(cnt==1){
			break;		
		}
		scanf(" %c %s",&a,b);
		if(a=='!'){
			if(stt==0){
				stt=1;
				int sz=strlen(b);
				for(int j=0;j<sz;j++){
					if(st[b[j]-'a']==0){
						cnt++;
						st[b[j]-'a']=1;					
					}					
				}
			}
			else{
				int sz=strlen(b);
				for(int j=0;j<sz;j++){
					if(st[b[j]-'a']==1){
						st[b[j]-'a']=2;					
					}					
				}
				for(int j=0;j<26;j++){
					if(st[j]==1){
						cnt--;
						st[j]=0;	
					}
					else if(st[j]==2){
						st[j]=1;
					}
				}
			}			
		}
		else if(a=='.'){
			int sz=strlen(b);
			for(int j=0;j<sz;j++){
				if(st[b[j]-'a']==1){
					cnt--;
					st[b[j]-'a']=0;					
				}		
			}
		}
		else if(a=='?'){
			if(st[b[0]-'a']==1){
				cnt--;
				st[b[0]-'a']=0;					
			}		
		}
	}
	int cr;
	cnt=0;
	int cnt1=0;
	for(int j=0;j<26;j++){
		if(st[j]==1){
			cnt1++;
			cr=j;			
		}	
	}
	for(;i<n-1;i++){
		scanf(" %c %s",&a,b);
		if(a=='!'){
			cnt++;	
		}
		else if(a=='?'){
			{
				cnt++;			
			}	
		}		
	}
	
	cout<<cnt;
}

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

Why Probelm D has tag "chinese remainder theorem"?
I think it should be replace with “Euler Theorem”

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

"Masha doesn't like first two cars, then their sizes are more than 2·Vm;"

Written where? I didn't get this..

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

can someone explain solution of div 2 C shockers problem in easy way??with use of set or without it also?? relpy fast pls