ICPC 2023 Online Challenge powered by Huawei

6 months ago, # ^ |

Definitely. This competition is much different from the regular "speedforces", since you will be working on a single (but hard problem) for 2 weeks, iterating on it finding better approximations (instead of exact solutions). You will have time to research and possibly learn many new things. I have seen in the previous competition some people performing really well having "low" rating, or unranked.

→ Reply

saelcc03

6 months ago, # ^ |

Here an on-going pupil registered for the contest ^^

I hope to be specialist by that day tho.

→ Reply

LittleXi

6 months ago, # |

so many awards!

→ Reply

tiny_fish

6 months ago, # |

o.O

→ Reply

Erinyes

6 months ago, # |

It's such a great chance to improve and have fun!

Especially working accompanied by the best players in the world.

→ Reply

Yang8on

6 months ago, # |

-12

nice! can't wait XD

→ Reply

klelo

6 months ago, # |

how many do usually attempt this? i just want a t-shirt :D

→ Reply

eulerscheZahl

6 months ago, # ^ |

That's the last round, prizes were almost the same: https://codeforces.com/contest/1813/standings

The rounds before had even less participants, probably because the problem statement was longer and harder to understand.

→ Reply

6 months ago, # |

._. yea time for me to have a skill issue

→ Reply

Inscryption

6 months ago, # ^ |

So true, same

→ Reply

6 months ago, # |

wait is this rated

→ Reply

Abdallah_Nasser

6 months ago, # ^ |

-8

???

→ Reply

6 months ago, # ^ |

-8

nvm its probably not rated

→ Reply

Abdallah_Nasser

6 months ago, # ^ |

-8

can you explain some information about this contest please

→ Reply

6 months ago, # ^ |

its an contest sponsored by huawei it includes 1 singular problem which is NP-Hard im probably not the best at explaining this but NP-Hard is on the difficulty of the Turing Halting Problem (non-deterministic polynomial-time hard)

→ Reply

Abdallah_Nasser

6 months ago, # ^ |

-8

Thanks bro

→ Reply

cosmohack

6 months ago, # |

great!!

→ Reply

log2win

6 months ago, # |

Will be there an additional mirror for Huawei employees, like the previous time?

→ Reply

HuaweiChallenge

5 months ago, # ^ |

Dear participant, Thank you for your interest in our contest. Unfortunately, this time additional mirror for Huawei employees is not provided.

→ Reply

Ag_Zenitsu

6 months ago, # |

Waku waku!

→ Reply

lyxleo

6 months ago, # |

be far ahead!

→ Reply

Fatnaoui

6 months ago, # |

there is any certificate for the participants ?

→ Reply

Sunnetbayev.S.S

6 months ago, # |

0_0

→ Reply

bitset

6 months ago, # |

+28

hmmmmm it still says post-world finals in the contest page

→ Reply

LOVESTONE

6 months ago, # |

-8

Jiangly will win the championship.

→ Reply

ninji

6 months ago, # |

← Rev. 2 →

-29

O_o

→ Reply

dylan1006498

6 months ago, # |

← Rev. 2 →

How hard is this problem gonna be lol?

→ Reply

Traumatize

6 months ago, # |

-14

Is it rated?

→ Reply

Skywalker_OIer

6 months ago, # |

O_O

→ Reply

ninji

5 months ago, # |

← Rev. 2 →

-9

Enjoy the contest!

→ Reply

Sanan_Sadichov

5 months ago, # |

Your code here...
cout<"Good luck, we hope this will be fun!"<<endl;

→ Reply

wsq127

5 months ago, # |

我嘞个豆，精神大爆发 I'm chinese,I'm proud!!! 华为太帅了（

→ Reply

__3clf

5 months ago, # |

Why don't they provide Chinese questions for such competitions every time? Is it difficult to do two sets of questions? Isn't Huawei a Chinese company?

→ Reply

MahmudulHasan19

5 months ago, # |

yoooo!!

→ Reply

NaAdIsMaAh

5 months ago, # |

← Rev. 2 →

Hi, I am very green to codeforces, I have read the guidelines but I just want to make sure that I am eligible. I am senior communications engineering student. Also, to fellow codeforces users like me who have or haven't participated in a huawei challenge like this before I want to ask: "is it worth it? Should I even try or I am way out the league of most participants? Also, what is is it gonna be like ? How should i prepare"

→ Reply

tickbird

5 months ago, # |

← Rev. 2 →

-23

→ Reply

DonSilvio

5 months ago, # |

+18

Is it enough to only set your Codeforces email the same as your ICPC email to be eligible for prizes?

→ Reply

suncup224

5 months ago, # |

← Rev. 3 →

+22

Will there be system test based on hidden test set like in the previous contest, or will the leaderboard be the final results?

Update: Looks like Huawei just published an announcement that addresses this

→ Reply

I_Love_Diar_Narumov

5 months ago, # ^ |

good question!

→ Reply

saelcc03

5 months ago, # |

"Why few people participating?"

→ Reply

mursalatul_pallob

5 months ago, # |

is there any penalty for WA?

→ Reply

DestinyGod

5 months ago, # |

← Rev. 2 →

I submitted the code a dozen times yesterday, but they were all been wrong. Today I was told that the problem is the space at the end of a line, which is too stupid.

→ Reply

Ina

5 months ago, # ^ |

-35

Same, I submitted a solution at 00:10:48 that would've gotten 1000 points and put me at first place but it got WA :skull:

→ Reply

feev1x

5 months ago, # |

← Rev. 2 →

-30

Why did you put me minus((?

→ Reply

aadit04

5 months ago, # |

WOW

→ Reply

Imeon

5 months ago, # |

← Rev. 5 →

-17

Hello Codeforces

→ Reply

Pash_Mak

5 months ago, # ^ |

Yes.

→ Reply

Mob_Psycho

5 months ago, # |

-16

look at this bot's submissions. maybe you can do something? ban for example https://codeforces.com/submissions/Wizst

→ Reply

Rinkeshkumarsinha

5 months ago, # |

-13

looks difficult to me..is it?

→ Reply

nandakishore

5 months ago, # |

-13

what are the skills and basics required to understand and solve this problem?

→ Reply

5 months ago, # |

← Rev. 3 →

+23

It was a fun competition. Congratulations to all participants! Would you mind sharing your approach? I am really curious to know what people have tried, specially the top performing contestants.

→ Reply

5 months ago, # ^ |

Can you share yours?

→ Reply

5 months ago, # ^ |

← Rev. 2 →

Sure. My (final) approach is a simple greedy one.

I sort frames ascendingly by their TBS. For each frame, I sort the TTIs, ascendingly, by the amount of users that are competing (user that has not-yet processed frame overlaping this TTI) it. Then I proceed trying to schedule, on each TTI, until I can deliver all the required TBS, in the following way:

If I have rq>0 free bands on the TTI (R's with no allocation), I allocate 1 power across all cells in these rq bands with this user (I call this a WideAllocation). If this exceeds TBS, I reduce bands quantity accordingly, using bissection method to approximate/minimize the amount of bands and allocation used. (this produces no interference)
If all bands are occupied, I verify if I can grab two WideAllocations and merge to a single band-cell (R-K) (I call this a MergeAllocation), or merge one WideAllocation to an existing MergeAllocation (resulting in 3+ users allocated in the same band-cell-tti). I have some policies to decide which to choose, based on the cost (amount of band used) for each of these operations. When sucessfull, I will have a free band to try to WideAllocate on (previous item). When not sucessfull, I check for ways to merge allocations of the current frame with WideAllocations or MergeAllocations.

When not sucessfull allocating the desired frame, I undo the operations/allocations.

In all these merges, I prevent doing more than one in the same R, different K (to avoid cross-cell interference). And for the same user I avoid having more than one in the same cell (just because it changes the geometric mean, and then I would need to calculate again the transmission).

I have experimented other types of merges having cross-cell interference, or keeping different merges having the same user in the same cell, but I could not make them perform well in time.

→ Reply

5 months ago, # ^ |

Thank you! Very interesting. Looks like only try and guess the only way. May be somebody tried more "scientific" approach?

Thx, I don't think that my be interesting, but anyway:

1) Sort frames by TBS/tti 2) For each tti I select band by maximum data that can bring (considering already existing allocations). Drops if we can't satisfy TBS 3) For each r select all k that brings non zero data. 4) Find optimal distribution (minumum power with target TBS). You used bisectional method, but I use formula.

Once finished I started another approach, like previous but select all (r, k, t) for given frame, sort by data it can bring and used all the power.

After, I select remaining frames and try to assign power and check result, if frames count decreased, power assigning canceled.

All brings about 13000. If I use first step or second, it brings about 12000.

It is interesting, what is make 3000 difference between my approach and yours. Hope we can submit solutions and I will try your sorting.

Also I made a mistake that lead to same user on the same cells, but the results were not worse.

I didn't finish 2 approaches. 1) recursion 2) shaking. This one as far as I remember gave good result in previous competitions.

Sorry If smth unclear

→ Reply

5 months ago, # ^ |

13k is kinda the best you can get without allocating multiple users on same TTi-frequency-cell spot.

The 3000 difference is due to that, almost entirely.

→ Reply

jkrs2

5 months ago, # ^ |

← Rev. 2 →

Look at equation (7) in the problem Broadly we want to make the s(r,n,t,k) values large, which means keeping the bottom line of equation (7) small, which suggests making the sum over (k!=k' and n!=n') zero.

For every pair (r,t) I choose non-zero p(n,k) values so that either all the n are constant and k varies, or the k are constant and n varies.

Some frames are small. For these we can look for a few p(n,k) (varying n, fixed k) so that several frames are handled by a single (r,t) pair.

Some frames are larger. These require several p(n,k) (fixed n, varying k), and sometimes several (r,t) pairs to allocate enough transmitted bits.

So roughly my algorithm became a greedy approach in 3 steps:

Try to allocate several small frames to a single (r,t) pair
Try to allocate a small and a large frame to a single (r,t) pair
Try to allocate a small number of (r,t) pairs to a single frame.

I never managed any form of iterative hill climbing. Once power is allocated to a frame it is never removed.

My scores per test case are shown below. Many frames in test cases #33 and #38 are not sent.

Test cases #33 and #38 all have frames time length 1, so the problem might be solved as T independent small problems which might have an exhaustive search solution. Anybody made progress here?

 #1 J    2  K  2  R  1  N   2 T   2 dt  2  score   2 Percent 100%  Frames missed   0
 #2 J  266  K  2  R 10  N   2 T 800 dt  2  score 261 Percent  98%  Frames missed   5
 #3 J  497  K  2  R 10  N   5 T 800 dt  5  score 492 Percent  98%  Frames missed   5
 #4 J  800  K  4  R 10  N  10 T 400 dt  2  score 795 Percent  99%  Frames missed   5
 #5 J  356  K  4  R 10  N  50 T 100 dt 10  score 340 Percent  95%  Frames missed  16
 #6 J  150  K  2  R 10  N  10 T 400 dt 20  score 150 Percent 100%  Frames missed   0
 #7 J  120  K  4  R  5  N  20 T 200 dt 20  score 120 Percent 100%  Frames missed   0
 #8 J  160  K  4  R  5  N  20 T 200 dt 20  score 160 Percent 100%  Frames missed   0
 #9 J  709  K  4  R  5  N  50 T 100 dt  2  score 677 Percent  95%  Frames missed  32
#10 J  180  K 10  R  5  N  20 T 200 dt 10  score 180 Percent 100%  Frames missed   0
#11 J  255  K  2  R 10  N  10 T 800 dt 20  score 247 Percent  96%  Frames missed   8
#12 J  380  K  4  R  5  N  20 T 600 dt 20  score 377 Percent  99%  Frames missed   3
#13 J   80  K  4  R  5  N  20 T 100 dt 20  score  80 Percent 100%  Frames missed   0
#14 J  821  K  4  R  5  N  50 T 100 dt  1  score 801 Percent  97%  Frames missed  20
#15 J  185  K 10  R  5  N  20 T 200 dt 10  score 185 Percent 100%  Frames missed   0
#16 J  571  K  4  R 10  N  10 T 400 dt  4  score 566 Percent  99%  Frames missed   5
#17 J  354  K  4  R 10  N  50 T 100 dt 10  score 291 Percent  82%  Frames missed  63
#18 J  150  K  2  R 10  N  10 T 400 dt 20  score 149 Percent  99%  Frames missed   1
#19 J  120  K  4  R  5  N  20 T 200 dt 20  score 119 Percent  99%  Frames missed   1
#20 J  160  K  4  R  5  N  20 T 200 dt 20  score 159 Percent  99%  Frames missed   1
#21 J  829  K  4  R  5  N  50 T 100 dt  1  score 732 Percent  88%  Frames missed  97
#22 J  181  K  4  R  5  N  20 T 200 dt 10  score 171 Percent  94%  Frames missed  10
#23 J  127  K  2  R 10  N  10 T 400 dt 20  score 126 Percent  99%  Frames missed   1
#24 J  255  K  4  R  5  N  20 T 400 dt 20  score 240 Percent  94%  Frames missed  15
#25 J   80  K  4  R  5  N  20 T 100 dt 20  score  71 Percent  88%  Frames missed   9
#26 J  837  K  4  R  5  N  50 T 100 dt  1  score 751 Percent  89%  Frames missed  86
#27 J  184  K 10  R  5  N  20 T 200 dt 10  score 184 Percent 100%  Frames missed   0
#28 J  282  K  4  R 10  N  10 T 200 dt  4  score 281 Percent  99%  Frames missed   1
#29 J  355  K  4  R 10  N  50 T 100 dt 10  score 222 Percent  62%  Frames missed 133
#30 J  150  K  2  R 10  N  10 T 400 dt 20  score 147 Percent  98%  Frames missed   3
#31 J  120  K  4  R  5  N  20 T 200 dt 20  score  95 Percent  79%  Frames missed  25
#32 J  160  K  4  R  5  N  20 T 200 dt 20  score 124 Percent  77%  Frames missed  36
#33 J 1654  K  4  R  5  N 100 T 100 dt  1  score 871 Percent  52%  Frames missed 783
#34 J  181  K 10  R  5  N  20 T 200 dt 10  score 181 Percent 100%  Frames missed   0
#35 J  254  K  2  R 10  N  10 T 800 dt 20  score 253 Percent  99%  Frames missed   1
#36 J  250  K  4  R  5  N  20 T 400 dt 20  score 220 Percent  88%  Frames missed  30
#37 J   80  K  4  R  5  N  20 T 100 dt 20  score  59 Percent  73%  Frames missed  21
#38 J 1657  K  4  R  5  N 100 T 100 dt  1  score 854 Percent  51%  Frames missed 803
#39 J  185  K  8  R  5  N  20 T 200 dt 10  score 185 Percent 100%  Frames missed   0
#40 J  805  K  4  R 10  N  10 T 400 dt  2  score 792 Percent  98%  Frames missed  13
#41 J  358  K  4  R 10  N  50 T 100 dt 10  score 358 Percent 100%  Frames missed   0
#42 J  150  K  2  R 10  N  10 T 400 dt 20  score 150 Percent 100%  Frames missed   0
#43 J  120  K  4  R  5  N  20 T 200 dt 20  score 120 Percent 100%  Frames missed   0
#44 J  160  K  4  R  5  N  20 T 200 dt 20  score 160 Percent 100%  Frames missed   0
#45 J  834  K  4  R  5  N  50 T 100 dt  1  score 798 Percent  95%  Frames missed  36
#46 J  182  K 10  R  5  N  20 T 200 dt 10  score 182 Percent 100%  Frames missed   0
#47 J  255  K  2  R 10  N  10 T 800 dt 20  score 255 Percent 100%  Frames missed   0
#48 J  380  K  4  R  5  N  20 T 600 dt 20  score 368 Percent  96%  Frames missed  12
#49 J   80  K  4  R  5  N  20 T 100 dt 20  score  80 Percent 100%  Frames missed   0
#50 J  825  K  4  R  5  N  50 T 100 dt  1  score 788 Percent  95%  Frames missed  37
#51 J  184  K 10  R  5  N  20 T 200 dt 10  score 184 Percent 100%  Frames missed   0

Total Score 16153 out of 18470
Frames not transmitted: 2317

→ Reply

Degalat57

5 months ago, # ^ |

← Rev. 2 →

Yeah, cases with dt = 1 are the most interesting. Comparing my scores with yours, I can assume that all other tests are solved almost optimally with a difference of magnitude of dozens of points. However, tests 21, 26, 33, and 38 are very different; most of the differences between the participants can be explained by these tasks, transferring the problem into an interesting yet distinct one. Let us see what the proportion in the final tests would be. About tests 33 and 38, you can read my post (approach three), and about tests 21 and 26, I'm very curious myself; I hope that some other participants will explain what worked in these cases. Thank you for gathering all the statistics, by the way. I had it in a quite disorganized format

→ Reply

5 months ago, # ^ |

My score is probably similar to yours，about #21 and #26, I only got 654/680points, and about #33 and #38, I got around 1100 points. maybe there is a significant differences in decision making which lead to this condition.

→ Reply

5 months ago, # ^ |

How do you see details of every test case?

→ Reply

jkrs2

5 months ago, # ^ |

← Rev. 2 →

You make submissions with the purpose of extracting information about the answer. For example, you could do

 const int bit=0;
 if (((J>>bit)&1) == 1)
    assert(0);

and run it a few times with bit=0,1,2,...

Better, is to allocate memory, though it takes care not to lose precision.

  char *p = malloc(N*1024*1024);
  memset(p, 0xaa, N*1024*1024)

In this challenge, once you have the scoring function correctly implemented, you can adjust the power allocations for a solution to reduce the score and signal a number.

→ Reply

5 months ago, # ^ |

Thanks!

→ Reply

5 months ago, # ^ |

Nice post to share the information extraction! Very useful.

→ Reply

5 months ago, # ^ |

Like others, I used a greedy approach.

Look at each time step in order, and use a fixed list of $$$\delta p$$$ values.
For each time step, look at users $$$n$$$ who have live frames which have not yet been sent, repeat the following three greedy methods a number of times (depending on how much CPU time is left), and take the answer with the best score:

Scramble the ordering of $$$r$$$, $$$k$$$, and $$$n$$$, start with an empty time step, and loop over $$$r$$$, $$$\delta p$$$, $$$k$$$, and $$$n$$$, in that order; add each $$$(r, k, n, \delta p)$$$ if it increases the score.
Scramble the ordering of $$$r$$$, $$$k$$$, and $$$n$$$, start with an empty time step, and loop over $$$k$$$, $$$\delta p$$$, $$$r$$$, and $$$n$$$, in that order; add each $$$(r, k, n, \delta p)$$$ if it increases the score.
Scramble the ordering of $$$r$$$, $$$k$$$, and $$$n$$$, start with an empty time step, and do the following twice: loop over $$$r$$$ and $$$k$$$ and for each $$$(r, k)$$$, consider all $$$(n, \delta p)$$$, and add the $$$(r, k, n, \delta p)$$$ which makes a maximum increase to the score, if any exists.

While doing the greedy loops, I used an approximation for $$$f(x,n):=n \log(1 + x^{1/n})$$$.

→ Reply

5 months ago, # ^ |

Someone asked for my code, so I'm providing sample code in this comment. This is not my contest submission, but it illustrates the approach I used. I have disabled the second greedy method listed above, but it's still visible in the code.

Code

#pragma GCC optimize("Ofast")

#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <random>
#include <bit>
#include <numeric>

#include <windows.h>

using namespace std;

//
// --------------------------------- Basic constants and counts. ----------------------
//

const int n_bits = 192;               // Bits per one time step, radio band, and cell.
const double scale_factor = n_bits / log(2.0);
const double power_limit = 4.0;       // Maximum power per one time step, band & cell.
const double power_sum_limit = 1.0;   // Maximum average power per band,
                                      // given one time step & cell.

int nnn;   // Number of users.
int kk;    // Number of cells.
int rr;    // Number of bands.
int tt;    // Number of time steps.

//
// ----------------------------------- I/O. ------------------------------------------
//


// Input.

const size_t buff_size = 200000000;
char buff[buff_size];
char * const buff_end = buff + buff_size;
char *buff_current = buff_end;

double get_double()
{
  double a;
  int sg = 1;
  double scale = 0.0;

  for (;;)
  {
    char c = *buff_current++;

    if (c == '-')
      sg = -sg;
    else if (c >= '0' && c <= '9')
    {
      a = c - '0';
      break;
    } else if (c == '.')
    {
      a = 0;
      scale = 1.0;
      break;
    }
  }

  if (scale == 0.0)
    for (;;)
    {
      char c = *buff_current++;

      if (c == '.')
        break; 
      else if (c < '0' || c > '9')
        return a * sg;
      a = a * 10.0 + (c - '0');
    }

  scale = 1.0;

  for (;;)
  {
    char c = *buff_current++;

    if (c < '0' || c > '9')
      break;

    scale *= 10.0;
    a = a * 10.0 + (c - '0');
  }

  return a * sg / scale;
}

void init_input()
{
  if (cin.read(buff, buff_size))
    buff_current = buff;
  else
  {
    long n_read = cin.gcount();
    buff_current = buff_end - n_read - 1;
    memmove(buff_current, buff, n_read);
    buff_end[-1] = '\0';
  }
}

// Output.

// Format: digit, '.', n_digits * digit, separator.

const size_t output_buff_ct = 10000000;
const size_t n_digits = 3;

const size_t output_buff_size = (n_digits + 3) * output_buff_ct;

char output_buff[output_buff_size];
char *output_buff_cur = output_buff;

void output_double(double d, char sep)
{
  *output_buff_cur++ = '0' + (int)d;
  d -= (int)d;
  *output_buff_cur++ = '.';
  for (size_t i = 0; i < n_digits; i++)
  {
    d *= 10.0;
    *output_buff_cur++ = '0' + (int)d;
    d -= (int)d;
  }
  *output_buff_cur++ = sep;
}

void output_dump()
{
  cout.write(output_buff, nnn * kk * tt * rr * (n_digits + 3));
}

//
// ----------------------------- Approximating n log(1 + x^(1/n)). --------------------
//

long long unsigned approx_lp_ct = 0;
long long unsigned exact_lp_ct = 0;

inline double exact_lp(double val, int ct)
{
  exact_lp_ct++;

  return (ct == 0) ? 0.0 : scale_factor * ct * log1p(pow(val, 1.0 / ct));
}

#define TABLE_CTS 5
#define TABLE_BITS 14

double approx_lp_table[TABLE_CTS][1 << TABLE_BITS];

void init_lp_table()
{
  int ct;
  unsigned long long j;

  for (int v = 0; v < TABLE_CTS; v++)
    for (j = (1ULL << (64 - (TABLE_BITS + 2))), ct = 0;
         ct != (1 << TABLE_BITS);
         j += (1ULL << (64 - (TABLE_BITS + 1))), ct++)
    {
      double d = bit_cast<double>(j);
      approx_lp_table[v][ct] = scale_factor * (v + 1) * log1p(pow(d, 1.0 / (v + 1)));
    }
}

inline double approx_lp(double val, int ct)
{
  approx_lp_ct++;

  if (ct == 0)
    return 0.0;

  if (ct > TABLE_CTS)
    return exact_lp(val, ct);

  unsigned long long v = bit_cast<unsigned long long>(val) >> (64 - (TABLE_BITS + 1));
 
  return approx_lp_table[ct - 1][v]; 
}

#undef TABLE_BITS
#undef TABLE_CTS


//
// -------------------------------- Main program. ---------------------------------
//

struct LiveUser
{
  int n;           // User number.
  int tbs;         // Bits in frame (if at the start of the frame.)
  bool is_ending;  // Is the frame ending?
};

vector<vector<LiveUser> > live_users;

vector<double> sns0, ds0, drecips0;

const double total_time = 1.85;


typedef unsigned long long u64;
u64 start_time_user, start_time_kernel;

double cpu_time_left()
{
  FILETIME fftt[4];

  GetProcessTimes(GetCurrentProcess(), &fftt[3], &fftt[2], &fftt[1], &fftt[0]);
  u64 time_user = (u64)fftt[0].dwLowDateTime + (((u64)fftt[0].dwHighDateTime) << 32);
  u64 time_kernel = (u64)fftt[1].dwLowDateTime + (((u64)fftt[1].dwHighDateTime) << 32);
  double elapsed_time = (time_user - start_time_user) * 1e-7 +
                        (time_kernel - start_time_kernel) * 1e-7;
  return max(total_time - elapsed_time, 0.0);
}


//
// -------- Time: fixed (given previous time steps) data for a given time step. -------
//

class Time
{
  vector<double> sns;
  vector<double> ds;
  vector<double> drecips;

  vector<bool> at_end;
  vector<double> bits_left;
  vector<double> recip_bits_left;
  vector<int> ns;
  int nn;

public:

  int get_nn() const { return nn; }
  const vector<bool> &is_at_end() const { return at_end; }
  const vector<int> &get_ns() const { return ns; }
  const vector<double> &get_bits_left() const { return bits_left; }

  double get_advance(int n, double old_bits_left, double advance) const
  {
    return (max(old_bits_left, 0.0) - max(old_bits_left - advance, 0.0)) 
             * recip_bits_left[n];
  }

  double sn(int k, int r, int n) const 
  { 
    return sns[n + nn * (r + rr * k)];
  }

  double d(int k, int m, int r, int n) const 
  {
    return ds[n + nn * (m + nn * (r + rr * k))];
  }
  
  double drecip(int k, int m, int r, int n) const 
  {
    return drecips[n + nn * (m + nn * (r + rr * k))];
  }

  Time(int t, const vector<LiveUser> &live_users_at_time, 
              const vector<double> &curr_bits_left);
};

Time::Time
   (int t, const vector<LiveUser> &live_users_at_time, 
           const vector<double> &curr_bits_left)
{
  for (const auto & [n, bits, end] : live_users_at_time)
  {
    double our_bits_left = (bits == 0.0 ? curr_bits_left[n] : bits);
    if (our_bits_left > 0.0)
    {
      ns.push_back(n);
      at_end.push_back(end);
      bits_left.push_back(our_bits_left);
      recip_bits_left.push_back(1.0 / our_bits_left);
    }
  }

  nn = ns.size();
  ds = vector<double>(nn * nn * kk * rr, 0.0);
  drecips = vector<double>(nn * nn * kk * rr, 0.0);
  sns = vector<double>(nn * kk * rr, 0.0);

  for (int i = 0; i < kk * rr; i++)
    for (int m = 0; m < nn; m++)
      for (int n = 0; n < nn; n++)
      {
        ds[n + nn * (m + nn * i)] 
          = ds0[ns[n] + nnn * (ns[m] + nnn * i)];
        drecips[n + nn * (m + nn * i)] 
          = drecips0[ns[n] + nnn * (ns[m] + nnn * i)];
      }

  for (int i = 0; i < kk * rr; i++)
    for (int n = 0; n < nn; n++)
      sns[n + nn * i] = sns0[ns[n] + nnn * (i + rr * kk * t)];
}


//
// ------------ PartialStory: a partial assignment of powers at a given time step. ----
//

// An emission of power in a given cell and band by a given user at a given time.
struct Emission
{
  int n;
  double p;     
       // p^{(k)}_{rnt}
  double num0;  
       // s^{(k)}_{0,rnt} \prod_(m \ne n, p^{(k)}_{rmt} > 0) exp(d^{(k)}_{mrn})
  double den;   
       // 1 + \sum_{l \ne k, m \ne n} s^{(l)}_{0,rnt} p^{(l)}_{rmt} exp(-d^{(l)}_{mrn})
};

class PartialStory
{
  int nn;

  // Indexed by k.
  vector<double> cell_powers;  // sum_{n, r} p^{(k)}_{rnt}

  // Indexed by k and r.
  vector<double> powers; // sum_n p^{(k)}_{rnt}
  vector<vector<Emission> > emissions;

  // Indexed by k and n.
  vector<int> counts;     
        // Number of bands used, i.e., number of r for which p^{(k)}_{rnt} > 0.  
  vector<double> prods;
        // product of num / den = p num0 / den over r for which p^{(k)}_{rnt} > 0.  
  vector<double> scores;  
        // score = W (count) log_2(1 + (prod)^{1/(count)}).
        // Sum over k to get the total number of bits sent by a given user, n.

  // Indexed by n.
  vector<double> bits_still_left;   // Can go below zero.

public:

  PartialStory() { }

  PartialStory(const Time &ttt) 
         : nn(ttt.get_nn()),
           cell_powers(kk, 0.0),
           powers(kk * rr, 0.0),
           emissions(kk * rr, vector<Emission>()),
           counts(kk * ttt.get_nn(), 0),
           prods(kk * ttt.get_nn(), 1.0),
           scores(kk * ttt.get_nn(), 0.0),
           bits_still_left(ttt.get_bits_left())
           { }

  bool can_add(int r, int k, double power_inc) const
  {
    return cell_powers[k] <= power_sum_limit * rr - power_inc &&
           powers[r + rr * k] <= power_limit - power_inc;
  }

  void output_powers(const Time &ttt) const;
  void store_bits(vector<double> *p_curr_bits_left, const Time &ttt) const;
  void recompute_scores(const Time &ttt);
  bool compute_overall_score_and_done(double *p_score, const Time &ttt) const;
  double add_remove_power(const Time &ttt, int r, int k, int n, double power_added);

};

void PartialStory::output_powers(const Time &ttt) const
{
  vector<double> output_power(nnn, 0.0);

  for (int i = 0; i < kk * rr; i++)
  {
    for (const auto &ee : emissions[i])
      output_power[ttt.get_ns()[ee.n]] = ee.p;

    for (int m = 0; m < nnn; m++)
      output_double(output_power[m], (m == nnn - 1 ? '\n' : ' '));

    for (const auto &ee : emissions[i])
      output_power[ttt.get_ns()[ee.n]] = 0.0;
  }
}

void PartialStory::store_bits(vector<double> *p_curr_bits_left, const Time &ttt) const
{ 
  for (int n = 0; n < nn; n++)
    (*p_curr_bits_left)[ttt.get_ns()[n]] = bits_still_left[n];
}

// Compute overall score & check if done.
bool PartialStory::compute_overall_score_and_done(double *p_score, const Time &ttt) const
{
  double rv = 0.0;
  bool is_done = true;

  for (int i = 0; i < nn; i++)
  {
    double initial = ttt.get_bits_left()[i];
    double now = bits_still_left[i];

    if (now >= 0.0)
      is_done = false;

    if (ttt.is_at_end()[i] && now >= 0.0)
      now = initial;

    rv += ttt.get_advance(i, initial, initial - now);
  }

  *p_score = rv;

  return is_done;
}

//
// Returns score change, given that we add or subtract a given increment of power 
// from user n, cell k and band r.  Also adjusts the partial story.
//
double PartialStory::add_remove_power
              (const Time &ttt, int r, int k, int n, double power_added)
{
  vector<Emission> &e = emissions[r + rr * k];
  vector<Emission>::iterator ei;
  for (ei = e.begin(); ei != e.end(); ++ei)
    if (ei->n == n)
      break;

  powers[r + rr * k] += power_added;

  cell_powers[k] += power_added;

  double old_score    = scores[n + nn * k];
  double old_prod     = prods[n + nn * k];

  double new_prod;

  double rv = 0.0;

  if (ei == e.end())
  {
    double num0 = ttt.sn(k, r, n);

    for (auto &ee : e)
    {
      int m = ee.n;

      num0 *= ttt.d(k, m, r, n);

      double dd              = ttt.d(k, n, r, m);
      ee.num0                *= dd;
      double old_other_score = scores[m + nn * k];
      double new_other_prod  = prods[m + nn * k]
                             = prods[m + nn * k] * dd;
      int    other_ct        = counts[m + nn * k];
      double new_other_score = scores[m + nn * k]
                             = approx_lp(new_other_prod, other_ct);
      double delta_other_score = new_other_score - old_other_score;
      rv += ttt.get_advance(m, bits_still_left[m], delta_other_score);
      bits_still_left[m] -= delta_other_score;
    }

    double den = 1.0;

    for (int l = 0; l < kk; l++)
      if (k != l)
        for (const auto &ee : emissions[r + rr * l])
          if (ee.n != n)
            den += ee.p * ttt.sn(l, r, n) * ttt.drecip(l, ee.n, r, n);

    emissions[r + rr * k].emplace_back(n, power_added, num0, den);
    ei = e.end() - 1;

    counts[n + nn * k]++;
    new_prod = old_prod * power_added * num0 / den;
  } else 
  {
    double old_our_power = ei->p;
    double new_our_power = ei->p 
                         = old_our_power + power_added;
    if (ei->p > 0.0)
      new_prod = old_prod * new_our_power / old_our_power;
    else
    {
      counts[n + nn * k]--;
      new_prod = old_prod * ei->den / (old_our_power * ei->num0);
    }
  }

  for (int l = 0; l < kk; l++)
    if (k != l)
      for (auto &ee : emissions[r + rr * l])
        if (ee.n != n)
        {
          int m = ee.n;

          double old_other_den   = ee.den;
          double new_other_den   = ee.den 
                                 = old_other_den 
                                         +   power_added 
                                           * ttt.sn(k, r, m) * ttt.drecip(k, n, r, m);
          double old_other_score = scores[m + nn * l];
          double new_other_prod  = prods[m + nn * l]
                                 = prods[m + nn * l] * old_other_den / new_other_den;
          int    other_ct        = counts[m + nn * l];
          double new_other_score = scores[m + nn * l]
                                 = approx_lp(new_other_prod, other_ct);
          double delta_other_score = new_other_score - old_other_score;
          rv += ttt.get_advance(m, bits_still_left[m], delta_other_score);
          bits_still_left[m] -= delta_other_score;
        }

  prods[n + nn * k] = new_prod;

  int ct              = counts[n + nn * k];
  double new_score    = scores[n + nn * k] = approx_lp(new_prod, ct);
  double delta_score = new_score - old_score;
  rv += ttt.get_advance(n, bits_still_left[n], delta_score);
  bits_still_left[n] -= delta_score;

  if (ei->p == 0)
  {
    for (auto &ee : e)
      if (ee.n != n)
      {
        int m = ee.n;

        double dd_recip        = ttt.drecip(k, n, r, m);
        ee.num0                *= dd_recip;
        double old_other_score = scores[m + nn * k];
        double new_other_prod  = prods[m + nn * k]
                               = prods[m + nn * k] * dd_recip;
        int    other_ct        = counts[m + nn * k];
        double new_other_score = scores[m + nn * k]
                               = approx_lp(new_other_prod, other_ct);
        double delta_other_score = new_other_score - old_other_score;
        rv += ttt.get_advance(m, bits_still_left[m], delta_other_score);
        bits_still_left[m] -= delta_other_score;
      }

    e.erase(ei);
  }

  return rv;
}

//
// Recompute scores exactly.
//
void PartialStory::recompute_scores(const Time &ttt)
{
  for (int n = 0; n < nn; n++)
    bits_still_left[n] = ttt.get_bits_left()[n];

  int i = 0;

  for (int k = 0; k < kk; k++)
    for (int n = 0; n < nn; n++)
    {
      bits_still_left[n] -= (scores[i] = exact_lp(prods[i], counts[i]));
      i++;
    }
}

//
// ------------compute_story(): Compute power at a given timestep. --------------
//                    Use an assortment of greedy algorithms.
// 

// Power increments to use.
const vector<double> power_incs_01 = {.125, .25, .5, 1, 2};
const vector<double> power_incs_2 = {.25, .5, .75, 1};

void compute_story(int t, const vector<LiveUser> &live_users_at_time,
                          vector<double> *p_curr_bits_left)
{
  static mt19937 our_rng(5);

  double initial_left_time = cpu_time_left();
  double final_left_time = initial_left_time * (1.0 - 1.0 / (tt - t));

  const Time ttt(t, live_users_at_time, *p_curr_bits_left);

  if (ttt.get_nn() == 0)
  {
    for (int i = 0; i < kk * rr; i++)
      for (int m = 0; m < nnn; m++)
        output_double(0.0, (m == nnn - 1 ? '\n' : ' '));

    return;
  }

  PartialStory final_ps;
  double final_advance(-1e9);
  vector<int> rs(rr, 0);
  vector<int> ks(kk, 0);
  vector<int> n0s(ttt.get_nn(), 0);

  iota(rs.begin(), rs.end(), 0);
  iota(ks.begin(), ks.end(), 0);
  iota(n0s.begin(), n0s.end(), 0);

  for (;;)
  {
    double overall_advance;
    
    PartialStory ps0(ttt);
    
    shuffle(rs.begin(), rs.end(), our_rng);
    shuffle(ks.begin(), ks.end(), our_rng);
    shuffle(n0s.begin(), n0s.end(), our_rng);
     
    for (int ir = 0; ir < rr; ir++) 
    { 
      int r = rs[ir];

      for (double power_inc : power_incs_01)
        for (int ik = 0; ik < kk; ik++) 
        { 
          int k = ks[ik];

          for (int n : n0s)
            if (ps0.can_add(r, k, power_inc) &&
                ps0.add_remove_power(ttt, r, k, n, power_inc) <= 0.0)
              (void)ps0.add_remove_power(ttt, r, k, n, -power_inc);
        }
    }  

    ps0.recompute_scores(ttt);
    if (ps0.compute_overall_score_and_done(&overall_advance, ttt))
    {
      final_ps = ps0;
      break;
    } else
      if (overall_advance > final_advance)
      {
        final_advance = overall_advance;
        final_ps = ps0;
      }

#if 0 
    PartialStory ps1(ttt); 
    
    for (int ik = 0; ik < kk; ik++) 
    { 
      int k = ks[ik];

      for (double power_inc : power_incs_01) 
        for (int ir = 0; ir < rr; ir++) 
        { 
          int r = rs[ir];

          for (int n : n0s)
            if (ps1.can_add(r, k, power_inc) &&
                ps1.add_remove_power(ttt, r, k, n, power_inc) <= 0.0)
              (void)ps1.add_remove_power(ttt, r, k, n, -power_inc);
        }
    } 
  
    ps1.recompute_scores(ttt);
    if (ps1.compute_overall_score_and_done(&overall_advance, ttt))
    {
      final_ps = ps1;
      break;
    } else
      if (overall_advance > final_advance)
      {
        final_advance = overall_advance;
        final_ps = ps1;
      }
#endif

    PartialStory ps2(ttt);

    for (int greedy_2 = 0; greedy_2 < 2; greedy_2++)
    {
      bool succ = false;
       
      for (int ir = 0; ir < rr; ir++)
      {
        int r = rs[ir];

        for (int ik = 0; ik < kk; ik++)
        {
          int k = ks[ik];

          double max_advance = 0.0;
          int max_n = -1;
          double max_pow = 0.0;
   
          for (int n : n0s)
          {
            double last_power_inc = 0.0;
            double local_advance = 0.0;

            for (double power_inc : power_incs_2)
            {
              double power_inc_inc = power_inc - last_power_inc;

              if (ps2.can_add(r, k, power_inc_inc))
              {
                local_advance += ps2.add_remove_power(ttt, r, k, n, power_inc_inc);
                if (local_advance > max_advance)
                {
                  max_advance = local_advance;
                  max_n = n;
                  max_pow = power_inc;
                }
                last_power_inc = power_inc;
              }
            }
            if (last_power_inc != 0.0)
              (void)ps2.add_remove_power(ttt, r, k, n, -last_power_inc);
          }

          if (max_n >= 0)
          {
            succ = true;
            (void)ps2.add_remove_power(ttt, r, k, max_n, max_pow);
          }
        }
      }
  
      if (!succ)
        break;
    }
    
    ps2.recompute_scores(ttt);
    if (ps2.compute_overall_score_and_done(&overall_advance, ttt))
    {
      final_ps = ps2;
      break;
    } else
      if (overall_advance > final_advance)
      {
        final_advance = overall_advance;
        final_ps = ps2;
      }

    if (cpu_time_left() <= final_left_time)
      break;
  }

  final_ps.output_powers(ttt);

  final_ps.store_bits(p_curr_bits_left, ttt);
}

//
// ----------------------------- main(). ---------------------------------
//

int main()
{
  // Get starting time.
  FILETIME fftt[4];

  GetProcessTimes(GetCurrentProcess(), &fftt[3], &fftt[2], &fftt[1], &fftt[0]);
  start_time_user = (u64)fftt[0].dwLowDateTime + (((u64)fftt[0].dwHighDateTime) << 32);
  start_time_kernel = (u64)fftt[1].dwLowDateTime + (((u64)fftt[1].dwHighDateTime) << 32);

  ios::sync_with_stdio(false);
  cin.tie(NULL);

  init_input();
  init_lp_table();

  nnn = (int)get_double();
  kk = (int)get_double();
  tt = (int)get_double();
  rr = (int)get_double();

  for (int i = 0; i < rr * kk * tt * nnn; i++)
    sns0.push_back(get_double());

  for (int i = 0; i < nnn * nnn * rr * kk; i++)
  {
    double v = exp(get_double());
    ds0.push_back(v);
    drecips0.push_back(1.0 / v);
  }

  int n_frames = (int)get_double();

  live_users.assign(tt, vector<LiveUser>());
    
  for (int i = 0; i < n_frames; i++)
  {
    (void)get_double();
    int tbs  = (int)get_double();
    int n    = (int)get_double();
    int t_st = (int)get_double();
    int len  = (int)get_double();

    for (int t = t_st; t < t_st + len; t++)
      live_users[t].emplace_back(n, t == t_st ? tbs : 0, (t == t_st + len - 1));
  }  

  vector<double> curr_bits_left(nnn, 0.0);

  for (int t = 0; t < tt; t++)
    compute_story(t, live_users[t], &curr_bits_left);

  output_dump();
}

→ Reply

sroid_03

5 months ago, # |

+48

When will the system test take place?

→ Reply

Kyte

5 months ago, # ^ |

← Rev. 3 →

a few days later

Update: Oh Sorry it's not!

→ Reply

5 months ago, # |

Here is a graph of the first few scores on the leaderboard (before final testing.) Graph

→ Reply

5 months ago, # ^ |

← Rev. 2 →

+10

I updated the graph to show the first few scores on the leaderboard on the final data set (green curve) as well as the preliminary data set (purple curve.)

Here is the correlation between the two scores, showing the preliminary score on the X axis and the final score on the Y axis. This graph only shows points which come from scores which were present on both the purple and green curves above.

→ Reply

Degalat57

5 months ago, # |

← Rev. 8 →

+92

While we are all waiting for the system tests, I want to write my postmortem.

I'm a big fan of Huawei contests and already have some achievements, but I have never before seriously competed for first place. It was an exciting experience to search for the decisive optimization at 5 o'clock, having the exact same result as two other competitors a couple of hours before the end of the contest. It was a great joy to participate, independent of the final result. But I'm going too fast; let us start from the very beginning...

A small disclaimer: I have never written a serious postmortem before and am not particularly skilled in it. Anyway, I hope that some of you will find some of my ideas meaningful or at least useful. As I believe that such contests should be tried by more competitors apart from sharing ideas for this exact problem, I will try to give some broader advice so this post can be used as an introduction to heuristic contests in general. The small disclaimer is clearly too big, so let us finally start.

All right, so we looked at the task for an hour, trying to figure out what to do and realize what this formula meant. Truly saying I needed way more than an hour for that, which is rather normal for such contests. The first thing to do after that is to start doing something — this is not the kind of task that can be solved with just pen and paper. However, the formula disturbs me very much; just the realization that it will take considerable time. All right, to start, we need to make a reasonable simplification and take a subcase that seems meaningful but still ignores most of the formula. The strangest part of the formula is the exponents and the denominator of the fraction; I spent over an hour trying to understand its behavior, got not too much, and decided just to ignore it. To do so, let us say that the whole frequency at each moment of time belongs just to one user, and then the fraction consists of only the transition rate multiplied by the provided power. Having done that, we can apply the most common method in such tasks — the greedy algorithm. Let us consider the tasks in the "growing" order (there are multiple ways to make a reasonable comparator, but just sorting by size works quite well) and put them greedily on units (unit is a pair of frequency and time) — just calculate for each unit, how much it can transmit and go one by one, till the task will not be fully transmitted. There is indeed some interference due to the geometrical mean, so the resulting transmission is not just a sum, but actually, it is quite a good approximation. Before making exact thoughts about how efficient the assumption is, it is almost always better to implement it quickly and see what happens. Important remark — in such contests, you should not try to write code as quickly as possible; there is a lot of time; what matters much more is to write a bag-free code and also make it as flexible as possible for future ideas. All right, so if you have done it properly, you get around 13.5k thousand, which was top-1 on the first day and around 130th place at the end of the contest. A reasonable optimization would also be to use less power for the final unit — just make a binary search and find how much power would be exactly enough to transmit the task and leave more power to the further ones.

The obvious problem with this assumption is the overuse of space for very small tasks. If you have many more tasks than units, the previous method can clearly not help too much. So, we should consider putting multiple small tasks in one unit. There are two essentially different ways of doing that — distribute subunits between the tasks (subunit is one server with one frequency at a particular point in time), then you have an easy numerator as in the previous case, but probably a big denominator or you can put all the tasks on one subunit, then the denominator would be just one, but the numerator gets smaller. The general strategy is again to simplify the formula in a different meaningful way. But pretty much brute force, you can just check all the pairs of tasks and try to put them in a unit. If it works — perfect, try to add a third, fourth, and so on. With a little bit of time optimization, you quickly get to 15-15.5k, which was top-1 for the first 3 or 4 days and is around the 100th place currently. Again — do not overthink; just see the problem (many small tasks) and implement the most obvious solution — put small tasks together.

Having made these first approximations, one can spend a lot of time improving it, searching for better comparators, or combining a couple of them. However, one can quickly realize that this has very limited potential — 100-200 points, I will assume. In fact, it is one of the major skills in heuristic contests to estimate how much you can have from the optimization, where it makes sense to spend hours or even days on the improvement, and then you should leave the idea after just a couple of attempts. This can be normally seen by the speed of the improvement you are getting. If you have +100 points just by tuning the constants, there is probably a lot there, and you should focus more on it. If you made a reasonable optimization and got just a couple of points or none at all, it means that you either have a wrong intuition for what works in the problem and should work hard on the improvement of intuition or (and it happens more frequently) you took all form this idea and even very smart ideas of its improvement will not bring you much. If you lose a thousand points on a single test, you should probably not focus too much on 10 or 20 points on the other tests. To find this information, do not forget that it is absolutely fine and even encouraged to extract some information from the tests, especially if some tests are openly shared. The way I did it was using the memory. We know the amount of memory used with the step of 1 megabyte, so you can easily send a number between 1-100 for sure. By that, you can, for example, find out how many tasks are not transmitted by the solution, and it turns out that there are two extremely big tests — 33 and 38, where neither of the strategies gives any reasonable points. So, the number of points missing on each of these tests is higher than the sum of the missing points on all of the other tests in general. Some further analysis shows that all the td on these tests are one, and the ds are very small, around -0.1, indicating a low interference of different users. After getting this information, it was time to take a break and think about what was missing in the strategies so far.

I was thinking about many different complex approaches, but as it frequently happens in such contests, the idea is rather simple. If the interference is small, it is very useful to have many tasks in the "numerator" and no tasks in the "denominator", so we take a group of tasks and choose one server for each frequency. The only question is how to take groups of tasks and choose servers, and the most reasonable answer is simple — "random". Any reasonable implementation quickly gives you a score of 16k+, which is around place 60 — the third price. This is also the case where just a small increase in the number of random samples or the quality of the random immediately gives a hundred points. By optimizing the time efficiency of everything (very quick input with strings, precalculation of powers, global variables, and vectors), I achieved around 400 repetitions for each moment of time and the size of the set of tasks, which seems to be the border, where the further optimization does not bring much. However, this moment lies pretty far, and for me, around 1330 points on these tests — an improvement of almost 1600 points in 2 tests and the result of around 16.9k and a solid second prize. Still, I did not give up on improving my results on these tests — in general, I spent around five days just on these two tests alone, and I guess it was a huge factor in the resulting preliminary placing. A good idea was to exclude very small tasks from some of the subunits to decrease the interference factor for big tasks. This allowed me to get around 1380 points on these tasks and a score of over 17k, top-1 just a couple of days ago, and around top-15 at the end of the contest.

No matter how important these particular tests were, it is important not to miss a time to stop and think about other smaller but not that well-optimized cases. The last important breakthrough was to combine all the strategies together, just going through the time steps one by one and trying to put as many tasks as possible with all the strategies above, choosing the best combination and adding control for the given time, using exactly as many random steps as it was possible not to get TL. After some trial and error, this solution got something between 17.1-17.2k, which is somewhere between the first and second prizes currently.

Apart from these main ideas, there were many small ones — in such contests, good realization and proper choice of the local problems to be solved is significantly more important than exact ideas, which can be seen through different approaches, still very similar results in many of the contests and especially in this one, where 3 participants were exactly tied for the first place just 3 hours before the end of the contest. To choose which ideas to implement, it is important to make some small experiments, realize a small but meaningful part, and see whether improvement is present and also improve your intuition of the problem. Ideas that do not work are not less important for understanding than the ones that work. For example, in this problem, no ideas, analyzing different orders of time or order of subunits worked; also, making more than 500 random guesses never helped, so I did not try to improve efficiency further (such results can be obtained by running the code on the first ten time slots and different number of random generations). It seems that the users have rather similar connections to all of the servers at all times, so the orders do not matter. I still spent a couple of hours on the ideas, which turned out to be useless, but in contrast to my previous contests, I was able to stop investing time in them and concentrate on ideas with a high potential.

Here are some smaller ideas that worked:

1) Try different comparators for the order of added tasks in the first method; take the best of them. Random shuffling and even reversing the order helps in some small cases. This gives up to +50 points.

2) If a task can be transmitted with the higher energy of one server but fewer servers — you should rather do it. Another +20-30 points.

3) Taking tasks by the second method, try to take tasks with the higher sizes if the number of the tasks is equal, it gives a better packing, also +20-30 points.

4) If there are many tasks that need just one unit, we have an optimal method of packing — kunh algorithm. Try to apply it and not just the greed algorithm — +10-15 points because these tests were small and solved well anyway.

5) With a small task, try not to close a cluster — all frequencies at one moment of time, leave it to a big task — +10 points

I will leave apart all the optimizations, which were taking place the last night, where every single point was very valuable; I think I am more than enough already :)

If you have any questions concerning my solution, the task, or heuristic contests in general, ask them, and I will do my best to answer them. I'm also very interested in the other approaches; from a brief chat with other participants after the contest, I realized that the focus of some other participants was on the other tests, and by a combination of approaches, another much better result can be born, so looking forward to other post-mortems.

Sorry if I'm repeating obvious things or going too fast and for inaccuracies in English — the night was pretty wild for me :) Thank you to the organizers and the other participants; I'm looking forward to the next contest. Good luck with the final tests for everybody!

P.S. The final results are there; I got second place with 17326.867 points. Congrats to the winner!

P.P.S. Now, I'm looking forward to combining my solution with other participants to get a more solid result. Let me know, if you wish to contribute to this process

→ Reply

5 months ago, # ^ |

← Rev. 2 →

+11

Wow. Thank you very much for sharing so throughly. And congratulations!

→ Reply

5 months ago, # ^ |

Congratulations on your grades, thanks a lot for your postmortem that helps me to rejudge my strategy

→ Reply

5 months ago, # ^ |

Congratulations! Thanks for the detailed explanation! The way to extract test cases are pretty useful. It is really helpful to see all those strategies.

→ Reply

square1001

5 months ago, # |

← Rev. 3 →

+28

The contest was truly enjoyable even though I could participate on last few days. These type of contests are rare in CodeForces, but I like it. At last I got 16.4k points in pretests, but instead of it (if you'd like, I can also write), as at a first glance the problem seems complicated, I'd share a simple and dolce solution that may get into prize zone :)

Solution 1:

Just input $$$N, K, T, R$$$ and ignore everything.
Construct answer to be $$$p_{rnt}^{(k)} = 1$$$ if $$$n \equiv tR + r \pmod N$$$, otherwise $$$p_{rnt}^{(k)} = 0$$$.
Surprisingly this gives 8.0k points ~~and reach top 1% of registrants~~. Intuition is the best thing I can believe.

Solution 2:

The solution above is inefficient, because some data are sent to the user without assigned frame.
For each $$$(t, r)$$$ in increasing order, do the following:
- Choose "least recently used" user $$$n$$$ among those assigned in time $$$t$$$.
- Set $$$p_{rnt}^{(0)} = \dots = p_{rnt}^{(K-1)} = 1$$$.
Surprisingly this gives 11.6k points, and possibly gets a T-shirt :)

→ Reply

5 months ago, # ^ |

maybe you are right, it is easy to just get a T-shirt with some simple algorithm

→ Reply

brezhart

5 months ago, # |

+22

start systests pls

→ Reply

Peter-007

5 months ago, # |

Nice contest, funny how simple greedy algorithms can earn you as much as top 200. My overthought idea barely has 11.4k after a lot of time spent. Also when systest usually happens after those contests?

→ Reply

Psyho

5 months ago, # |

← Rev. 2 →

+24

My approach: link

Includes code, provisional data stats and results from my last submit

→ Reply

https://en.wikipedia.org/wiki/Simulated_annealing

5 months ago, # ^ |

Thanks for sharing. I really like your implementation. Glad to see it performed well.

Despite not enjoying people overfitting, I agree with your take on the number of opened test cases (afterall, whoever overfits will likely fall on closed tests)

→ Reply

BallBreaker

5 months ago, # |

using not very accurate checker( but fast), you can get 5000+ points

→ Reply

Liudas

5 months ago, # ^ |

To be fair, you can achieve about 6k without using any checker at all by just giving each person some bandwidth that doesn't exceed the limit.

→ Reply

5 months ago, # ^ |

I also used simulated annealing to optimize. It can achive a pretty good score if it is allowed to run about 20s. For example, it can achieve 700+ frames on test case 21. But the time limit is the problem so only few steps are able to run.

→ Reply

BallBreaker

5 months ago, # ^ |

you know, i was shocked knowing getting 6k+ is so easy

→ Reply

5 months ago, # ^ |

Yeah, I think simulated annealing is easy to implement but time consuming. Next time I would definitely try this first before implementing those deterministic algorithm, because the results from this random optimization can give me some hints. It is good for some analysis.

→ Reply

MinaRagy06

5 months ago, # ^ |

← Rev. 2 →

My solution used a very dumb greedy without even checking anything nor using any techniques and it got 8300

I sort frames by the TBS then for the first R frames assign a unique RBG and TTI and a random power and keep repeating this and for the remaining J — R frames just assign anything xD

→ Reply

AlephZero01

5 months ago, # |

Agree that getting a t-shirt was not that hard, easier than I personally expected (good! :) ). I approached it with heavy simplifications:

(1) all stations in a specific TTI do the same thing (like a single station) and

(2) ignore frequency dependency (e.g. all RGBs behave identically).

In this scenario, I used a greedy allocation based on the approach "take the easiest frame and try to allocate it, prioritizing the TTIs with a criteria that balances volume you can transit in it (as a plus) and overall need for that TTI (as a minus)". With my surprise, given the simplifications and the greedy strategy, that led to 13.7K, that on Friday night was stably in t-shirt zone (like 110th or so).

In the last few hours, I added a second step trying to stuff the remaining frames into the t/r slots already taken, overlapping at most 2 users, starting with the easiest frames still to allocate, and with the slots belonging to already allocated frames with most wasted resources. This improved to 14.4K. But I realized just now a big mistake in this second step (it was 4am...), i.e. not freeing the resources when an allocation attempt fails. So maybe it could have gone a bit further.

Thank you for the interesting challenge! (Huawei and Mike&staff).

→ Reply

martins

5 months ago, # |

← Rev. 2 →

+13

For those interested, there is a simple greedy approach that instantly gives 13600+ points.

The base idea is to assign every $$$(t, r)$$$ to a single user $$$n^*$$$ (or frame $$$j$$$) and fill all those $$$p^k_{rn^*t}$$$ with 1. This avoids all interference.

We choose which $$$(t, r)$$$ to assign first by calculating $$$score(t, r, n) = \sum_k \log(1 + s_{0,rnt}^k)$$$, sort all $$$(t, r, n)$$$'s by their $$$score(t, r, n)/tbs_j$$$ and greedily assign $$$(t,r)\to n$$$ using highest first. If the $$$(t,r)$$$ was already assigned, skip it. If the frame is already filled, ignore that $$$(t,r)$$$.

Doing only that gives the score I said above. There are some small adjustments like choosing an incomplete frame, removing all of its power, and trying to fill another incomplete frame, but it probably gives 20+ points.

→ Reply

Coder

5 months ago, # |

+10

For me the key to getting good scores (16K+) easily was simplifying problem a bit. If you don't allow the second type of interference, the complicated SINR expression becomes much more approachable:

$$$s_{r n t}^{(k)}={s_{0, r n t}^{(k)} \times p_{r n t}^{(k)} \times \prod_{m \neq n} e^{d^{(k)}_{mrn} \times b_{r m t}^{(k)}}} \tag{7}$$$

→ Reply

5 months ago, # ^ |

I am pretty curious about how to see the interference on nominator is smaller than that on denominator. Because I think the nominator is a multiplication which could be large if there are several users in the same unit. And the denominator is just a sum. Is it because the $$$s_{0,rnt}^{(k)}$$$ term in denominator makes it large?

→ Reply

1xx55

5 months ago, # ^ |

You are right. most of times $$$s^{(k)}_{0,rnt}*p^{(k)}_{0,rnt}*e^{-d^{(k)}_{mrn}}$$$ is much larger than 1 and ruins the value of $$$s^{(k)}_{rnt}$$$ ,and the nominator 's multiplication is easier to control.You can choose those very small interference (e.g. >-0.1) and $$$s^{(k)}_{rnt}$$$ will not decrease that much.

→ Reply

1xx55

5 months ago, # ^ |

Same Idea with you. I tried not allowed both types of interference at first and get 11k.Then I tried not allowed the second type of interference and get 13k. I think accept the first type of interference is better than accept the second one. But I can't go further if I just throw the second type of interference away. I find it much harder to handle and give up at day 9. I'm curious about how to go further when an "seems optimal" strategy can already gives 13k points.

Congrats on your good grades!

→ Reply

plagues

5 months ago, # |

← Rev. 2 →

What’s happened with scores?

→ Reply

BenjaR

5 months ago, # ^ |

they just did the system testing, this should be the final scores

→ Reply

gultai4ukr

5 months ago, # |

-8

I know there never was any upsolving for Huawei challenges and I could understand the reasons why, but could you at least disclose the rest of preliminary tests so the users could try to make some more experiments on their own with possibility to compare progress against provisional leaderboard?

And thanks again for the challenge!

CC: ICPCNews HuaweiChallenge

→ Reply

geranazavr555

5 months ago, # |

+24

The system tests has been performed. The standings are finalized.

→ Reply

5 months ago, # |

so when will I get the T-shirt & money and how? is there any post that write about it?

→ Reply

gerasikoff

5 months ago, # |

← Rev. 2 →

+35

I'm really bad at this

→ Reply

Komimi

5 months ago, # |

← Rev. 9 →

+14

I used a mathematical methods to allocate the accurate power, it works well and fast on many cases except frame-intensive cases like #33, #38

1 On each tti, I sort all frames by weight = (remaining TBS) * (remaining tti) / (approximate bits in this tti) in ascending order

2 Then I try to put the frames into the current tti one by one. For any frame:

2.1 I give the same power x[k] to different RBGs below CELL[k], cuz when all x equals, the geometric mean Π(x)^1/n is maximum, SINR does not matter

2.2 Determine x[k] for each CELL via conditional extremum, suppose using all RBGs, then

min z = Σ(x[k])
log2(1 + c[1]*x[1]) + ... + log2(1 + c[K]*x[K]) = TBS/W/R, c[k] = Π{SINR[k][r]|1<=r<=R}^1/R

By this we can get the accurate power for each cell to reach the TBS of a frame, while reducing the total power to minimum. Lagrange multiplier can solve this

x[k] = [2^D / Π(c[k])]^1/K - (1 / c[k]),  D=TBS/W/R,  0<=x[k]<=4

I didn't make a good job on #33 and #38, only 900+ each. I use brute force with greedy to get a lot of possible combinations expressed as (CELL, RBG, j1,...,jn), then I find the max independent set of all tuples. I think if I allowed different frames into different units of same RBG, it would be better.

→ Reply

shiyihang

5 months ago, # |

← Rev. 2 →

-6

Hi Codeforces!

I got a message said that my submission 235524249 significantly coincides with solutions opipo/234238136. I do never know who "opipo" is, and I've found out that he is a new account register 11 days before. Since I can't see other people's submission in this contest, I can't compare my code with his to find out exactly what went wrong.

I didn't upload my code to any other website until Nov.26 17:48 (UTC+8). At that time I pushed a commit which includes my codes on my github repository. You can find it here. But the "opipo"'s last submission is at Nov.25 21:49 (UTC+8), so I think it's not reasonable.

Could anyone help me?

→ Reply

gultai4ukr

5 months ago, # |

+12

Looks like plagiarism detection is going on right now. Good to know. What would be the desired way to report some suspicious submissions/users?
CC: ICPCNews HuaweiChallenge MikeMirzayanov geranazavr555

→ Reply

T1024

5 months ago, # |

← Rev. 3 →

+12

It seems that timing is not ideal on the platform.

A common concomitant of optimization contests is that the result is not produced by a finite algorithm, but rather tries to improve it continuously, in each iteration. In such cases, we are compelled to measure the time so as not to run to TLE. And here a problem comes: we mostly can measure the wall time, while the system measures the CPU time, which are roughly the same in most cases, but in rare cases the two can differ to an extreme rate. Unfortunately, I ran into such a problem during the system test.

System test:

#46: Accepted [421 ms, 8 MB, 714.999 points] with total score: 16446.661

Practice submission with exactly same code:

#46: Accepted [1684 ms, 8 MB, 1192.999 points] with total score: 16918.661

The early return was worth 400+ points and a prize category for me.

It is not a unique problem, as far as I know other competitors also experienced this. It would be fair if Codeforces could do something about this, so that it would not happen again.

CC: MikeMirzayanov geranazavr555

→ Reply

jkrs2

5 months ago, # ^ |

How are you measuring time?

My experience is that using clock() and CLOCKS_PER_SEC has been quite reliable, but perhaps I have been lucky.

→ Reply

T1024

5 months ago, # ^ |

double time()
{
	timeval tv;
	gettimeofday(&tv,0);
	return tv.tv_sec + 1e-6*tv.tv_usec;
}

I have used this on many contests on different platforms and it has always worked.

→ Reply

BenjaR

5 months ago, # ^ |

← Rev. 2 →

This is a known problem, I noticed the same during the competition as my solution was based on trying random changes, if the time was not correctly measured I would get considerably lower scores from time to time and I was concerned for the reliability of my code on system test. At the end I was able to fix this on the last few days of the contest using the following solution https://codeforces.com/blog/entry/85677?#comment-734421.

Using only clock() / CLOCKS_PER_SEC does not fix the problem on all compilers. You can read the post above for more information.

→ Reply

eulerscheZahl

5 months ago, # ^ |

+11

This is a helpful hint, thank you for sharing. Psyho implemented the same idea. As those optimization contest are a more or less regular thing now (hooray!), I would still appreciate, if the underlying problem could be addressed for two reasons: first of all, not every contestant will find this information, causing an inequality between them. Coming from other platforms (Codingame and Topcoder mostly), it would never even have occurred to me, to measure time in a different way. In addition, that's a C++ solution. I think I can make that logic work in C#, although painful to code under Linux. But for other languages it can be a challenge to implement.

→ Reply

gleb.astashkin

5 months ago, # |

+25

hi, guys!

i finished 7th this time. Finally got some time to make a presentation about my approach. you can find it here

→ Reply

Kyte

4 months ago, # |

Hi, everyone! It's my first time participating in HUAWEI ICPC Online Chanllenge, is there anything i need to prepare before getting the winner prize, excpet for filling in the "ICPC winners form" ? And What's the date I can receive the prize? Thanks for your help!

→ Reply

Mob_Psycho

4 months ago, # |

ヽ(・∀・)ﾉ How soon will I be contacted to receive my cash prize? I am so excited. This is my first such award, and not some diplomas and certificates. I'm very sad that you don't answer

→ Reply

eulerscheZahl

4 months ago, # ^ |

+14

First of all: just lean back and wait. Huawei will contact you on their own with detailed instructions. I've never had any issues to claim the prize (except for the t-shirt: depending on where you live, customs might just send it back. At least German customs likes doing exactly that). Last time the prize was in my bank account 2 months after the contest ended.

To answer Kyte's question: You will receive a document, that you have to print, sign, scan, send back via email. There you again confirm to give them permission to use your code. The prize will even be a bit higher to account for taxes that Huawei pays on your behalf. This form also asks you for your passport number (at least did so in the past, I don't want to be responsible for you getting a passport that you don't need). If you don't have one, Huawei will wait until you do. Furthermore you have to register as a supplier on some Huawei website and enter your bank account. Confirm that with another round of print-sign-scan-upload. This step can be skipped, if you already have a supplier account.

→ Reply

Kyte

4 months ago, # ^ |

Thanks!

→ Reply

1xx55

4 months ago, # |

+16

When will Huawei 2024 Spring Online Challenge be held ? I have seen one blog and it said it will be held on Jan 12 ,2024. But that blog seems to be deleted. Should I just wait now maybe?

→ Reply

4 months ago, # ^ |

Here is the blog about delayed start: https://codeforces.com/blog/entry/124031

→ Reply

zaq1xsw2tktk

3 months ago, # |

+11

I received a reward notification email, but it says it is encrypted. How can I open it? The email content is as follows.

This message is protected with Microsoft Information Protection. You can open it using Microsoft Outlook, available for iOS, Android, Windows, and Mac OS. Get Outlook for your device here: https://aka.ms/protectedmessage. Microsoft Information Protection allows you to ensure your emails can't be copied or forwarded without your permission. Learn more at https://aka.ms/cp_rms.

→ Reply

3 months ago, # ^ |

I'm facing this problem too. I install the app on "https://aka.ms/protectedmessage" and enter, it needs me to enter my account. After I enter my account, it shows me that "User account '[email protected]' is a personal Microsoft account. Personal Microsoft accounts are not supported for this application unless explicitly invited to an organization. Try signing out and signing back in with an organizational account. "

→ Reply

meaningIess

3 months ago, # ^ |

Same question. I can't open it even using outlook.

→ Reply