| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| Problem 1190. Bar of Chocolate rejudged | Vladimir Yakovlev (USU) | 1190. Плитка шоколада | 26 окт 2025 17:11 | 1 |
New tests added to the problem. Accepted solutions were rejudged. 144 authors lost Accepted status for this problem. |
| Overrated | Bot_14`~ | 1480. Талоны | 25 окт 2025 10:46 | 1 |
|
| To admins: weak tests | LeTim | 1277. Cops and Thieves | 25 окт 2025 03:10 | 2 |
My AC program prints wrong answer on this test:
9
6 7 1 6
1 8 2 6 5 1
1 2
1 3
2 4
2 5
3 4
4 6
5 6
Correct answer is NO Your test was added. Previously accepted solutions from 39 authors were affected by this test.
A bunch of other tests against the same issue and against unrelated issues were added. At the same time the time limit was reduced from 1 sec to 0.5 sec to better match the original limitations when the problem was first published.
All solutions were rejudged. 65 authors lost the Accepted status for this problem.
Thanks! |
| To ADMIN add test, because tests are weak | coder | 2175. Лестница | 21 окт 2025 04:33 | 2 |
Hi, Admins.
Please, add these case:
N > 5*10^4
a[i] = 1, for i = 1.. N-1, and
a[N] = 10^9
Q = N
p[i] = i, x[i] = i
For example:
77888
1 1 1 1 1 1 .... 1 1 77888
77888
1 1
2 2
3 3
4 4
5 5
...
77888 77888 Your test was added.
The problem was rejudged, but only your solutions were affected.
Thanks! |
| Strange statement | 🦄imosk72🦄[GTGU] | 2181. Студент, или Туда и обратно | 19 окт 2025 22:40 | 2 |
> The student’s home is located at the coordinates (1, 1), and the university is at the coordinates (N, M).
It means, for example, if N == 1 && M == 1 then university have same coordinates as home. Of course we can not use any roads in such case. But according to the sentence:
> There are a total of N streets running from north to south and M streets running from west to east.
there are some roads that can not be used. I think there should be N - 1 streets running from north to south and M - 1 streets running from west to east. The statement was updated to N, M >= 2. The tests with N == 1 or M == 1 were removed.
Thanks for bringing this up. |
| Test 7 contains intersecting squares which contradicts the statement | bidzilya | 1097. Квадратная страна 2 | 19 окт 2025 19:40 | 2 |
Tests 7 and 8 have been fixed. Thanks for spotting this.
The few affected solutions have been rejudged. |
| Input Value Exception | Juve | 1644. Куча орехов | 19 окт 2025 03:50 | 2 |
Input Values is not in a range [3, 9] I checked the tests, they are correct. The number of walnuts is in range [3, 9]. |
| Problem Editorial (written by a beginner) | Adham Essam | 2025. Стенка на стенку | 18 окт 2025 15:03 | 2 |
First of all, we need to understand which number of teams x (from 2 to k) we need to pick to distribute our fighters into.
Through intuition we might get the idea that the bigger the K **the more the fights** (which is what is required).
It can be proven that our intuition is correct; the more you divide n the better the result, therefore we will need to divide n by k.
Proof: assuming we have n = 3, now let us assume we will distribute them to 1 team where the first team is of 3 fighters, there will be 0 fights, let us now assume we will distribute them to 2 teams where the first is of 2 and second is of 1 fighters, there will be 2 fights, lastly let us assume that we will distribute them to 3 teams where each team has a fighter, there will be 3 fights, we can then deduce that for each fighter you divide into a new group more fights are formed.
Conclusion: It is always the best choice to divide by the biggest possible number you can divide by, thus we will always divide by K.
To solve the problem we can then deduce that there will always be two cases:
Case 1 (k divides n): here we simply divide fighters into k groups, each group (composed of (n/k) fighters) will fight some other group (composed of (n/k) fighters) thus the equation for the first case is simply:
(k * (k - 1) / 2) * (n / k)^2
Case 2 (k doesn't divide n): here we notice that n will be composed of x count of floor(n / k) and y count of ceil(n / k) meaning floor(n/k)*x + ceil(n/k)*y = n, and that obviously, x + y = k, through these equations we can deduce algebraically the values of x and y, and from it form our equation.
Our equation will have x groups of floor (n / k) fighters which within them will form a specific number of fights, we will also have y groups of ceil (n / k) fighters which within them will form a specific number of fights, then we will also need an to find an equation that calculates the number of fights that happens between the x groups and the y groups, through observation and deduction you will find that this will be the equation of the second case:
((x * (x - 1) / 2) * (floor(n/k))^2) +
((y * (y - 1) / 2) * (ceil(n/k))^2) +
(floor(n/k) * ceil(n/k)) * x * y
Code:
```
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t; std::cin >> t;
while (t--) {
int n, k; std::cin >> n >> k;
if (n % k == 0) {
int count = k * (k - 1) / 2;
std::cout << count * (n / k) * (n / k) << '\n';
} else {
int x = n - ((n + k - 1) / k) * k;
x = x / ((n / k) - ((n + k - 1) / k));
int y = k - x;
int part1 = (x * (x - 1) / 2) * (n / k) * (n / k);
int part2 = (y * (y - 1) / 2) * ((n + k - 1) / k) * ((n + k - 1) / k);
int part3 = (n / k) * ((n + k - 1) / k) * x * y;
std::cout << part1 + part2 + part3 << '\n';
}
}
return 0;
}
```
Edited by author 18.10.2025 15:04
Edited by author 18.10.2025 15:06
Edited by author 30.10.2025 12:18 Thank you for reading my editorial.
Edited by author 18.10.2025 15:05 |
| WA 42 | ~'Yamca`~ | 1043. Закрыть дугу | 16 окт 2025 21:12 | 1 |
WA 42 ~'Yamca`~ 16 окт 2025 21:12 if u use rational, use int128 |
| WA 2 | ~'Yamca`~ | 1043. Закрыть дугу | 16 окт 2025 21:11 | 1 |
WA 2 ~'Yamca`~ 16 окт 2025 21:11 -476 -612
-487 -615
-478 -616
ans: 66 |
| test 2 ？？？？？！！！！！！ | gaoshangbo | 1168. Radio Stations | 16 окт 2025 20:49 | 3 |
make sure you are reading m first (not n) |
| Please help | RAVEman | 1168. Radio Stations | 16 окт 2025 20:48 | 2 |
Where am i wrong? It should be obvious :) because it is WA2 #include <algorithm> #include <string> #include <set> #include <map> #include <vector> #include <queue> #include <iostream> #include <fstream> #include <iterator> #include <math.h> #include <cstdio> #include <cstdlib> #include <sstream> using namespace std; const double eps=1e-6; struct R{ int x; int y; double r; }; R r[1111]; int a[55][55]; bool s[55][55]; int n,m,k,x,y; int main(){ cin>>n>>m>>k; for(int i=0;i<m;i++) for(int j=0;j<n;j++) cin>>a[i][j]; for(int i=0;i<k;i++){ cin>>r[i].x>>r[i].y>>r[i].r; r[i].x--;r[i].y--; s[r[i].x][r[i].y]=true; } long res=0; for(int i=0;i<m;i++) for(int j=0;j<n;j++) if(!s[i][j]){ bool possible=true; double d; int mina=a[i][j]; int maxa=32000; int _mna,_mxa; for(int q=0;q<k;q++){ d=r[q].r*r[q].r-(i-r[q].x)*(i-r[q].x)-(j-r[q].y)*(j-r[q].y); if(d<-eps) {possible=false;break;} d=floor(sqrt(d+eps))+eps; _mna=d;_mna=a[r[q].x][r[q].y]-_mna; _mxa=d;_mxa=a[r[q].x][r[q].y]+_mxa; if(mina<_mna) mina=_mna; if(maxa>_mxa) maxa=_mxa; if(mina>maxa) {possible=false;break;} } if(possible) res+=(maxa-mina+1); } cout<<res<<endl; return 0; } Edited by author 01.07.2007 04:19replace cin>>n>>m>>k; with cin>>m>>n>>k; |
| My O(n) loop solution AC 0.001s, but O(1) sum solution AC 0.015s :)) | coder | 1068. Сумма | 16 окт 2025 09:07 | 1 |
|
| Problem 1281. River Basin reworked | Vladimir Yakovlev (USU) | 1281. River Basin | 16 окт 2025 03:44 | 1 |
Clarifications added to the problem statement regarding river basin definition, river intersection restrictions and input precision.
Tests that were invalid according to the clarifications have been fixed or replaced. Tests 9 and 13 contained overlapping segments making the river flow the same path back and forth; the tests have been replaced with new tests. Tests 15, 16, 18, 19 contained rivers with self-intersections; the tests have been corrected. Test 23 contained a river with a mouth lying on the segment of the other river and didn’t count as tributary; the test has been corrected, this situation is no longer allowed in the tests.
New tests have been added. In particular, tests with more than 2 rivers in a basin have been introduced.
All solutions have been rejudged. 106 authors lost, and 12 other authors gained the solved status for the problem. |
| If you have WA#47 | Keworker `~ | 2102. Миша и криптография | 11 окт 2025 20:12 | 2 |
Test 47 is some number from 1e14 to 1e18 with correct answer "No". I am stucking at Test 47. I tried some number from 1e14 to 1e18. My program give me expected result. But I cannot figure out why Test 47 give me WA. :( |
| the last digit of N...... | Imback | 1049. Отважные воздухоплаватели | 11 окт 2025 12:45 | 1 |
|
| use long long but not double | Imback | 1011. Кондукторы | 10 окт 2025 13:10 | 1 |
use long long integer and mod operator....... fuck the double. |
| If you have WA6 | ~'Yamca`~ | 2163. Собеседование | 23 сен 2025 21:38 | 1 |
try this test:
3 3
2 2
0 0 0
0 0 0
ans: 1 |
| WA2 Помогите! | Bob | 1226. йынтарбО кодяроп | 17 сен 2025 00:00 | 1 |
Почему не робит второй тест? |
| Brute force Accept in 1.625 | zser | 1044. Счастливые билеты. Easy! | 14 сен 2025 22:58 | 2 |
#include <bits/stdc++.h>
using namespace std;
int cal(int x){
int ret = 0;
while (x > 0){
ret += x % 10;
x /= 10;
}
return ret;
}
bool lucky(int x, int mm){
int a = x / mm;
int b = x % mm;
if (cal(a) == cal(b)) return true;
return false;
}
int main(){
int n;
cin >> n;
int nn = round(pow(10, n)) - 1;
int mm = round(pow(10, n / 2));
int tot = 0;
for (int i = 0; i <= nn; i++){
if (lucky(i, mm)) tot++;
}
cout << tot << endl;
}
if your code is simple and fast enough, brute force can work. the input N consists of only even numbers, meaning the number of digits won't be odd.
moreover, input range is limited between 2 and 8, meaning the only possible inputs are 2, 4, 6 and 8.
now this would be my approach :
lets say, the input number is 4 digits in length. meaning, the sum of the first 2 digits need to be equal to the sum of the last 2 digits.
what i'd do is, i'd check for all 2-digit numbers starting from 00 all the way to 99, and store the sum of their digits in an array (in this particular case there are total 100 numbers so that'd be the array length).
after storing the sums in an array, i'd run nested loops through the array. the outer loop would take a sum value from an index. the inner loop would search through all elements in the array from the beginning to the end (including that index from the outer loop too) to see if any sum value matches the outer loop's index sum value. if there's a match, the count increases by 1. the final value of the count is the answer. this process of nested loops is time consuming, so we can sort the array first and then only run the inner loop as long as the next sum values match with the current sum value. this will only improve the performance slightly, as there will still be cases that need the inner loop to run for longer.
a far better approach would be to find the maximum possible value of the sums, and then take an array of that size plus 1. for our example of 4-digit numbers, the maximum possible sum of 2-digit numbers would be 9+9=18 (or 9x2=18) because 99 is the largest 2-digit number. thus the array size here would be 18+1=19 (so that we can access from array[0] all the way to array[18] when needed).
initially, all index values of this array would be 0. as we go through all the 2-digit numbers, we'll find the sum of their digits and raise the value of the corresponding index in the array by 1. this way, we'll immediately know how many times a particular sum has occurred by just looking at that sum's index value, instead of running nested loops. for example, if array[4]=5, then the sum 4 has occurred 5 times in all 2-digit numbers (04, 13, 22, 31, 40). again, if array[5]=6, then the sum 5 has occurred 6 times (05, 14, 23, 32, 41, 50). all we need to do then is find the total sum of all the individual sum count's squares from the entire array.
in case someone doesn't understand why we need to square the individual sum counts : we only counted the sums for 2-digits in our example. but all the possible cases of the 2-digits for a particular sum will occur in both the left half and the right half of a 4-digit number. lets say, the sum value was 4 and a total of 5 cases were found where the 2-digits sum up to 4. then, for each of these 5 cases in one side, all of these 5 cases will occur too in the other side. thus, there will be 5x5=25 total cases where a 4-digit number will have the sum of its left half digits as 4 and the sum of its right half digits as 4 as well. if the sum value was 5, then we'd find 6x6=36 total such 4-digit numbers. that's why we square the individual sum counts before adding them up to the total sum.
there might be even better approaches that i'm not familiar with just yet. maybe an alien would be able to help you with such superior alien concepts. |
