UWCOI20F - Blocks - Editorial

F. Blocks:

Link to Practice
Link to Contest

Author: Soumyaditya Choudhuri (socho)
Tester: Taranpreet Singh (taran_1407)
Editorialist: Soumyaditya Choudhuri (socho)

DIFFICULTY:

MEDIUM

PREREQUISITES:

Z-FUNCTIONS, PRIME FACTORISATION, BINARY SEARCH

PROBLEM:

You are not given a hidden string S, of length N. You are given the length N. You are able to query the Z-function of the string S at most Q times. Find the maximum number of repeating blocks in the compressed representation of S, using at most Q queries.

Subtask 1 [28 points]: Q = 240
Subtask 2 [33 points]: Q = 20
Subtask 3 [39 points]: Q = 9

QUICK EXPLANATION:

We prime factorise the number N. We then calculate the contribution of each prime factor to the final answer by fixing all other prime factors to the maximum, and binary searching over the minimum possible contribution of this prime factor.

EXPLANATION:

This task essentially allows you to query the Z-function of a hidden string to obtain the maximum number of blocks in the ā€œcompressedā€ representation of the string. The fundamental observation in this task, is that if you query index i and the result of i + query(i) == N, then the block from 0..i-1 is a valid repeating block. More information can be found at the CP-algorithms article for the Z-function. In our editorial, we only discuss how to reduce the number of queries.

Subtask 1

In the first subtask, we are allowed 240 queries. In particular, we note that the number of blocks in a compressed representation of a string can only be some factor of N itself. We notice that the number \leq 1000000 with the maximum number of factors is 720720, which has 240 factors. We simply query for each of these factors to be the block length, in ascending order. If i is the minimum factor for which the query works, there must be N/i blocks in the string, which is what we answer.

Subtask 2

In the second subtask, we are allowed 20 queries. We consider the prime factorisation of the number N. Instead of finding the maximum number of blocks K, we focus on finding the minimum length of the blocks B which can be used to make the string. It is easy to revert the answer using KB = N.

In particular, the important observation to make is that if blocks of size B can be repeated K times to make our hidden string, blocks of size 2B can be repeated K/2 times to also make the hidden string (as long as K/2 is an integer). Similarly, if blocks of size B can be repeated K times to make our hidden string, blocks of size 3B can be used K/3 times to make the hidden string (as long as K/3 is an integer), and so on. This makes us realise that we can calculate the contribution of each prime factor to finding the value of B independently.

To calculate the contribution of each prime factor, we first set all other prime factors to the maximum possible exponent, which is the exponent in N. By setting all other prime factors to the maximum possible exponent, we ensure that the divisibility of the other prime factors in the answer will not affect the calculation for this prime factor. We then sequentially test every possible exponent of this prime factor, for the least contribution which works as a valid block.

Here is an example where N = 240:

The prime factorisation is then 2^4 * 3^1 * 5^1. Letā€™s say the minimum block size is 6.

To calculate the contribution of the prime factor 2 to our answer, we first fix the contributions of 3 and 5 to the maximum possible, which is 3^1 * 5^1 = 15.

We then try the contribution of 2 as 0, so 2^0, which makes 15 * 2^0 = 15. This is an invalid block size (it is not a multiple of 6), so we continue searching.

We now try the contribution of 2 as 1, so 2^1, which makes 15 * 2^1 = 30. This is a valid block size (it is a multiple of 6), so we note the final contribution of 2 to our answer as 2^1 = 2.

We now attempt to calculate the contribution of the prime factor 3 in our answer. We fix the contribution of 2 and 5 to the maximum, which is 2^4 * 5^1 = 80. We try to use the contribution of 3 as 0, which makes 3^0 = 1. Then, the block size we try is 80 * 1 = 80, which is not a multiple of 6, so will not work. We then try 3^1 as the contribution of 3 in the answer, which is 240. This is a multiple of 6, so it will work. We note that the final contribution of 3 in our answer is 3^1 = 3.

We repeat the idea for 5. At the end, we multiply all our calculated contributions, using 2^1 * 3^1 * 5^0 = 6, which gives us the value for B. Then, we use the equation KB = N or K = N/B to find the answer. This solution uses at most 19 or 20 queries.

Subtask 3:

The last subtask builds onto the previous subtask. We notice that if a^b is a valid contribution of the prime factor a, then a^{b+1} is also a valid contribution of the prime factor a. This means that the validity of the exponent is monotonic, which means that we can use binary search over each exponent, while applying the same solution as before. This solution uses at most 9 queries, and obtains a perfect score for this problem.

SOLUTIONS:

Setter's Solution
#include "bits/stdc++.h"
using namespace std;

int n;
map<int, int> done;

int query(int pos) {
	if (done.find(pos) != done.end()) return done[pos];
	cout << "? " << pos << endl;
	int ans;
	cin >> ans;
	return done[pos] = ans;
}

int pw(int n, int k) {
	if (k == 0) return 1;
	return n * pw(n, k-1);
}

bool works(int x) {
	if (x == 0) return true;
	if (x == n) return true;
	return query(x) + x == n;
}

void answer(int ans) {
	cout << "! " << ans << endl;
	int res;
	cin >> res;
	if (res != 0) exit(0);
}

void blocks(int N) {
	// return the maximum number of blocks in S!
	// to query a position i, do query(i)
	done.clear();
	map<int, int> prime_factorise;
	int num = N;
	n = N;
	for (int i=2; i*i <= num+4; i++) {
		while (num % i == 0) {
			prime_factorise[i]++;
			num = num / i;
		}
	}
	if (num > 1) {
		prime_factorise[num]++;
	}
	int prod = 1;
	
	for (map<int, int>::iterator x=prime_factorise.begin(); x!=prime_factorise.end(); x++) {
		int fa = x->first;
		int in_num = x->second;
		
		int low = 0;
		int high = in_num + 1;
		
		int full = N / pw(fa, in_num);
		
		//cout << full << ' ' << fa << ' ' << low << ' ' << high << endl;
		
		while (low + 1 < high) {
			int mid = (low + high) / 2;
			int x = full * pw(fa, mid);
			if (works(x)) {
				high = mid;
			}
			else {
				low = mid;
			}
		}
		
		if (works(full * pw(fa, low))) {
			prod *= pw(fa, low);
			//cout << " > " << low << endl;
		}
		else {
			prod *= pw(fa, high);
			//cout << " > " << high << endl;
		}
		
	}
	
	answer(N / prod);
}

int main() {
	
	int t;
	cin >> t;
	while (t--) {
		int n, q;
		cin >> n >> q;
		blocks(n);
	}
	
}
Tester's Solution
import java.math.BigInteger;
import java.util.*;
import java.io.*;
import java.text.*;
public class Main{
    //SOLUTION BEGIN
    //Into the Hardware Mode
    void pre() throws Exception{}
    void solve(int TC)throws Exception {
        int n = ni(), q = ni(), x = n;
        int[] a = new int[10], p = new int[10];int c = 0;
        for(int i = 2; i<= x; i++){
            if(x%i != 0)continue;
            a[c] = i;
            while(x%i == 0){
                x /= i;
                p[c]++;
            }
            c++;
        }
        int ans = 1;
        for(int i = 0; i< c; i++){
            int lo = 0, hi = p[i];
            while(lo+1 < hi){
                int mid = (lo+hi)>>1;
                int sz = ans*pow(a[i], mid);
                if(query(n, n/sz) == n-n/sz)lo = mid;
                else hi = mid-1;
            }
            int sz = ans*pow(a[i], hi);
            if(query(n, n/sz) == n-n/sz)lo = hi;
            ans *= pow(a[i], lo);
        }
        pni("! "+ans);
        hold(ni() == 0);
    }
    int pow(int a, int x){
        int cur = 1;
        while(x-->0)cur *= a;
        return cur;
    }
    int query(int n, int ind) throws Exception{
        if(ind == 0)return n;
        if(ind == n)return n;
        pni("? "+ind);
        return ni();
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    void exit(boolean b){if(!b)System.exit(0);}
    long IINF = (long)1e15;
    final int INF = (int)1e9+2, MX = (int)2e6+5;
    DecimalFormat df = new DecimalFormat("0.00000000000");
    double PI = 3.141592653589793238462643383279502884197169399, eps = 1e-7;
    static boolean multipleTC = true, memory = true, fileIO = false;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        if(fileIO){
            in = new FastReader("");
            out = new PrintWriter("");
        }else {
            in = new FastReader();
            out = new PrintWriter(System.out);
        }
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();
        for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
        else new Main().run();
    }
    int find(int[] set, int u){return set[u] = (set[u] == u?u:find(set, set[u]));}
    int digit(long s){int ans = 0;while(s>0){s/=10;ans++;}return ans;}
    long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
    int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }
            return str;
        }
    }
}
2 Likes

if you query index i and the result of i+query(i)==N, then the block from 0\cdots iāˆ’1 is a valid repeating block

Once we find that i+query(i)==N for some i shouldnā€™t we check for all valid intervals to be sure that the repeating block is valid?

If password is helloworldhello and we query for the last hello, then i+query(i)==N, does it mean that first hello is a valid repeating block?