Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

ROIgold's blog

By ROIgold, history, 4 weeks ago, In English,

Given 3 permutations of equal lengths n ≤ 105, let's call them A, B and C.
Find number of such i-s that there's no such j, that (Ai > Aj and Bi > Bj and Ci > Cj)

Read more »

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

By ROIgold, history, 4 weeks ago, In English,

This post partially reached its purpose, please ignore it as it has never ever existed, but You might look into comments, thank You!

Please, don't down-vote this post only because you might get negative rating change, because objectively, fair decisions are better for whole community, as a current result we have that, after this contest:
Some people don't get their rating at all.
And some people get fake rating. Because first ones were discarded.

So, can this round be rated even after failing on D?
This idea was fairly supported by many people in comments of this round.

I think there are also people who have a similar situation (if You are, please write in comments something like "Me too"!), please support this not post, but the idea of it to be heard by its authors. Don't even need to search for more examples, just scroll top-200 of div.2 and You'll see how many people would get their rank updated (You might be in their group, too).
Additionally, there might be people who really tried to solve D with Kruskal or other techniques, but failed, rather than with that terrible/weird/stupid/awful/... cout << 0 which added weight to such conclusion.

Maybe I'm misunderstanding/missing something, but the general idea is pure truth.

Read more »

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

By ROIgold, history, 2 months ago, In English,

This problems is nice Binary Search problem, first I figured out solution by myself, then I get WA#19 and choose to watch tutorial, but it uses the same approach, after 5 more WAs at that same 19th test, I sadly watched author's shitty written solution, but as I compared it with mine, they don't differ at all, also the contest which contains that problem doesn't allow to watch people's solutions, I did substitute long long instead of int, please point me to where I'm doing something wrong.

Problem's statement
Author's solution
Tutorial, problem F
I'm very sorry, here's my code (submission):

#include <bits/stdc++.h>

#define FILE_NAME "BattleFury"

using namespace std;

typedef long long ll;

ll up(ll n, ll d) {
    return (n + d - 1) / d;
}

signed main() {
#ifdef LOCAL
    freopen(FILE_NAME".in", "r", stdin);
    freopen(FILE_NAME".out", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);    
    ll n, damage, splash;
    cin >> n >> damage >> splash;
    vector<ll> creeps(n);
    for (ll& hp : creeps)
        cin >> hp;
    auto okay = [&](ll hits) {
        ll done = 0;
        for (ll hp : creeps) {
            ll left = max(0ll, hp - hits * splash);
            if (damage == splash) {
                if (left)
                    return false;
            } else done += up(left, damage - splash);
        }
        return (done <= hits);              
    };

    ll ans = -1;
    for (ll l = 1, r = (ll) 1e16; l <= r;) {
        ll hits = (l + r) / 2;
        if (okay(hits)) {
            ans = hits;
            r = hits - 1;                        
        } else l = hits + 1;    
    }
    cout << ans;
    return false;
}

Read more »

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

By ROIgold, history, 2 months ago, In English,

I've just submitted this solution to some DP problem 44099523 and it gets Judgement Failed verdict.
I read that this is error from Judgement System's side, please fix this.

Read more »

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

By ROIgold, history, 5 months ago, In English,

Question is solved, please ignore this post

Why if xor sum of segment is equal to sum of segment, this condition is also satisfied for all subsegments of original segment?
I know that it's true when all bits in numbers are unique, but is it the only case when it's true, and if it is, then why?

Read more »

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

By ROIgold, history, 5 months ago, In English,

Given an array of n positive integers called a
For each of q queries which are described with integers 1 ≤ l ≤ r ≤ n, output xor of unique values in segment(l, r), i.e. if x1, x2, x3, ..., xk is set of unique values from al, al + 1, al + 2, ..., ar - 2, ar - 1, ar, then output x1 xor x2 xor x3 xor ... xor xk

1 ≤ n, q ≤ 106
for all i, 1 ≤ ai ≤ 109

TL: 3.5 seconds
ML: 256 megabytes

How to solve it?
If it's possible, I'd like a solution which uses some of data structures listed below:
Segment Tree
Binary Rise/Lift
Trie
Merge Sort Tree

Read more »

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

By ROIgold, history, 6 months ago, In English,

Problem was solved!

Input is consist of 1 ≤ q ≤ 2 * 104 queries every of which are described with single positive integer n not exceeding 4 * 106.
Output is to print for each query:
Where:

x⌋ =  whole part of number, i.e. max integer which's  ≤ x
φ(x) is Euler Totient Function

OK, I can previously calculate phis of all numbers from 1 to 4 * 106 and Pi for any i, 1 ≤ i ≤ 4 * 106 in O(nlogn), but what's then? I don't know how to further optimize solution, because it is TLE with O(n) complexity per query.
Please, help me!

Read more »

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

By ROIgold, history, 6 months ago, In English,

When I try to register to icpcarchive.ecs.baylor.edu, I always get this error, how to fix it?
I really need it to submit some problems.

Read more »

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

By ROIgold, history, 6 months ago, In English,

click

But when I test this approach it gives me Wrong Answer. Can You please open my blind eyes (and stupid brain), and show me where's my mistake?
Please, if You didn't understand some of my thoughts, don't instantly dislike this post, rather just ask me in comments, and I'll reply as fast as possible.

Read more »

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

By ROIgold, history, 6 months ago, In English,

problem: 987D - Fair
ACC solution: 38952968 1372ms
TLE solution: 38952357 2000ms
Codes are actually the same, in TLE one I use multiset instead of sort. Is it normal that multiset is much slower than quicksort?

Read more »

 
 
 
 
  • Vote: I like it  
  • -15
  • Vote: I do not like it  

By ROIgold, history, 8 months ago, In English,

I'd really like to learn how to solve this problem: 961D - Пара прямых

But even if I read a tutorial and even looked at code, I didn't understand anything, because I'm an absolute zero at geometry & solution uses something like this:

inline point operator -(const point &a, const point &b) {
	return {a.x - b.x, a.y - b.y};
}

inline long long cross(const point &a, const point &b) {
	return a.x * 1ll * b.y - a.y * 1ll * b.x;
}

I'd be very grateful if someone could give me some links to learn a little geometry to be able to understand such things, or explain it in comments.

Thank you for your time & attention!

Read more »

 
 
 
 
  • Vote: I like it  
  • -7
  • Vote: I do not like it  

By ROIgold, history, 8 months ago, In English,

input:

1 <= n <= 2e5

1 <= a[i] <= n

queries:

1. 1 <= pos, value <= n: a[pos] = value

2. 1 <= l, r, x <= n: count of a[i], l <= i <= r, that a[i] >= x

My Question: how to solve it?

Read more »

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

By ROIgold, history, 9 months ago, In English,

Hello everyone! Since, I've found out that I'm weak at math & constructive tagged problems, I decided to fix it, now I'm struggling at one really cool problem. I've already read editorial but I can't understand even first line.

The problem is: 552C - Ваня и весы.

And here's my question, how can we turn a number into w-ary representation, as I know it's always possible to turn a number only to Binary Representation.

Thanks in advance!

Any help'll be appreciated!

Sorry, for my English.

Read more »

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

By ROIgold, history, 9 months ago, In English,

Hello & Nice day to everyone!

I'd like to solve this 877D - Olya and Energy Drinks problem, but I have no idea why my solution is incorrect, would someone please help me out? Here's my submission 36087913.

Thanks in advance & for attention!

Read more »

 
 
 
 
  • Vote: I like it  
  • -6
  • Vote: I do not like it  

By ROIgold, history, 9 months ago, In English,

Hello everyone! Recently, I've started to solve one very interesting problem from title statements. And if You want you can solve it in this group.

And here is my request, is here anyone who would give me some hints to solve this problem, because it seems very hard for me, thanks for attention & in advance!

Read more »

 
 
 
 

By ROIgold, history, 12 months ago, In Russian,

When I try to precompile my programm:

C:\Users\admin\Documents\JOB\Olympiad\Algo\DATA STRUCTURES\MIXED\Travel>g++ -O2 -Wall, --stack=268435456 -std=gnu++11 Travel.cpp -o Travel.exe C:\Program Files (x86)/CodeBlocks/MinGW/bin/../lib/gcc/mingw32/4.9.2/../../../../mingw32/bin/ld.exe: cannot open output file Travel.exe: Invalid argument collect2.exe: error ld returned 1 exit status

How can I fix it?

Read more »

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

By ROIgold, history, 12 months ago, In Russian,

Hello everyone, recently I started solving this problem 721C - Путешествие, but absolutely unexpectedly now I have MLE, here's my submission 33479111, I very strongly hope that someone'll help me with this for me inunderstandable MLE

Read more »

 
 
 
 

By ROIgold, history, 15 months ago, In Russian,

Hello! I was solving one problem with std::set and std::map, actually solutions are same, but with std::set 29967156 I have solved this problem but with std::map 29967113 I have W/A on Test#7 Can you please explain me where's my mistake or is there anything special about std::map and std::set?

Read more »