josdas's blog

By josdas, history, 9 years ago, translation, In English

570А — Elections

We need to determine choice for each city. Then sum it for each candidate and determine the winner.

O(n * m)

Solutions

570B — Simple Game

Lets find which variant is interesting. For Andrew is no need a variant wherein |a - m| > 1 because we can increase probability of victory if we will be closer to m. Then we consider two variants, a = c - 1 and a = c + 1. Probability of victory will be c / n for first variant and (n - c + 1) / n for second.

We need to choose better variant, also we must keep in mind case of n = 1.

O(1)

Solutions

570C — Replacement

Lets find how replacements occur. If we have segment of points with length l,we need l - 1 operations and stop replacements for this segment. If we sum lenghts of all segments and its quantity then answer will be = total length of segments — quantity of segments. After change of one symbol length changes by 1.

Quantity of segments can be supported by array. Consider events of merging, dividing,creation and deletion of segments. For merging we need to find if both of neighbors(right and left) are points then merging occured and quantity of segments reduced by 1. Other cases can be cosidered similarly.

O(n + m)

Solutions

570D — Tree Requests

We need to write vertices in DFS order and store time of enter/exit of vertices in DFS. All vertices in subtree represent a segment. Now we can get all vertices in subtree v on height h as a segment, making two binary searches.

We can make a palindrome if quantity of uneven entries of each letter is less than 2.

This function can be counted for each prefix in bypass for each depth.

For saving the memory bit compression can be used considering that we need only parity and function is xor.

O(m * (log + 26) + n)

D had a offline solution too in O(n + m * (26 / 32)) time and O(n * 26 / 8) memory

Solutions

570E — Pig and Palindromes

We need palindrome paths. Palindrome is word which reads the same backward or forward. We can use it. Count the dynamic from coordinates of 2 cells, first and latest in palindrome.

From each state exists 4 transitions (combinations: first cell down/to the right and second cell up/to the left). We need only transitions on equal symbols for making a palindrome. Note that we need a pairs of cells on equal distance from start and end for each.

For saving memory we need to store two latest layers.

O(n3) — time and O(n2) — memory

Solutions

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

| Write comment?
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been translated by josdas(original revision, translated revision, compare)

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

Can you explain Problem D in a bit more detail.What is meant by in and out time of vertex.What is bypass the prefix.Doesn't makes much sense to average people like me.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Some of my thoughts: we can firstly compute the depth of each vertex and use a list to record the order of vertices in each depth. Let's consider the mentioned example (see the problem). the order of vertices in each depth is:
    Depth 1: 1
    Depth 2: 2, 3, 4
    Depth 3: 5, 6
    This process can help us quickly find the vertices in depth h for the required vertex v in the following. Going on, after that, we use DFS to record the in-time and out-time of each vertex. For the given example, we have the DFS order as follows:
    DFS order: 1, 2, 2, 3, 5, 5, 6, 6, 3, 4, 4, 1
    This can be addressed by applying the following pseudo-code:
    time = 1;
    DFS(vertex u)
        in[u] = time ++;
        for each son v
            DFS(v)
        out[u] = time++;
    The above-mentioned two steps can be considered as a pre-processing operation. Then, for each query, denoted by <v, h>, we find the answer as follows.
    Case 1: if h is no more than the depth of v, return "Yes".
    Case 2: if v has no posterity that locates in depth h, then return "Yes".
    Case 3: Otherwise, find the required vertices in depth h, and judge "Yes" or "No".
    It can be said that, Case 1 is easy to solve. Here, Case 2 and Case 3 will utilize binary search (BS) to find the answer. Clearly, we will use BS to find the most left vertex (posterity) and the most right vertex (posterity) in the Depth-list of depth h for the vertex v. The BS exploits the in-time and out-time to find the most left vertex and the most right vertex. For example, if we want to find the most left vertex in depth h for the vertex v, we use the following pseudo-code:
    l = 0, r = Depth[h].size() -1, ans_left = -1;
    while( l <= r )
        m = (l + r) >> 1;
        if vertex Depth[h][m] is posterity of v
            ans_left = m, r = m -1;
        else if the ancestor of Depth[h][m] in depth "dep[v]" is in the left of v
            l = m + 1;
        else
            r = m -1;
    Here, we will utilize the in-time and out-time of a vertex to judge that: whether a vertex A is the ancestor of a vertex B, or the left/right one of the ancestor of B in the Depth-list.
    An accepted source code: 12519227

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

      I read your code. I didn't get one thing. In the part-> int x = mp[make_pair(v, h)]; if( x == 1 ) puts("Yes"); else if( x == -1 ) puts("No"); else run(v, h); }

      Why do you even check for the value of x? Why don't you straight away use run(v, h) everytime? What is the use of even using a map? It will only be helpful if the same inputs are encountered. Right?

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

        It is a memorization technique.

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

      Can you explain me your time complexity? It seems to me that for each of the m query, you do two binary searches, and count the characters between ans1 and ans2. However, if (ans2-ans1) is big, isn't it going to be slow?

      I see you used map there. But how does it guarantee fast time complexity? I hope my question makes sense.

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

      How do we check whether the letters form a palindrome? Iterating through all the elements in the range might get a TLE exception.

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

Please elaborate Problem E also.You have not explained very clearly?

  • »
    »
    9 years ago, # ^ |
    Rev. 5   Vote: I like it +42 Vote: I do not like it

    Let's assume f(x1, y1, x2, y2) be the function which gives the number of ways of going from point (x1, y1) to (x2, y2).

    Now, the basic recurrence without memoization can be seen as :

    f(x1, y1, x2, y2) :
      if S[x1][y1] != S[x2][y2] : return 0
      if x1 > x2 or y1 > y2 : return 0
    
      // include the base case when have two neighbouring cells or single cell
      // if neighbouring cells have same value return 1
      // else return 0
    
      ans = 0
      ans = ans + f(x1 + 1, y1, x2 - 1, y2)
      ans = ans + f(x1, y1 + 1, x2 - 1, y2)
      ans = ans + f(x1 + 1, y1, x2, y2 - 1)
      ans = ans + f(x1, y1 + 1, x2, y2 - 1)
      return ans
    

    Also, one argument in the recursive function is dependent on other 3, if we know x1, y1 and x2, we could compute y2 because the points are such that the manhattan distance beetween (1, 1), (x1, y1) and (n, n) and (x2, y2) are same.

    So, we could have three arguments to the recurrence. And as there's no loop inside, time complexity of the solution after memoization would be O(n^3). But, space complexity will also be O(n^3). To make the solution run in required space (256MB), observe the fact that the current layer (equidistant set of points from (0, 0)) is only dependent on next set of layers (points with distance one more) we could write a bottom up dp with O(n^2) space. Storing just last one calculated layer everytime.

    I wrote top-down dp with memoization, got Memory Limit Exceeded, couldn't code bottom-up dp properly in time! :'(

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

      thanks a lot :) this is so much clearer (y)

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

      can u tell me more clear how to find y2?

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

        Assuming 1 based indexing and the corners to be at (1,1) and (n, m).

        Now, if we are at (x1, y1), it means that the count of total moves is :

        moves = (x1 — 1) + (y1 — 1) [Because at each step either x1 increments by one or y1 increments by one]

        Similarly, from bottom corner we get

        moves = (n — x2) + (m — y2)

        So y2 = n + m — x2 — x1 — y1 + 2

»
9 years ago, # |
  Vote: I like it +9 Vote: I do not like it

The problems were great, but these explanations are a bit lacking. Could you please explain the solutions in more detail?

»
9 years ago, # |
  Vote: I like it +9 Vote: I do not like it

C can be solved in _ O(nlogn+mlogn) _ using a Segment Tree, storing for each node the number of operation needed to transform the whole segment, and another 2 variables pref,and suff which allows to know if the segment has a "dot"-1prefix or "dot-1suffix" :) is a simple solution but it needs more memory 12518296

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

For C — regarding "...Quantity of segments can be supported by array." — we actually don't need to keep the segments. Rather we keep only current value of f() — and when we put a new symbol to the string — then f() changes by +-2, +-1 or 0. This depends solely on the old symbol and 2 its neighbors.

12510601

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

    I also tried to solve C this way, but got wrong answer. Could you take a look at my code? 12511578

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

      In the edge cases else if (t == n - 1) and else if (t == 0) the cur variable is not updated.

      Also I believe there can be out of bound issues in those edge cases, when n is 1 — as s[t - 1] and s[1] indexes are accessed there, which is surely beyond the string limits.

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

      A hint: you can also avoid dealing with those edge cases if you add a letter to the beginning and to the end of the string. This operation doesn't change f(s). After that your string will be of length n + 2 and all the replacement operations on it will be between indexes 1 and n inclusive — so the neighbours will never be out of string bounds.

      This makes code smaller — i.e. less errors possible, faster to type and verify.

      This is a general idea in many tasks — instead of dealing with edge cases — extend the field of work and work inside a sub field of that.

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

        this idea can save a lot of time from a newbie's point of view,thankyou!! :)

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

    At first I was trying to come up with a solution similar to the editorial, but then I realised that a change in F is only influenced by the neighbours.

    Anyways, here is my solution if anybody needs more help: 12512037

  • »
    »
    9 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Great, thanks, so simple :) AC 12522984

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

I am struggling with problem C

Can anyone give me a simplified explanation to it?

Thanks

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Consider the simplest case: The string, of length L, is formed by all dots. Clearly f(s) = L - 1.

    Imagine there k strings of consecutive dots of length L1, L2, ... Lk, separated by non-dot characters, the answer is just taking the sum of respective reductions, namely,

    Let's see how we can perform updates in constant time.

    Case 1: A segment's boundary becomes a non dot character. Number of dots reduced by 1, and number of segments is reduced by at most 1, depending on whether the segment is of length 1 or not. So the answer is reduced by at most 1.

    Case 2: A segment's boundary is extended by 1, but not merging other segments. Number of dots is increased by 1, number of segments unchanged. So the answer is increased exactly by 1.

    Case 3: A new segment is added (of length 1). This is the same as Case 2.

    Case 4: One segment is broken by two non empty segments (otherwise, it's just case 1). In this case, number of dots is reduced by 1, the number of segment is increase by 1. So the answer is reduced by 2.

    Case 5: Two non empty segments are merged. Number of dots is increased by 1, and the number of segments is reduced by 1. So the answer is increased by 2.

    So you need to check neighbors of the changing position to see which case the operation falls into and update the answer in constant time accordingly.

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

      Thanks alot I solved it correctly ... But when i surfed the internet , i found an algorithm (data structure) called suffix array . Can it be used to solve this problem?

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

    Each substitution on s[xi] (ci' -> ci) will only effect s[xi]'s two neighbors(s[xi-1] and s[xi+1], if it has). Only need to recalculate the value on (s[xi-1], s[xi], s[xi+1]).

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

Auto comment: topic has been updated by josdas (previous revision, new revision, compare).

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

Hi, I can't figure out what's wrong with my solution for D... Here it is: http://codeforces.net/contest/570/submission/12521712 Please help!

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

Problem D : Beware, Even printf , scanf giving TLE ;( using fast I/O got ACCEPTED .

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

    Your solution O(m * log * 26 + n). It is close to time limit.

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

    My solution took 1996 ms. I'm running in the house yelling "Damn!".

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

I am not able to understand why in problem B second variant probability is (n-c+1)/n . why it is not (c+1)/n .

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

    If A is greater than the number of M, we are winning on any value from A to N.

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

PROBLEM 570C-REPLACEMENT

for the test case:

3 3

...

1 .

2 a

3 b

ans should be:

2

0

0

correct me if i am wrong

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

For the first hour, I ended up solving the wrong problem C. now I am curious how to approach this problem, If instead of replace the operation was of insert . How would be approach the problem. eg : s="..as..qwert...." first query is 1 h s'="h..as..qwert...."

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

    Instead of an array using a balanced search tree. The need for surgery to insert and retrieve an item.

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

Can someone explain the author's solution of the tree-requests, i am trying to understand the xor part of the code but couldn't find any explanations..Here the link to the author's solution-

http://codeforces.net/contest/570/submission/12523757

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can you perhaps provide more explanations in your solution to problem 570E? For example, what are stored in the array ou[dd][dd] and in[dd][2 * dd]? What is sotred in the array Si? Also, what does the variable ts represent?

Thank you!

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

    ou[x][y] the position of the cell (x, y) on the diagonal.

    in[x][y] the number and position of the diagonal of the coordinate cell.

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

In D question, I did not understand the XOR part. Could someone explain me?

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

Problem D.I use technique similar to finding LCA,in order to find parent at i-th depth.But I have time limit,is this normal or the problem is in my code?code

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

In 570B Can anyone explain me the case when n is odd and the m is selected at middle of 1 to n range. (Say n=5 and m=3).Can't here we select both n/2 and n/2+2 as answer for a?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    hi if you see this comments please do tell me to if you found the ans

»
6 years ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

Could anyone explain in problem B 570B - Simple Game the case that are n = 1 and m = 1 , how the answer is 1 ,please ?? Although the problem says { The boys agreed that if m and a are located on the same distance from c, Misha wins.}

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

    if you read the output section carefully you will notice that the problem say " If there are multiple such values, print the minimum of them."

    so in your case you can choose any number because all numbers there probability is zero but the minimum one is "1".

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

570D Can also be done using DSU on trees. See this blog.

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

    How do you use DSU on trees in this problem?

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 3   Vote: I like it +3 Vote: I do not like it

      Yes. You can see this submission. If you understand the blog, it'll be easy to understand the solution. Do let me know if there's anything confusing in the code.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

C-Replacement has a very simple solution Code : https://codeforces.net/contest/570/submission/81380215 Explaination: If a new . is added to a position i,(which currently has alphabet) there are 3 cases: 1. if it is causing merging of two groups-in that case i-1 and i+1 will also have . and f(s) will increase by 2. 2. if it is creating a new group-in that case i-1 and i+1 will have alphabets,and no change in f(s). 3. if it is adding to a current group-in that case either i-1 will have . or i+1 will have . but both i-1 and i+1 simultaneously don't have . , in that case f(s) increase by 1 Similarly,If a new alphabet is added in place of dot: if it breaks a group into two groups , f(s) decreases by 2 if it reduces length of a group f(s) decreases by 1 if it takes place of a single . (i.e. no dot is present on left or right) then no change

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

Can anyone check my submission for problem D? 91924931 I think it's O(nlog(n) + 26m). Am I right? Thank you.

»
2 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Problem $$$E$$$ is a replica of this USACO problem. I guess the USACO problem is a little easier because you don't have to deal with annoying parity stuff, but it's still basically the same problem...

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

nice round

»
20 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

570B: If n is odd and m is the middle point,then why a=m-1? Why not a=m+1??

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

    Both have same probability and since m-1<m+1, we use m-1. The problem statement states that "If there are multiple such values, print the minimum of them."

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does this code get WA On #14 in the Problem D?

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
string color;
long long n,m,bfn[500010],bfn_rep[500010],dfn[500010],dfn_rep[500010],cnt_bfn,cnt_dfn,dep[500010],dep_left[500010],dep_right[500010],siz[500010];
struct segtree
{
	long long sum[500010],type;
	void build()
	{
		for(long long i=1;i<=n;i++) sum[i]=sum[i-1]+(color[bfn_rep[i]]-'a'==type);
	}
	long long query(long long x,long long y)
	{
		return sum[y]-sum[x-1];
	}
}tree[26];
vector<long long>graph[500010];
void bfs()
{
	queue<pair<long long,long long>>q;
	q.push(make_pair(1,1));
	while(!q.empty())
	{
		long long from=q.front().first,now_dep=q.front().second;
		q.pop();
		bfn[from]=++cnt_bfn;
		bfn_rep[cnt_bfn]=from;
		dep_left[now_dep]=dep_left[now_dep]==0?bfn[from]:dep_left[now_dep];
		dep_right[now_dep]=bfn[from];
		dep[from]=now_dep;
		for(long long to:graph[from])
			q.push(make_pair(to,now_dep+1));
	}
}
void dfs(long long now)
{
	dfn[now]=++cnt_dfn;
	dfn_rep[cnt_dfn]=now;
	siz[now]=1;
	for(long long to:graph[now])
	{
		dfs(to);
		siz[now]+=siz[to];
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(long long i=2;i<=n;i++)
	{
		long long fa;
		cin>>fa;
		graph[fa].push_back(i);
	}
	cin>>color;
	color.insert(color.begin(),'0');
	bfs();
	dfs(1);
	for(long long i=0;i<26;i++)
	{
		tree[i].type=i;
		tree[i].build();
	}
	for(long long i=1;i<=m;i++)
	{
		long long u,h;
		cin>>u>>h;
		if(dep[u]>h)
		{
			cout<<"Yes\n";
			continue;
		}
		long long l=dep_left[h],r=dep_right[h],x=0,y=0;
		while(l<=r)
		{
			long long mid=(l+r)>>1;
			if(dfn[bfn_rep[mid]]>=dfn[u])
			{
				x=mid;
				r=mid-1;
			}
			else l=mid+1;
		}
		l=x,r=dep_right[h];
		while(l<=r)
		{
			long long mid=(l+r)>>1;
			if(dfn[bfn_rep[mid]]<=dfn[u]+siz[u]-1)
			{
				y=mid;
				l=mid+1;
			}
			else r=mid-1;
		}
		long long len=y-x+1,sum_odd=0;
		for(long long j=0;j<26;j++)
		{
			long long tmp=tree[j].query(x,y);
			if(tmp%2) sum_odd+=tmp;
		}
		if(x==0||y==0) cout<<"Yes\n";
		else if((len%2==0&&sum_odd>0)||(len%2==1&&sum_odd!=1)) cout<<"No\n";
		else cout<<"Yes\n";
	}
}