algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

commit ba0f42996af843faf912ed82c46a3708092e69e5
parent ee86843858c87fa3134aedcd2db76ecd953dfd61
Author: Andrew Laack <andrew@laack.co>
Date:   Thu, 15 Oct 2026 18:23:04 -0500

TLE cf problem xor

Diffstat:
Acomp/xor-transformations-easy/ex1.txt | 15+++++++++++++++
Acomp/xor-transformations-easy/ex2.txt | 15+++++++++++++++
Acomp/xor-transformations-easy/main.cpp | 86+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/xor-transformations-easy/problem.txt | 31+++++++++++++++++++++++++++++++
Acomp/xor-transformations-easy/thoughts.txt | 50++++++++++++++++++++++++++++++++++++++++++++++++++
5 files changed, 197 insertions(+), 0 deletions(-)

diff --git a/comp/xor-transformations-easy/ex1.txt b/comp/xor-transformations-easy/ex1.txt @@ -0,0 +1,15 @@ +4 +5 1 +0 0 1 1 1 +1 +5 2 +6 7 8 9 15 +0 +1 +8 2 +102 92 15 19 25 54 62 36 +2 +1 +10 1 +56 73 81 23 17 92 50 34 67 78 +2 diff --git a/comp/xor-transformations-easy/ex2.txt b/comp/xor-transformations-easy/ex2.txt @@ -0,0 +1,15 @@ +4 +5 1 +0 0 1 1 1 +0 +5 2 +6 7 8 9 15 +0 +1 +8 2 +102 92 15 19 25 54 62 36 +2 +1 +10 1 +56 73 81 23 17 92 50 34 67 78 +2 diff --git a/comp/xor-transformations-easy/main.cpp b/comp/xor-transformations-easy/main.cpp @@ -0,0 +1,86 @@ +#include <vector> +#include <algorithm> +#include <unordered_map> +#include <iostream> + +void transform(std::vector<int>& current) { + std::vector<int> expanded {}; + + for(int i = 0; i < current.size(); ++i) { + for(int x = i+1; x < current.size(); ++x) { + + expanded.push_back(current[i] ^ current[x]); + std::push_heap(expanded.begin(), expanded.end()); + + if(expanded.size() > current.size()) { + std::pop_heap(expanded.begin(), expanded.end()); + } + } + } + sort(expanded.begin(), expanded.end()); + for(int i = 0; i < current.size(); ++i) { + current[i] = expanded[i]; + } +} + + +int score(const std::vector<int>& current) { + int max = current[0]; + for(auto& val: current) + if(val > max) + max = val; + int min = current[0]; + + for(auto& val: current) + if(val < min) + min = val; + + return max - min; +} + +int main() { + + int problems = 0; + std::cin >> problems; + + for(int z = 0; z < problems; ++z) { + + int arrSize, queryCount = 0; + std::cin >> arrSize; + std::cin >> queryCount; + + std::vector<int> arr {}; + for(int i = 0; i < arrSize; ++i) { + int current = 0; + std::cin >> current; + arr.push_back(current); + + } + std::unordered_map<int,int> queries {}; + for(int i = 0; i < queryCount; ++i) { + int current = 0; + std::cin >> current; + queries[current] = i; + } + + int maxCount = 0; + + for(auto& val: queries) { + if(val.first > maxCount) { + maxCount = val.first; + } + } + + std::vector<int> results(queryCount,0); + + for(int i = 0; i <= maxCount; ++i) { + if(queries.find(i) != queries.end()) { + results[queries[i]] = score(arr); + } + transform(arr); + } + for(int i = 0; i < results.size(); ++i) { + std::cout << results[i] << std::endl; + } + } +} diff --git a/comp/xor-transformations-easy/problem.txt b/comp/xor-transformations-easy/problem.txt @@ -0,0 +1,31 @@ +F1. XOR Transformations (Easy Version) +time limit per test +4 seconds +memory limit per test +512 megabytes + +This is the easy version of the problem. The difference between the versions is that in this version, the constraints on n and q are smaller. You can make hacks only if you have solved all versions of this problem. + +For an array b consisting of m integers, define a transformation as follows: + + Write down the values bi⊕bj for all 1≤i<j≤m, where ⊕ denotes the bitwise XOR operation.. + Take the m smallest among the written values. + Replace the elements of the array with the taken m values. + +For example, consider the transformation of the array [6,7,8,9,15]. We write down the values 1,1,6,7,8,9,14,14,15,15. After the transformation, the array becomes [1,1,6,7,8] — the 5 smallest elements. + +You are given an array a consisting of n non-negative integers. Let max(a) denote the maximum element of the array a, and min(a) — the minimum. Your task is to answer q queries, each of which gives you one integer x. For each query, find the value of max(a)−min(a) after x transformations on the array. Note that the queries are independent, i.e. before each query, the array a is restored to its original state. +Input + +Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤100). The description of the test cases follows. + +The first line of each test case contains two integers n and q (5≤n≤2000,1≤q≤2000) — the size of the array and the number of queries. + +The second line of each test case contains n integers a1,a2,…,an (0≤ai<230). + +The next q lines of each test case contain an integer x (0≤x<230). + +It is guaranteed that the sum of n and the sum of q over all test cases do not exceed 2000. +Output + +For each test case, output q integers — the answer to each query. diff --git a/comp/xor-transformations-easy/thoughts.txt b/comp/xor-transformations-easy/thoughts.txt @@ -0,0 +1,50 @@ +- Array b of m integers + - Write down the values bi⊕bj for all 1≤i<j≤m, where ⊕ denotes the bitwise XOR operation.. + - so xor between b_i and b_j where both are valid and i < j + - take m smallest + - replace the elements of the array with the m selections + +--- + +[6,7,8,9,15] + +We write down the values 1,1,6,7,8,9,14,14,15,15 + +[6,7,8,9,15] + +6 xor 7, 6 xor 8, 6 xor 9, 6 xor 15, 6 xor 7, ... + +then sort and select the first m elements (not necessarily sort but def +lowest 5) + +--- + +given a of size n with non-negative numbers + +for each element of array a, x: + - perform x transformations + - return max(a) - min(a) + - each query is independent so we mustn't manipulate the underlying collct. + +--- + +The first line of each test case contains two integers n and q (5≤n≤2000,1≤q≤2000) — the size of the array and the number of queries. + +The second line of each test case contains n integers a1,a2,…,an (0≤ai<230). + +The next q lines of each test case contain an integer x (0≤x<230). + +It is guaranteed that the sum of n and the sum of q over all test cases do not exceed 2000. + +output: + +For each test case, output q integers — the answer to each query. + +--- + +- approach: + - we could just find the largest x and answer all incremental steps + - this would just use memoization + - there's an alt approach that'd track which states we care about too + - math approach + - xor has some nice properties, perhaps there's something there