Hi all ! Here's the editorial of our training contest, Some of the problems had editorial before and we put the links there, But some of them didn't and we wrote editorial for them, Hope you liked the problems and had fun :)
In this problem we can simply increase a times the current time by one minute (after each increasing we should check the hours and the minutes for overflow).
/*
* ────────────── •✵•✵• ──────────────
* | In The Name of Allah |
* ────────────── •✵•✵• ──────────────
*/
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <iomanip>
#define pb push_back
#define si(s) s.size()
#define all(a) a.begin(), a.end()
using namespace std;
typedef long long ll;
int h, m, a;
char b;
void get_input() {
cin >> h >> b >> m >> a;
}
void solve() {
while (a){
m ++;
if (m == 60){
h ++;
m = 0;
}
if (h == 24){
h = 0;
}
a --;
}
}
void output() {
if (h < 10) cout << "0" << h;
else if (h > 9) cout << h;
cout << ":";
if (m > 9) cout << m;
else cout << "0" << m;
}
int main () {
ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
int tc = 1;
// cin >> tc;
while (tc --) {
get_input(), solve(), output();
}
return 0;
}
/* Thanks Allah */
An efficient solution is while traversing the array, store sum so far in currsum. Also, maintain the count of different values of currsum in a map. If the value of currsum is equal to the desired sum at any instance increment count of subarrays by one. The value of currsum exceeds the desired sum by currsum – sum. If this value is removed from currsum then the desired sum can be obtained. From the map find the number of subarrays previously found having sum equal to currsum-sum. Excluding all those subarrays from the current subarray, gives new subarrays having the desired sum. So increase count by the number of such subarrays. Note that when currsum is equal to the desired sum then also check the number of subarrays previously having a sum equal to 0. Excluding those subarrays from the current subarray gives new subarrays having the desired sum. Increase count by the number of subarrays having sum 0 in that case.
// C++ program to find number of subarrays
// with sum exactly equal to k.
#include <bits/stdc++.h>
using namespace std;
// Function to find number of subarrays
// with sum exactly equal to k.
int findSubarraySum(int arr[], int n, int sum)
{
// STL map to store number of subarrays
// starting from index zero having
// particular value of sum.
unordered_map<int, int> prevSum;
int res = 0;
// Sum of elements so far.
int currsum = 0;
for (int i = 0; i < n; i++) {
// Add current element to sum so far.
currsum += arr[i];
// If currsum is equal to desired sum,
// then a new subarray is found. So
// increase count of subarrays.
if (currsum == sum)
res++;
// currsum exceeds given sum by currsum
// - sum. Find number of subarrays having
// this sum and exclude those subarrays
// from currsum by increasing count by
// same amount.
if (prevSum.find(currsum - sum) != prevSum.end())
res += (prevSum[currsum - sum]);
// Add currsum value to count of
// different values of sum.
prevSum[currsum]++;
}
return res;
}
int main()
{
int arr[] = { 10, 2, -2, -20, 10 };
int sum = -10;
int n = sizeof(arr) / sizeof(arr[0]);
cout << findSubarraySum(arr, n, sum);
return 0;
}
First of all, let's analyze how can we calculate the minimum number of powers of two needed to get $$$n$$$ as the sum. We can use binary representation of $$$n$$$: each bit in it, which is equal to $$$1$$$, becomes a summand in the answer.
Firstly, if the number of summands is greater than $$$k$$$ then the answer is NO. Okay, what if we don't have enough summands? Every summand $$$x$$$ $$$>$$$ $$$1$$$ can be broken down into two summands equal to $$$x / 2$$$ Let's maintain all summands greater than $$$1$$$ somewhere (stack, array, queue, multiset, anything you want), and pick an arbitrary summand and break it into two until we have exactly $$$k$$$ summands. If $$$n$$$ $$$≥$$$ $$$k$$$, then this process will terminate since we will have some summand to pick until all of them are equal to $$$1$$$.
/*
* ────────────── •✵•✵• ──────────────
* | In The Name of Allah |
* ────────────── •✵•✵• ──────────────
*/
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <iomanip>
#define pb push_back
#define si(s) s.size()
#define all(a) a.begin(), a.end()
typedef long long ll;
using namespace std;
int n, k;
ll sum;
vector <int> a;
bool f = false;
// If you submit this solution with other C++ versions except C++20 you will get ACC
// But can you tell why it will get MLE on test 1 if you submit it with C++20?
bool check(int n, int k){
a.clear();
sum = k;
for (int i = 0; i < k; i++){
a.pb(1);
}
for (int i = k - 1; i >= 0; i --){
while (sum + a[i] <= n){
sum += a[i];
a[i] *= 2;
}
}
if (sum != n) f = false;
else f = true;
}
void get_input() {
cin >> n >> k;
}
void solve() {
check(n, k);
}
void output() {
if (f == false){
cout << "NO";
return;
}
else {
cout << "YES" << '\n';
for (auto x: a){
cout << x << ' ';
}
}
}
int main () {
ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t --) {
get_input(), solve(), output();
}
return 0;
}
/* Thanks Allah */
Because of the low constraints, this problem can be solved by complete search over all problem sets (there are $$$2^{n}$$$ of them).
For every potential problem set (which can be conviniently expressed as bit mask) we need to check if it satisfies all needed criteria. We can simply find the sum of problem complexities and also the difference between the most difficult and the easiest problems in linear time, iterating over the problems that we included in our current set/bitmask. If this problem set can be used, we increase the answer by one.
The time Complexity of the solution is $$$O(2^{n} * n)$$$.
If you don't know what's bitmask read this blog.
Bonus : Find another solution without bit mask and write it down in the comments!
/*
* ────────────── •✵•✵• ──────────────
* | In The Name of *Allah* |
* ────────────── •✵•✵• ──────────────
*/
#include <algorithm>
#include <iostream>
#include <cstring>
#include <math.h>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <iomanip>
using namespace std;
#define pb push_back
typedef long long ll;
typedef long double ld;
#define si(x) (int)x.size()
#define all(x) x.begin(), x.end()
const int maxn = 20;
int a[maxn], ans, n, x, l, r;
void solve (){
cin >> n >> l >> r >> x;
for (int i = 0; i < n; i ++){cin >> a[i];}
for (int i = 0; i < (1 << n); i ++){
ll cost = 0;
int mini = 1e9, maxi = 0, kom = 0;
for (int j = 0; j < n; j ++){
if (i & (1 << j)){
++ kom;
mini = min(mini, a[j]), maxi = max(maxi, a[j]), cost += a[j];
}
}
if (cost >= l and cost <= r and maxi - mini >= x and kom >= 2){
++ ans;
}
}
cout << ans;
}
int main () {
ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
int tc = 1;
// cin >> tc;
while (tc --) {
solve();
}
return 0;
}
/* Thanks *Allah* */
Let's use map from string to vector of strings to simplify implementation. The map keys is friend names, and the values — list of phone numbers.
At first let's put all input data in map, but if vector for a current friend already contains a current number we should not put this number in the vector (for example, we can check it with help of set).
After that we need only to remove for each friend the numbers which are the suffixes of other number of that friend. The time limit allows to make it in time equals to square of phone number count for a current friend.
Now we need to iterate through map key set (it will be names of all Nolimiya's friends) and print all remaining phone numbers for each friend.
/*
* ────────────── •✵•✵• ──────────────
* | In The Name of *Allah* |
* ────────────── •✵•✵• ──────────────
*/
#include <algorithm>
#include <iostream>
#include <cstring>
#include <math.h>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <iomanip>
using namespace std;
#define pb push_back
typedef long long ll;
typedef long double ld;
#define si(x) (int)x.size()
#define all(x) x.begin(), x.end()
map <string, set <string>> a;
int n;
const int maxn = 1000;
bool mark[maxn];
bool issuf(string a, string b) {
string kom = "";
if (si(b) < si(a)) {
return false;
}
kom = b.substr(si(b) - si(a), si(a));
return (kom == a);
}
void RemovSufs(vector <string> kom) {
fill(mark, mark + maxn, 0);
for (int i = 0; i < si(kom); i ++) {
for (int j = 0; j < si(kom); j ++) {
if (i != j) {
if (issuf(kom[j], kom[i])) {
mark[j] = 1;
}
}
}
}
vector <string> ans;
for (int i = 0; i < si(kom); i ++) {
if (!mark[i]) {
ans.pb(kom[i]);
}
}
cout << si(ans) << ' ';
for (auto x : ans) {
cout << x << ' ';
}
}
void solve () {
cin >> n;
for (int i = 0; i < n; i ++) {
string kom;
cin >> kom;
int m;
cin >> m;
for (int j = 0; j < m; j ++) {
string x;
cin >> x;
a[kom].insert(x);
}
}
cout << si(a) << '\n';
for (auto x : a) {
cout << x.first << ' ';
vector <string> k;
for (auto y : x.second) {
k.pb(y);
}
RemovSufs(k);
cout << '\n';
}
}
int main () {
ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
int tc = 1;
// cin >> tc;
while (tc --) {
solve();
}
return 0;
}
/* Thanks *Allah* */
Firstly we pay 10 operations to ask in this format from $$$i$$$ = $$$0$$$ to $$$9$$$ : ask($$$i$$$, $$$i$$$, $$$i$$$, $$$i$$$) then in each query, If the first answer of system was more than 0 it means that we have one $$$i$$$ in some position of the jury's permutation, So we store it somewhere like vector or ... and do the rest of the queries, After asking the $$$10$$$ queries then we just have to permute all the permutations of the candidates and print the first $$$4$$$ values of it, it can be proven that this will take no more than $$$24$$$ queries and in total $$$34$$$ queries to guess the answer (Prove it yourself !).
Bonus : Solve the harder version of this problem here with a smarter solution!
/*
* ────────────── •✵•✵• ──────────────
* | In The Name of *Allah* |
* ────────────── •✵•✵• ──────────────
*/
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define si(x) (int)x.size()
#define all(x) x.begin(), x.end()
void solve (){
// let's first solve the easy version !
vector <int> a;
for (int i = 0; i <= 9; i ++){
cout << i << i << i << i << endl;
int c, b;
cin >> c >> b;
if (c){
a.pb(i);
}
}
do {
cout << a[0] << a[1] << a[2] << a[3] << endl;
int c, b;
cin >> c >> b;
if (c == 4){
break;
}
}while(next_permutation(all(a)));
}
int main () {
ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
int tc = 1;
// cin >> tc;
while (tc --) {
solve();
}
return 0;
}
/* Thanks *Allah* */
Good bye for now (◕ᴗ◕)
